Hoàng Minh Quân - THPT Ngọc Tảo - Hà Nội Viết tặng Diễn Đàn MathScope.org CHUYÊN ĐỀ: SỬ DỤNG HÀM SINH GIẢI BÀI TỐN TỔ HỢP Lời nói đầu Tổ hợp lớp tốn khó, xuất nhiều kì thi học sinh giỏi Nói đến tổ hợp không nhắc tới tốn đếm có nhiều ứng dụng thực tiễn Với u thích mơn tổ hợp vừa độ khó nó, vừa thích thú vui sướng chinh phục toán tổ hợp khó, tìm lời giải cho tốn tổ hợp giống chàng trai chinh phục gái đẹp khó tính Ngày nay, tổ hợp trở thành lĩnh vực toán phát triển, góp phần quan trọng việc ứng dụng khoa học công nghệ vào sống sản xuất Đến tồn lý thuyết tốn học cho lĩnh vực nói hồn thiện Bài tốn tổ hợp ứng dụng trực tiếp vào lĩnh vực sản xuất với mơ hình "lập lịch làm việc quan", vào giao thông vận tải với mơ "bài tốn vận tải", vào quản lý người với mơ hình "phân việc" ứng dụng gián tiếp tốn phương pháp, thuật toán giải tốn tối ưu tốn "Xếp ba lơ", toán "Người du lịch" Các toán tổ hợp giải nhiều phương pháp như: - Phương pháp sử dụng nguyên lí bù trừ - Phương pháp song ánh - Phương pháp sử dụng lí thuyết quân xe - Phương pháp hàm sinh - Phương pháp quỹ đạo Trong số phương pháp trên, phương pháp có ưu điểm riêng, phương pháp hàm sinh có ưu điểm đại, có nhiều ứng dụng toán tổ hợp, xác suất Dù cố gắng song thời gian trình độ có hạn nên ứng dụng hàm sinh xác suất chưa nêu Mọi ý kiến đóng góp xin gửi địa hoangquan9@gmail.com Hà Nội, ngày 20 tháng năm 2011 Người viết Hoàng Minh Qn-batigoal Hồng Minh Qn MathScope.org Mục lục TĨM TẮT LÍ THUYẾT ỨNG DỤNG HÀM SINH GIẢI CÁC BÀI TỐN ĐẾM ĐIỂN HÌNH 2.1 Ứng dụng hàm sinh giải toán chia kẹo Euler 2.2 Ứng dụng hàm sinh tìm cơng thức tổng quát dãy số 2.3 Ứng dụng hàm sinh chứng minh đẳng thức tổ hợp 2.4 Ứng dụng hàm sinh giải toán phân hoạch 10 Một số tốn tổng hợp Hồng Minh Qn 12 MathScope.org TĨM TẮT LÍ THUYẾT 1.Định nghĩa: Định nghĩa 1: Hàm sinh dãy số thực a0 , a1 , a2 , , an , hàm số xác định bởi: G(x) = a0 + a1 x + a2 x2 + + an xn + Định nghĩa 2: Cho dãy số thực a0 , a1 , a2 , , an , Hàm số cho công thức G(x) = ∞ n=0 an xn n! gọi hàm sinh dạng mũ dãy a0 , a1 , a2 , , an , 2.Một số đẳng thức liên quan đến hàm sinh = + x + x2 + x3 + 1−x = + 2x + 3x + 4x + (1 − x) n(n + 1) n(n + 1)(n + 2) x + x + = n = + nx + (1 − x) 2! 3! ∞ i Ci+n−1 xi i=0 = − x + x2 − x3 + 1+x 2 3 = + 2ax + 3a x + 4a x + (1 − ax) = + xr + x2r + x3r + r 1−x Hai mệnh đề thường sử dụng Mệnh đề 1: Cho hàm sinh G(x) = (1 + x + x2 + )n r a, Đặt ar hệ số xr khai triển G(x) : ar = Cr+n−1 b,(1 − xm )n = − Cn1 xm + Cn2 x2m − + (−1)n xmn c,(1 + x + x2 + + xm−1 )n = (1 − xm )n (1 + x + x2 + +)n Mệnh đề 2: (Cơng thức xác định hệ số tích hai hàm sinh) Cho hai hàm sinh hai dãy (an ),(bn ) là: A(x) = a0 + a1 x + a2 x2 + B(x) = b0 + b1 x + b2 x2 + Đặt G(x) = A(x)B(x) = (a0 + a1 x + a2 x2 + )(b0 + b1 x + b2 x2 + ) = a0 b0 + (a0 b1 + a1 b0 )x + (a0 b2 + a1 b1 + a2 b0 )x2 + (a0 b3 + a1 b2 + a2 b1 + a0 b3 )x3 + Khi hệ số xr khai triển G(x) là:a0 br + a1 br−1 + a2 br−2 + + ar−2 b2 + ar−1 b1 + ar b0 (*) Chú ý: Trong ví dụ ứng dụng hàm sinh để giải toán đếm nâng cao phần II hay sử dụng cơng thức (*) Hồng Minh Qn MathScope.org ỨNG DỤNG HÀM SINH GIẢI CÁC BÀI TỐN ĐẾM ĐIỂN HÌNH 2.1 Ứng dụng hàm sinh giải toán chia kẹo Euler Ý tưởng chung phương pháp sử dụng hàm sinh giải tốn đếm tìm hệ số xr khai triển hàm sinh với r số phần tử chọn n đối tượng với điều kiện buộc cho trước Bây vận dụng kiến thức hàm sinh vào việc giải toán đếm tổ hợp nâng cao Thơng qua nhiều ví dụ khác định hình nắm cách sử dụng hàm sinh việc giải tốn đếm tổ hợp nâng cao, Ví dụ 2.1.1 Vào ngày nghỉ chủ nhật, cô Hoa chơi mua quà 12 cam cho đứa trẻ An, Bình, Chi.Hỏi Hoa có cách phân phối 12 cam cho An có quả, Bình Chi người có quả, Chi không nhiều quả? Lời giải Hàm sinh cho số cách chọn cho An là: A(x) = x4 + x5 + x6 + x7 + x8 = x4 (1 + x + x2 + x3 + x4 ) = x4 − x5 1−x Hàm sinh cho số cách chọn cho Bình là: − x5 B(x) = x + x + x + x + x = x (1 + x + x + x + x ) = x 1−x Hàm sinh cho số cách chọn cho Chi là: − x4 C(x) = x2 + x3 + x4 + x5 = x2 (1 + x + x2 + x3 ) = x2 1−x Hàm sinh cho số cách phân phối 12 cam thỏa mãn điều kiện đề là: 2 2 x8 (1 − x5 ) (1 − x4 ) − x5 − x5 − x4 G(x) = A(x)B(x)C(x) = x x x = 1−x 1−x 1−x (1 − x)3 = x (1 − 2x + x )(1 − x ) x−1 10 = (x − x − 2x + 2x + x − x ) x−1 12 13 17 18 22 Do tìm hệ số x12 khai triển G(x) nên ta quan tâm tới hệ số U (x) = (x8 − x12 − 2x13 + 2x17 + x18 − x22 ) với bậc ≤ 12.Do U(x) có hệ số a8 , a12 thỏa mãn r r Và hệ số x khai triển V (x) = br = Cr+2 x−1 Vậy hệ số x12 khai triển G(x) là: a8 b4 + a12 b0 = 1.C64 − 1.C20 = 14 Kết luận : Cơ Hoa có 14 cách phân chia 12 cam cho đứa trẻ thỏa mãn yêu cầu An có quả, Bình Chi người có quả, Chi khơng Hồng Minh Quân MathScope.org nhiều NHẬN XÉT: Thoạt nhìn ban đầu thấy cách giải liệt kê cho lời giải ngắn gọn cách hàm sinh suy nghĩ sâu thêm thấy tốn có kiện lớn cách làm liệt kê tỏ hiệu chí khó làm được, chẳng hạn tốn thay đổi chút sau : ‘’ Vào ngày nghỉ chủ nhật, cô Hoa chơi mua quà 50 kẹo cho đứa trẻ An, Bình, Chi.Hỏi Hoa có cách phân phối 50 kẹo cho An có kẹo, Bình Chi người có kẹo, Chi không nhiều kẹo? ” Rõ ràng cách làm liệt kế tốn trở nên hiệu quả, khó khăn thời gian nhiều phải xét nhiều trường hợp.Khi giải pháp hàm sinh toán đem lại cho hiệu rõ rệt cần quan tâm tới hệ số khai triển hàm sinh tương ứng đề Trong sống thực tiễn liệu đa dạng, với toán đếm có nhiều điều kiện buộc khác việc sử dụng hàm sinh cho lời giải hiệu Ví dụ 2.1.2 Có cách xếp giỏ gồm n trái gồm (táo, chuối, cam,đào), cho số táo phải chẵn, số chuối chia hết cho năm, nhiều cam nhiều đào Lời giải Hàm sinh cho số cách chọn táo (số chẵn)là: 1 − x2 Hàm sinh cho số cách chọn chuối (số chia hết cho 5)là: B(x) = + x5 + x10 + x15 + = − x5 Hàm sinh cho số cách chọn cam (nhiều quả)là: − x5 C(x) = + x + x2 + x3 + x4 = 1−x Hàm sinh cho số cách chọn đào (nhiều quả)là: − x2 D(x) = + x = 1−x Hàm sinh cho số cách chọn loại là: ∞ 1 − x5 − x2 G(x) = A(x)B(x)C(x)D(x) = = = (i + 1)xi − x − x5 − x − x (1 − x)2 i=0 Vậy số cách chọn trái thỏa mãn đề n + cách A(x) = + x2 + x4 + x6 + = Ví dụ 2.1.3 Có cách chọn 15USD từ 20 người 19 người đầu, người đưa nhiều USD, người thứ 20 đưa 1USD USD không USD Lời giải Hoàng Minh Quân MathScope.org Hàm sinh cho số cách chọn nhiều USD từ 19 người là:A(x) = (1 + x)19 Hàm sinh cho số cách chọn 1USD USD không USD người thứ 20 là:B(x) = + x + x5 Hàm sinh cho số cách chọn 15USD là: G(x) = A(x)B(x) = (1 + x)19 (1 + x + x5 ) Chúng ta tìm hệ số x15 khai triển G(x) (1 + x)19 = Ta có: 19 k 19−k x C19 k=0 Đặt ar hệ số xr khai triển A(x), br hệ số xr khai triển r B(x).Khi ta có:ar = C19 và b0 = b1 = b5 = 15 Vậy hệ số x khai triển G(x) là:a15 b0 + a14 b1 + a13 b2 + + a0 b15 15 14 10 Ta có : a15 b0 + a14 b1 + a10 b5 = C19 + C19 + C19 = 107882 Vậy có 107882 cách chọn 15 USD thỏa mãn điều kiện đề Ví dụ 2.1.4 Tìm số nghiệm ngun dương phương trình: u + v + w + z = 27 với ≤ u, v, w,z ≤ Lời giải Hàm sinh cho số nghiệm nguyên dương phương trình là: G(x) = (x3 + x4 + + x8 )4 = [x3 (1 + x + x2 + + x5 )]4 = x12 (1 + x + x2 + + x5 )4 Số nghiệm nguyên dương phương trình hệ số x27 khai triển G(x) hệ số x15 khai triển H(x) = (1 + x + x2 + + x5 )4 4 1 − x6 Ta có: H(x) = (1 + x + x2 + + x5 )4 = = (1 − x6 )4 1−x 1−x Đặt A(x) = (1 − x6 )4 , B(x) = Ta có: 1−x A(x) = (1 − x6 )4 = − C41 x6 + C42 x12 − C43 x18 + x24 B(x) = 1−x = + C41 x + C52 x2 + C63 x3 + Do tìm hệ số x15 khai triển H(x) nên ta quan tâm tới hệ số A(x) với bậc ≤ 15 Do A(x) có hệ số a0 , a6 , a12 thỏa mãn Hoàng Minh Quân MathScope.org r r = Cr+3 Và hệ số x khai triển B(x) = br = Cr+4−1 x−1 Vậy hệ số x15 khai triển H(x) là: 15 a0 b15 + a6 b9 + a12 b3 = 1.C18 − C41 C12 + C42 C63 Vậy số nghiệm nguyên dương phương trình là: 15 + C42 C63 − C41 C12 C18 r Ví dụ 2.1.5 Phương trình: x1 + x2 + x3 + x4 + x5 = 30 có nghiệm nguyên dương thỏa mãn: ≤ x1 , x2 ≤ 10; ≤ x3 , x4 , x5 ≤ x1 , x2 chẵn Hướng giải Hàm sinh cho số nghiệm nguyên dương phương trình là: G(x) = (1 + x2 + x4 + + x10 ) (x3 + x4 + x5 ) Cơng việc tìm hệ số x30 xin giành cho bạn đọc 2.2 Ứng dụng hàm sinh tìm cơng thức tổng qt dãy số Ví dụ 2.2.1 Tìm cơng thức tổng qt dãy số (an )với : a0 = an = 2an−1 + 2n n ≥ 1(∗) Lời giải Đặt G(x) hàm sinh cho dãy (an ), có: G(x) = a0 + a1 x + a2 x2 + −2xG(x) = −2a0 x − 2a1 x2 − 2a2 x3 − Cộng hai đẳng thức ta có: G(x) − 2xG(x) = a0 + (a1 − 2a0 )x + (a2 − 2a1 )x + + (an − 2an−1 +)x + Từ giả thiết a0 = từ (*), có: G(x) − 2xG(x) = + 2x + 22 x2 + + 2n xn + = − 2x Do ∞ G(x) = = (k + 1)(2x)k (1 − 2x) k=0 Vậy an = (n + 1).2n , n Hoàng Minh Quân MathScope.org Ví dụ 2.2.2 Tìm cơng thức tổng quát dãy số(an )với : a0 = 0, a1 = n an + 5an−1 + 6an−2 = 3n Lời giải Đặt G(x) hàm sinh cho dãy (an ), có: G(x) = a0 + a1 x + a2 x2 + 5xG(x) = 5a0 x + 5a1 x2 + 5a2 x3 + 5a3 x4 + 6x2 G(x) = 6a0 x2 + 6a1 x3 + 6a2 x4 + 6a3 x5 + Cộng đẳng thức ta có: (1 + 5x + 6x2 )G(x) = a0 + (a1 + 5a0 )x + (a2 + 5a1 + 6a0 )x2 + (a3 + 5a2 + 6a1 )x3 + ∞ ixi x+3 i=2 = x + 3(2x2 + 3x3 + 4x4 + ) = x + 3x(2x + 3x2 + 4x3 + ) = −2x + 3x(1 + 2x + 3x2 + 4x3 + ) = −2x + −2x3 + 4x2 + x 3x = (1 − x)2 (1 − x)2 −2x3 + 4x2 + x −2x3 + 4x2 + x Vậy G(x) = = (1 + 5x + 6x2 )(1 − x)2 (3x + 1)(2x + 1)(1 − x)2 −2x + 4x + x A B C D Phân tích G(x) = + + + = 3x + 2x + 1 − x (1 − x)2 (3x + 1)(2x + 1)(1 − x) −2 Đồng hệ số chứng ta tìm : A = ; B = ;C = ;D = 16 48 Vậy G(x) = −2x3 + 4x2 + x 5 1 − + + = 16 + 3x + 2x 48 − x (1 − x)2 (3x + 1)(2x + 1)(1 − x) = 16 ∞ (−1) (3x) − i i=0 ∞ i (−1) (2x) + 48 i i=0 ∞ i x + ∞ i i=0 (i + 1)xi i=0 Hệ số xn khai triển G(x)là : 5 n 17 (−1)n 3n − (−1)n 2n + + (n + 1) = (−1)n 3n − (−1)n 2n + + 16 48 16 48 Hoàng Minh Quân MathScope.org Vậy an = n 17 (−1)n 3n − (−1)n 2n + + 16 48 Ví dụ 2.2.3 Tìm công thức tổng quát dãy số(an )với : a0 = an+1 = (n + 1)(an − n + 1) n Lời giải xn , từ đề ta có: n! xn+1 xn+1 ∞ ∞ a = a − n+1 n n=0 n=0 (n + 1)! n! Xét hàm sinh G(x) = ∞ n=0 an ∞ n=0 (n − 1) xn+1 n! Ta có: G(x) − = xG(x) − x2 ex + x.ex tương đương G(x) = + xex = n≥0 xn + − x xn là: an = n! + n Vậy hệ số n! Do dãy số an có cơng thức tổng quát an = n! + n 2.3 n≥0 xn+1 n! Ứng dụng hàm sinh chứng minh đẳng thức tổ hợp Ví dụ 2.3.1 Chứng minh đẳng thức tổ hợp : n + n + + n n = 2n n Lời giải Xét đa thức (1 + x)2n có hệ số xn 2n (1) n Mặt khác ta có: (1 + x)2n = (1 + x)n (1 + x)n Xét hàm sinh G(x) = H(x) = (1 + x)n có hệ số ar = br = nr 2 Hệ số xn G(x)H(x) a0 bn + a1 bn−1 an b0 = n0 + n1 + + 2 Từ (1) (2) ta có: n0 + n1 + + nn = 2n n n n (2) Ví dụ 2.3.2 (VandeMone)Chứng minh đẳng thức tổ hợp : m m n = m+n k=0 k r−k r Hướng giải Dựa vào ý tưởng lời giải 2.3.1 bạn đọc chứng minh đẳng thức VandeMone Hồng Minh Qn MathScope.org Ví dụ 2.3.3 (China1994)Chứng minh đẳng thức tổ hợp : n k n n−k = 2n+1 k k=0 k n Lời giải Ta có kk hệ số tự khai triển (1 + x)(x + x−1 )k Khi đó: n k=0 n (1 + x) x + k x n k n−k = (1 + x) k=0 n k = (1 + x) + x + = So sánh hệ số tự ta có: n n k=0 k 2n−k x+ x x k 2n−k n 1 (1 + x)(2x + x2 + 1)n = n (1 + x)2n+1 n x x k k = 2n+1 n Ví dụ 2.3.4 Chứng minh số Fibonacci viết dạng: Fn = n0 + n−1 + n−2 + Lời giải Chúng ta biết công thức dạng truy hồi số Fibonacci: F1 = F2 = n Fn = Fn−1 + Fn−2 Đặt G(x) hàm sinh cho dãy (Fn ), giả sử F0 = có: G(x) = F0 + F1 x + F2 x2 + F3 x3 + −xG(x) = −F0 x − F1 x2 − F2 x3 − −x2 G(x) = −F0 x2 − F1 x3 − F2 x4 − Cộng vế với vế ba đẳng thức trên, ta có: (1 − x − x2 )G(x) = F0 + (F1 − F0 )x + (F2 − F1 − F0 )x2 + = x x Do đó: G(x) = − x − x2 Ta viết lại G(x) sau: 1 = = + x(1 + x) + x2 (1 + x)2 + + xn (1 + x)n − x − x2 − x(1 + x) + n−2 + Hệ số xn khai triển cuối n0 + n−1 2.4 Ứng dụng hàm sinh giải toán phân hoạch Một phân hoạch số tự nhiên r cách viết r thành tổng số nguyên dương hay số không thứ tự (ai) thỏa mãn = r Hồng Minh Qn MathScope.org Ví dụ phân hoạch 2=1+1 3=2+1=1+1+1 4=3+1=2+2=2+1+1=1+1+1+1 5=4+1=3+2=3+1+1=2+2+1=2+1+1+1=1+1+1+1+1 Đặt ek số nguyên dương thành phần xuất k lần Ta có: 1e1 + 2e2 + + kek + + rer = r Xây dựng hàm sinh cho phương trình ta có: G(x) =(1 + x + x2 + x3 + + xn + ) (1 + x2 + x4 + x6 + + x2n + ) (1 + x3 + x6 + x9 + + x3n + ) .(1 + xk + x2k + x3k + + xkn + ) Ví dụ 2.4.1 Xây dựng hàm sinh đếm số nghiệm nguyên dương phương trình : 2x + 3y + 5z = r với x, y, z ≥ Hướng giải Hàm sinh cho phương trình là: (1 + x2 + x4 + + x2n )(1 + x3 + x6 + + x3n )(1 + x5 + x10 + + x5n ) Ví dụ 2.4.2 Hỏi có cách đổi tờ 500 nghìn đồng thành tờ nghìn, nghìn, nghìn, 10 nghìn, 20 nghìn Hướng giải Bài toán cho quy đếm số nghiệm nguyên dương phương trình: x1 + 2x2 + 5x3 + 10x4 + 20x5 = 500 Số nghiệm nguyên dương phương trình hệ số x500 khia triển hàm sinh: Hoàng Minh Quân MathScope.org G(x) = + x + x2 + + x2 + x4 + + x5 + x10 + + x10 + x20 + + x20 + x40 + = (1 − x) (1 − x2 ) (1 − x5 ) (1 − x10 ) (1 − x20 ) Ví dụ 2.4.3 Xây dựng hàm sinh đếm số nghiệm nguyên dương phương trình : 2x + 3y + 7z = r z≤2≤y≤8≤x với Ví dụ 2.4.4 (China 1996)Cho n số nguyên dương Tìm số đa thức P (x) với hệ số thuộc {0; 1; 2; 3} thỏa mãn P (2) = n Lời giải Đặt P (x) = a0 + a1 x + a2 x2 + + ak xk + Theo giả thiết P (2) = n nên ta có: a0 + 2a1 + 4a2 + + 2k ak + = n với 0≤ k ≤ Chúng ta xây dựng hàm sinh: G(x) = (1 + x + x2 + x3 )(1 + x2 + x4 + x6 )(1 + x4 + x8 + x12 ) ∞ k k k) + x2 + x2(2 ) + x3(2 = k=0 ∞ k+2 − x2 = = k (1 − x) (1 − x2 ) 1−x k=0 = 1 1 1 + + − x (1 − x) 41+x ∞ = k=0 Vậy có ∞ k=0 1 + (−1)n + (n + 1) xn 4 1 + (−1)n + (n + 1) 4 đa thức tỏa mãn đề Một số toán tổng hợp Ví dụ 3.1 Huấn luyện viên bóng có n cầu thủ tập luyện hàng ngày Đầu tiên huấn luyện viên chia cầu thủ thành nhómvà yêu cầu cầu thủ nhóm xếp thành hàng Nhóm thứ chọn áo da cam, áo trăng áo xanh, nhóm thứ hai chọn áo đỏ Hỏi có cách thực cơng việc chọn áo Hoàng Minh Quân MathScope.org Hướng giải Giả sử huấn luyện viên chọn k người từ nhóm thứ Đặt ak số cách mà k người chọn áo màu da cam, trắng, xanh nhóm xếp thẳng hàng nên có ak = k!3k xk ,Do hàm sinh lũy thuwad cho ak : A(x) = k≥0 k!3k = k! − 3x Tương tự đặt bm số cách chọn m người từ nhóm thứ hai xếp hàng thẳng chọn áo đỏ, ta có :bm = m! Hàm sinh cho dãy bm là: xm B(x) = m≥0 m! = m! 1−x 1 Vậy hàm sinh cho nhóm chọn áo : G(x) = A(x)B(x) = − 3x − x xn khai triển G(x) xong Đến bạn đọc cần tìm hệ số n! n! (3n+1 − 1) Đáp số : Ví dụ 3.2 Cho r đồ vật Hỏi có cách phân phối r dồ vật khác vào n hộp cho khơng có hộp rỗng Lời giải Hàm sinh lũy thừa cho số cách phân phối r đồ vật là: G(x) = x2 x3 + + x+ 2! 3! n = (ex − 1)n n = i=0 n = i=0 ∞ n (ex )n−i (−1)i i r=0 n (−1)i = r=0 Do hệ số ar = ∞ n i n i n i=0 (−1) i i=0 (n − i)r xr r! n (n − i)r i n−i (−1)i xr r! (n − i)r Ví dụ 3.3 Cho số tự nhiên r Đếm số phân hoạch r gồm thành phần xuất số 1, 2, 3, 5, Hướng giải Xây dựng hàm sinh G(x) = (1 − x)(1 − x2 )(1 − x3 )(1 − x5 )(1 − x7 ) Ví dụ 3.4 Một đơn vị đội có n người lính xếp thẳng thành hàng Người sĩ quan phân chia người lính thành nhóm nhỏ để giao nhiêm vụ Hỏi sĩ quan có cách chọn nhóm để phân cơng trực đêm Hồng Minh Qn MathScope.org Ví dụ 3.5 Có cách phân phối 25 bóng giống hệt vào bảy hộp riêng biệt cho hộp có khơng q 10 bóng số bóng tùy ý hộp sáu hộp lại Lời giải Hàm sinh cho số cách phân phối r bóng vào bảy hộp riêng biệt cho hộp có khơng q 10 bóng là: G(x) = (1 + x + x2 + x3 + + x10 )(1 + x + x2 + )6 = − x11 1−x 1−x = (1 − x11 ) 1−x 7 Đặt A(x) = − x11 , B(x) = 1−x Chúng ta có hệ số khác hàm số A(x) là: a0 = 1; a11 = −1 Và B(x) = ∞ 1−x = r r nên hệ số xr là: Cr+6 Cr+6 r=0 25 14 Vậy hệ số x25 khai triển G(x) là: a0 b25 + a11 b14 = C31 − C20 = 697521 Vậy có 697521 cách phân phối 25 bóng giống hệt vào bảy hộp riêng biệt cho hộp có khơng q 10 bóng số bóng tùy ý hộp sáu hộp cịn lại Ví dụ 3.6 Có cách chọn 25 đồ chơi từ bảy loại đồ chơi khác cho loại đồ chơi có từ đến đồ chơi chọn Lời giải Hàm sinh cho số cách chọn r đồ chơi từ bảy loại đồ chơi khác cho loại có từ đến đồ chơi chọn là: G(x) = (x2 + x3 + x4 + x5 + x6 )7 = [x2 (1 + x + x2 + x3 + x4 )]7 = x14 (1 + x + x2 + x3 + x4 )7 Để tìm hệ số x25 khai triển G(x) tìm hệ số x11 khai triển 7 1 − x5 7 H(x) = (1 + x + x + x + x ) = = (1 − x ) 1−x 1−x 7 Đặt A(x) = (1 − x ) ; B(x) = 1−x ∞ r B(x) = = Cr+6 xr 1−x r=0 Do tìm hệ số x11 khai triển H(x) nên ta quan tâm tới hệ số A(x) với bậc ≤ 11 Do A(x) có hệ số a0 ; a5 ; a10 thỏa mãn Và hệ số xr r khai triển B(x) br = Cr+6 Hoàng Minh Quân MathScope.org 11 Vậy hệ số x11 khai triển H(x) là: a0 b11 +a5 b6 +a10 b1 = 1.C17 +(−C71 )C12 + C7 C7 = 6055 Ví dụ 3.7 Tính tổng: S = 2.12 + 2.22 + 2.32 + + 2n2 Hướng giải Xuất phát từ hàm sinh: x r = 1x + 2x + 3x + + rx + (1 − x) Ta có: x d x(1 + x) x = = 12 x + 22 x2 + 32 x3 + + r2 xr + dx (1 − x) (1 − x)3 Nhân vế đẳng thức cuối với ta có: 2x(1 + x) = 2.12 x + 2.22 x2 + 2.32 x3 + + 2.r2 xr + G(x) = (1 − x)3 Vậy hệ số ar = 2r2 Ta có cần tính tổng hệ số ao + a1 + a2 + + an Ta có: G(x) 2x(x + 1) G∗ (x) = = = 2x(1 − x)−4 + 2x2 (1 − x)−4 1−x (1 − x)4 Hệ số xn khia triển 2x(1 − x)−4 hệ số xn−1 khai triển 2(1 − x)−4 Hệ số xn khia triển 2x2 (1 − x)−4 hệ số xn−2 khai triển 2(1 − x)−4 Do tổng S = (n−1)+4−1 + (n−2)+4−1 = n+2 + n+1 (n−1) (n−2)) 3 Ví dụ 3.8 Trong túi sách Long có chứa bao gồm 10 nhẫn vàng, 20 nhẫn bạc 30 viên kim cương.Hỏi Long có cách chọn 30 đồ vật để đem bán, biết loại trang sức có đồ vật lấy Lời giải Hàm sinh cho số cách chọn nhẫn vàng chọn là: M (x) = x + x2 + x3 + + x10 Hàm sinh cho số cách chọn nhẫn bạc chọn là: N (x) = x + x2 + x3 + + x20 Hàm sinh cho số cách chọn viên kim cương chọn là: P (x) = x + x2 + x3 + + x30 Vậy hàm sinh cho số cách chọn 30 đồ vật để đem bán, biết loại trang sức có Hồng Minh Qn MathScope.org đồ vật lấy là: G(x) = M (x)N (x)P (x) = (x + x2 + x3 + + x10 )(x + x2 + x3 + + x20 )(x + x2 + x3 + + x30 ) = x3 (1 + x + x2 + + x9 )(1 + x + x2 + + x19 )(1 + x + x2 + + x29 ) − x10 − x20 − x30 1−x 1−x 1−x x3 (1 − x10 )(1 − x20 )(1 − x30 ) = (1 − x)3 x3 (1 − x20 − x10 + x30 )(1 − x30 ) = (1 − x)3 x3 (1 − x30 − x20 + x50 − x10 + x40 + x30 − x60 ) = (1 − x)3 x3 (1 − x10 − x20 + x40 + x50 − x60 ) = (1 − x)3 = (x3 − x13 − x23 + x43 + x53 − x63 ) (1 − x)3 x3 (1 − x10 − x20 + x40 + x50 − x60 ) = (1 − x)3 = (x3 − x13 − x23 + x43 + x53 − x63 ) (1 − x)3 = x3 (1 − x)3 Hệ số khác khơng có bậc nhỏ 30 A(x) là: a3 = 1; a13 = −1; a23 = −1 ∞ ∞ r r r Trong B(x) = = C = Cr+2 có hệ số xr br = Cr+2 r+3−1 (1 − x) r=0 r=0 Vậy hệ số x30 khai triển hàm sinh G(x) là: 27 17 a3 b27 + a13 b17 + a23 b7 = 1.C29 − 1.C19 − 1.C97 = 199 Vậy Long có 199 cách chọn 30 đồ vật để đem bán mà loại trang sức có đồ vật lấy Đặt A(x) = x3 − x13 − x23 + x43 + x53 − x63 ; B(x) = Ví dụ 3.9 Có cách phân hoạch số tự nhiên n thành thành phần gồm số nguyên dương lẻ khác nhau? Hướng giải Bài toán trở thành tìm hệ số xn khai triển hàm sinh : 1 1 − x − x − x − x7 Ví dụ 3.10 Phương trình sau có nghiệm ngun: u + v + w + z = 20 với u ≥ 0, v ≥ 0, w = 2m, z = 2k + Hướng giải Hoàng Minh Quân MathScope.org Xét hàm sinh : G(x) = (1 + x + x2 + x3 + x4 + )2 (1 + x + x2 + x4 + )(1 + x3 + x5 + x7 + ) Ví dụ 3.11 (Đẳng thức PasCal) Chứng minh rằng: n = n−1 + n−1 k k k−1 Lời giải Xét hàm sinh Gn (x) = (1 + x)n Ta viết lại sau: Gn (x) = (1 + x)n = (1 + x)(1 + x)n−1 = (1 + x)Gn−1 x = Gn−1 (x) + xGn−1 (x) Để ý rằng: Hệ số xk khai triển Gn (x) = (1 + x)n nk , hệ số xk khai triển Gn−1 (x) + xGn−1 (x) n−1 + n−1 k k−1 n−1 Vậy nk = n−1 + k k−1 Ví dụ 3.12 (PTNK 2009) Tìm số tất số có n chữ số lập từ chữ số 3, 4, 5, chia hết cho Lời giải Một số chia hết cho tổng chữ số chia hết cho Mỗi chữ số 3, 4, 5, Xét hàm sinh G(x) = (x3 + x4 + x5 + x6 )n = g0 + g1 x + g2 x2 + + g6n x6n Gọi số tất số có n chữ số lập từ chữ số 3, 4, 5, chia hết cho Sn Sn tổng hệ số số mũ chia hết cho 2πi Gọi ε = e bậc ba ngun thủy phương trình x3 = ta có: ε2 + ε + = Ta có: G(1) + G(ε) + G(ε2 ) = 3g0 + (1 + ε + ε2 )g1 + (1 + ε + ε2 )g2 + 3g3 + = 3(g0 + g3 + g6 + ) = 3Sn Vậy G(1) + G(ε) + G(ε2 ) = (1 + + + 1)n + ε2 + + ε + = (4n + 2) Sn = n + ε + + ε2 + n Ví dụ 3.13 Cho số nguyên dương n Gọi αn số cách phân tích n thành tổng số tự nhiên lẻ, βn số cách phân tích n thành tổng số tự nhiên đôi khác Hãy chứng tỏ αn = βn Lời giải Xét hàm sinh F (x) = Hoàng Minh Quân i∈N (1 + xi + x2i + x3i + ) với i lẻ MathScope.org Hệ số xn khai triển F (x) αn Xét hàm sinh G(x) = (1 + x) (1 + x2 ) (1 + x3 ) Hệ số xn khai triển G(x) βn Ta có: 1 1 1 − x2 − x4 − x6 F (x) = , G(x) = = 3 1−x1−x 1−x 1−x 1−x 1−x − x − x − x5 Do F (x) = G(x) hay αn = βn Ví dụ 3.14 (IMO 1998 Shortlisted) Cho dãy số a0 , a1 , a2 , , an dãy số không giảm cho số tự nhiên biểu diễn dạng + 2aj + 4ak với i, j, k số tự nhiên không thiết khác Tìm a1998 Lời giải Xét hàm sinh G(x) = xa0 + xa1 + xa2 + Ta có: G(x2 ) = x2a0 + x2a1 + x2a2 + G(x4 ) = x4a0 + x4a1 + x4a2 + Vậy ta có hàm sinh: F (x) = G(x)G(x2 )G(x4 ) = i,j,k xai +2aj +4ak Theo giả thiết: Mọi số tự nhiên biểu diễn dạng + 2aj + 4ak với i, j, k số tự nhiên không thiết khác ên ta biểu diễn F (x) = + x + x2 + x3 + = 1−x Từ ta có: 1−x 1 = F (x2 ) = G(x2 )G(x4 )G(x8 ) = 1−x 1−x1+x F (x) = G(x)G(x2 )G(x4 ) = G(x) = + x hay G(x) = (1 + x)G(x8 ) = (1 + x)(1 + x8 )G(x8 ) = G(x8 ) 2 Vậy G(x) = (1 + x)G(x8 ) = (1 + x)(1 + x8 )G(x8 ) = (1 + x)(1 + x8 )(1 + x8 )G(x8 ) Ta có số tự nhiên nên viết theo số biểu diễn số Do ta biểu diễn 1998 theo số , thay số số số Ta có 1998 = 11111001110(2) Do a1998 = 11111001110(8) Vì Ví dụ 3.15 Tìm số tập tập {1, 2, 3, , 2003} cho tổng phần tử chúng chia hết cho Hướng giải Xét hàm sinh G(x) = (1 + x)(1 + x2 )(1 + x3 ) (1 + x2003 ) Giả sử khai triển G(x) = an xn Ta cần tính tổng hệ số có số mũ chia hết cho 5, tức tính a0 + a5 + a10 + Đáp số: (22003 + 2401 ) Hoàng Minh Quân MathScope.org Bài tập Tìm số nghiệm nguyên dương phương trình: u + v + w + z = 20 với u, v, w,z Bài tập Tìm số nghiệm nguyên dương phương trình: u + v + w + z = 20 với u 4; v, w,z Bài tập Có cách phân phối 10 bóng giống cho cậu bé cô bé cho cậu bé bóng bé bóng? Bài tập Cơ Trang có 25 bơng hoa lọ hoa.Hỏi Trang có cách phân phối 25 bơng hoa vàị lọ hoa cho lọ có bơng hoa nhiều bơng hoa Bài tập Hỏi có cách chọn 25 bóng gồm loại bóng, xanh, đỏ, trắng.Sao cho số bóng đỏ chọn nhiều 2, số bóng xanh chọn nhiều 3; số bóng trắng chọn nhiều Bài tập Một cậu bé cha tặng 30 viên bi làm đồ chơi.Hỏi cậu bé có cách phân phối 30 viên bi vào hộp cho hai hộp đầu có chứa số chẵn viên bi số bi hộp khơng vượt q 10 viên, số bi hộp lại có viên nhiều viên Bài tập Có cách sưu tầm 24 tem từ bạn nam bạn nữ.Biết người có tem bạn nam có nhiều tem cịn bạn nữ có nhiều tem Bài tập Tìm cơng thức tổng qt dãy số (an ) với : a0 = 2, a1 = an − 6an−1 + 5an−2 = n Bài tập Tìm cơng thức tổng qt dãy số (an ) với : a0 = 0, a1 = 1, a2 = 2an = an−1 + 2an−2 − an−3 Hoàng Minh Quân n MathScope.org Bài tập 10 Tìm cơng thức tổng qt dãy số (an ) với : a0 = −4, a1 = −5 an − an−1 − 2an−2 = 4n n Bài tập 11 (IMO 1995)Cho p số nguyên tố lẻ Tìm số tập A tập hợp = , 2, , 2p} thỏa mãn: i, Tập A có p phần tử ii, Tổng phần tử tập A chia hết cho p Bài tập 12 Chứng minh số cách thêm dấu ngoặc vào vào tích gồm n + 1 nhân tử số Catalan Cn = Cn n + 2n Bài tập 13 (Rookie Contest 1990)Cho n số nguyên tố a1 , a2 , , am số nguyên dương Gọi f (k)là số m số (c1 , c2 , , cm ) thỏa mãn điều kiện ≤ ci ≤ c1 + c2 + + cm ≡ k (mod m) Chứng minh f (0) = f (1) = = f (n − 1) n|aj với j thuộc {1, 2, , m} Bài tập 14 Tìm hệ số x18 khai triển: (1 + x3 + x6 + x9 + )7 Bài tập 15 (AMM 2010) Chứng minh với số nguyên dương n ta có: n k=0 n k (2k + 1) 2n 2k 24n (n!)4 = (2n)! (2n + 1)! Bản quyền chuyên đề thuộc tác giả ban quản trị MathScope.org Hoàng Minh Quân MathScope.org TÀI LIỆU THAM KHẢO [1] Hàm sinh, Kim Đình Sơn, Mathsope.org [2] Nguyễn văn Mậu (Chủ biên), Biến phức, định lí áp dụng [3] TituAndreescu and Zuming Feng, A path to combinatorics for undergraduates [4] Titu Andreescu, Zuming Feng - 102 Combinatorial Problems [5] Combinatorics aproblem orienred approach, Daniel A.Marcus [6] Philippe Flajolet, Robert Sedgewick, Analytic combinatorics [7] John Michael Harris, Jeffry L Hirst, Michael J Mossinghoff, Combinatorics and graph theory [8] http://forum.mathscope.org/index.php Hoàng Minh Quân MathScope.org ... DỤNG HÀM SINH GIẢI CÁC BÀI TỐN ĐẾM ĐIỂN HÌNH 2.1 Ứng dụng hàm sinh giải toán chia kẹo Euler 2.2 Ứng dụng hàm sinh tìm cơng thức tổng qt dãy số 2.3 Ứng dụng hàm sinh chứng... dụ ứng dụng hàm sinh để giải toán đếm nâng cao phần II hay sử dụng cơng thức (*) Hồng Minh Qn MathScope.org ỨNG DỤNG HÀM SINH GIẢI CÁC BÀI TOÁN ĐẾM ĐIỂN HÌNH 2.1 Ứng dụng hàm sinh giải toán chia... phương pháp sử dụng hàm sinh giải toán đếm tìm hệ số xr khai triển hàm sinh với r số phần tử chọn n đối tượng với điều kiện buộc cho trước Bây vận dụng kiến thức hàm sinh vào việc giải tốn đếm