Luận văn Các số tổ hợp liên quan đến số các phân hoạch

on của X thỏa mãn điều kiện là mỗi tập con đó đều không chứa hai số liên tiếp nào của X. Ký hiệu P1 = {A ∈ P : A chứa n− 2} và P2 = {A ∈ P : A không chứa n− 2}. Khi đó P1 ∩ P2 = ∅ và P1 ∪ P2 = P . Theo quy tắc cộng, ta có Fn = |P | = |P1| + |P2|. Mỗi A ∈ P1 đều không thể chứa n− 3. Do đó mỗi A ∈ P1 tương ứng với đúng một tập của tập X \ {n − 3, n − 2} = {1, 2, ..., n − 4} thỏa mãn điều kiện là không chứa hai số liên tiếp nào của tập X \ {n− 3, n− 2}. Suy ra |P1| = Fn−2. Mỗi tập con A2 ∈ P2 cũng là tập con của X \ {n− 2} = {1, 2, ..., n− 3}. Vì vậy, |P2| = Fn−1. Suy ra Fn = Fn−1 + Fn−2. Ta muốn tìm biểu thức tính Fn qua n bằng cách sử dụng hàm sinh thông thường. Giả sử G(t) là hàm sinh thông thường cho dãy số {Fn}∞n=0. Khi đó, G(t) = F0 + F1t + F2t 2 + F3t 3 · · · , t.G(t) = F0t + F1t 2 + F2t 3 + F3t 4 · · · , t2.G(t) = F0t 2 + F1t 3 + F2t 4 + F3t 5 · · · , Do đó, G(t) − tG(t)− t2G(t) = F0 + (F1 − F0)t + (F2 − F1 − F0)t2 + · · · + (Fn − Fn−1 − Fn−2)t n + · · · = t vì F0 = 0, F1 = 1 và Fn = Fn−1 + Fn−2 cho mọi n ≥ 2. Suy ra (1− t− t2)G(t) = t ⇐⇒ G(t) = t 1 − t− t2 . 42 Như vậy, ta đã tìm được hàm sinh thông thường cho dãy {Fn}∞n=0 dưới dạng biểu thức số học của các hàm hữu tỷ, cụ thể là, G(t) = t 1− t− t2 . Tiếp theo, ta cần biểu diễn G(t) dưới dạng chuỗi lũy thừa. Để làm điều này, trước tiên ta phân tích t 1 − t− t2 thành tổng các phân thức đơn giản bằng phương pháp hệ số bất định. Xét tam thức bâc hai 1− t− t2. Tam thức này có hai nghiệm phân biệt là a = 1 + √ 5 −2 và b = 1 −√5 −2 . Suy ra t 1− t− t2 = −t (t− a)(t− b) = A (t− a) + B (t− b) = (A + B)t− (Ab + Ba) (t− a)(t− b) . Vì vậy ta nhận được hệ phương trình sau đây để xác định A và B :  Ab + Ba = 0 A + B = −1 Giải hệ phương trình này ta được A = a (b− a) và B = −b (b− a) , tức là t 1− t− t2 = a (b− a)(t− a) − b (b− a)(t− b). Ta có a (b− a)(t− a) = 1 a− b · 1 1 − t a = 1 a− b ∞∑ n=0 tn an b (b− a)(t− b) = 1 a− b · 1 1− t b = 1 a− b ∞∑ n=0 tn bn . Vì a− b = −√5 nên từ hai đẳng thức ở trên ta nhận được t 1 − t− t2 = − 1√ 5 ∞∑ n=0 tn an + 1√ 5 ∞∑ n=0 tn bn = ∞∑ n=0 [ 1√ 5 ( 1 bn − 1 an )] tn. 43 Ta lại có 1 bn − 1 an = an − bn (−1)n = (−a) n − (−b)n. Do đó t 1− t− t2 = ∞∑ n=0 1√ 5 [( 1 + √ 5 2 )n − ( 1−√5 2 )n] tn. Suy ra Fn = 1√ 5 [( 1 + √ 5 2 )n − ( 1 −√5 2 )n] cho mọi n = 0, 1, 2, .... Một điều lý thú trong công thức trên là ta đã dùng số vô tỷ để biểu diễn các số nguyên. Ví dụ 2.7. Có n hình vuông rời nhau kích thước tương ứng là 1 × 1, 2 × 2, ..., n× n cần được lát bằng các viên gạch kích thước 1× 1. Tính số viên gạch cần thiết để lát đủ n hình vuông đó (bằng công thức phụ thuộc vào n). Giải. Gọi an là số viên gạch cần thiết để lát đủ n hình vuông đã cho. Khi đó, dễ thấy rằng an = n∑ k=0 k2. Do đó, a0 = 0, an − an−1 = n∑ k=0 k2 − n−1∑ k=0 k2 = n2 cho mọi n ≥ 1 Ta sử dụng hàm sinh thông thường để tính an. Giả sử G(t) là hàm sinh thông thường của dãy {an}∞n=0. Khi đó G(t) = a0 + a1t + a2t 2 + a3t 3 + · · · tG(t) = a0t + a1t 2 + a2t 3 + a3t 4 + · · · Do đó, G(t)− tG(t) = a0 + (a1 − a0)t + (a2 − a1)t2 + (a3 − a2)t3 + · · · = ∞∑ n=0 n2tn Suy ra (1 − t)G(t) = ∞∑ n=0 n2tn. (2.2) 44 Ta muốn nhận được biểu thức số học của các hàm hữu tỷ cho chuỗi ở bên vế phải của đẳng thức trên. Để làm được điều đó, xuất phát từ công thức (2.1 ) ta có : 1 (1 − t)2 = ∞∑ n=0 Cnn+1t n ⇐⇒ 1 (1− t)2 = ∞∑ n=0 (n + 1)tn. Suy ra t (1− t)2 = ∞∑ n=0 (n + 1)tn+1. Lấy đạo hàm hai vế của đẳng thức này ta được 1 + t (1 − t)3 = ∞∑ n=0 (n + 1)2tn. Suy ra t + t2 (1 − t)3 = ∞∑ n=0 (n + 1)2tn+1 = ∞∑ n=0 n2tn. (2.3) Từ hai công thức (2.2 ) và ( 2.3) ta được (1− t)G(t) = t + t 2 (1 − t)3 , tức là G(t) = t + t2 (1− t)4 . Giả sử t + t2 (1 − t)4 = A 1 − t + B (1− t)2 + C (1 − t)3 + D (1 − t)4 = A(1− t)3 + B(1− t)2 + C(1− t) + D (1− t)4 = −At3 + (3A + B)t2 + (−3A− 2B − C)t + (A + B + C + D) (1− t)4 . Suy ra   −A = 0 3A + B = 1 −3A− 2B − C = 1 A + B + C + D = 0 Giải hệ phương trình trên ta được A = 0, B = 1, C = −3, D = 2, tức là G(t) = t + t2 (1− t)4 = 1 (1 − t)2 − 3 (1 − t)3 + 2 (1 − t)4 . 45 Sử dụng công thức (2.1 ) ta được G(t) = 1 (1− t)2 − 3 (1− t)3 + 2 (1− t)4 = ∞∑ n=0 Cnn+1t n − 3 ∞∑ n=0 Cnn+2t n + 2 ∞∑ n=0 Cnn+3t n = ∞∑ n=0 ( Cnn+1 − 3Cnn+2 + 2Cnn+3 ) tn = ∞∑ n=0 n(n + 1)(2n + 1) 6 tn . Vậy an = n∑ k=0 k2 = n(n + 1)(2n + 1) 6 . Ví dụ 2.8. Số Catalan. Số Catalan là một con số quan trọng trong tổ hợp, là lời giải của nhiều bài toán đếm tổ hợp quan trọng. Ta dẫn ra ở đây một trong những bài toán như vậy. Xét việc tính tích của các ma trận : A = A0A1...An. Do tích ma trận có tính chất kết hợp nên có nhiều cách để thực hiện việc tính tích trên. Ví dụ khi n = 3, ta có thể thực hiện việc tính tích A = A0A1A2A3 theo 5 cách sau: A = A0(A1(A2A3)) = A0((A1A2)A3) = (A0A1)(A2A3) = (A0(A1A2))A3 = ((A0A1)A2)A3. Ta gọi số Catalan thứ n là số cách thực hiện việc tính A = A0A1...An là tích của n + 1 ma trận A0, A1, ..., An, ký hiệu là cn. Ta tính cn theo n. Dễ thấy c1 = 1, c2 = 2. Để cho tiện sử dụng, ta định nghĩa c0 = 1. Nếu ta đặt dấu ngoặc phân tách đầu tiên vào sau thừa số Ak: A = (A0A1...Ak)(Ak+1Ak+2...An), 46 thì có ck cách thực hiện việc tính A0A1...Ak và cn−k−1 cách thực hiện việc tính Ak+1Ak+2...An, suy ra có ckcn−k−1 cách tính A trong trường hợp này. Do dấu ngoặc phân tách đầu tiên có thể đặt sau Ai, i = 0, 1, ..., n− 1, nên ta thu được cn = n−1∑ k=0 ckcn−k−1 = c0cn−1 + c1cn−2 + c2cn−3 + · · ·+ cn−1c0. Gọi c(t) là hàm sinh thông thường của dãy số {cn}∞n=o. Khi đó, c(t) = c0 + c1t + c2t 2 + c3t 3 + · · · (c(t)) 2 = c20 + (c0c1 + c1c0)t + (c0c2 + c2c0)t 2 + · · · + (c0cn−1 + c1cn−2 + · · ·+ cn−1c0)tn−1 + · · · = c1 + c2t + c3t 2 + c4t 3 + · · · . Vì thế t2(c(t))2 = t ( c1t + c2t 2 + c3t 3 + · · · ) = t [c(t)− 1] = tc(t) − t, tức là (tc(t))2 − tc(t) + t = 0. Giải phương trình bậc hai đối với tc(t) ta tìm được tc(t) = 1 + √ 1− 4t 2 hoặc tc(t) = 1 −√1− 4t 2 . Ta phân tích f(t) = √ 1 − 4t = (1− 4t) 12 thành chuỗi dựa vào công thức Taylor f(t) = f(0) + ∞∑ k=1 f (k)(0) k! tk. Ta có dk dtk (1− 4t) 12 = 1 2 ( 1 2 − 1 )( 1 2 − 2 )( 1 2 − k + 1 ) (1 − 4t) 12−k(−4)k. 47 Do đó, hệ số của tk trong khai triển f(t) là (−4)k 1 2 ( 1 2 − 1 )( 1 2 − 2 ) ... ( 1 2 − k + 1 ) k! = (−1)k22k 1 2 ( −1 2 )( −3 2 ) ... ( −2k − 3 2 ) k! = (−1)k22k 1.3.5...(2k − 3) k!(−1)k−12k = −2k(1.3.5...(2k − 3)) k! . Vì vậy các hệ số này là các số âm cho mọi k ≥ 1. Điều đó chứng tỏ rằng 1 + √ 1 − 4t 2 không thể bằng tc(t) vì các hệ số của tk trong tc(t) là các số nguyên dương. Vậy tc(t) = 1 −√1− 4t 2 = 1 2 [ 2 1! t + 22 2! t2 + 23.1.3 3! t3 + · · ·+ 2 k.1.3.5....(2k− 3) k! tk + · · · ] . Suy ra c(t) = 1 + 2 2! t + 22.1.3 3! t2 + · · ·+ 2 k−1.1.3.5....(2k − 3) k! tk−1 + · · · . Do đó cn = 2n.1.3.5....(2n− 1) (n + 1)! = 2n.1.2.3.4.5....(2n− 1)(2n) (n + 1)!2.4.6...(2n) = 2n(2n)! (n + 1)!n!2n = (2n)! (n + 1)n!.n! = 1 n + 1 Cn2n. Vậy cn = 1 n + 1 Cn2n. Từ công thức trên, chẳng hạn ta có c3 = 1 4 C36 = 5. 48 2.2 Phương pháp đếm dùng hàm sinh mũ Định nghĩa 2.2.1. (theo [3, 2.2]) Hàm sinh mũ của dãy số {an}∞n=0 là chuỗi lũy thừa hình thức G(t) = a0 + a1 t 1! + a2 t2 2! + a3 t3 3! + · · · = ∞∑ i=0 ai ti i! . Hàm sinh mũ đóng một vai trò nền tảng trong việc nghiên cứu các mảnh tổ hợp (combinatorial species). Trong mục này ta chỉ đề cập đến phương pháp sử dụng hàm sinh mũ để giải quyết một số bài toán đếm như thế nào. Giả sử với mỗi tập hữu hạn N ta có một tập S(N) các vật mà ta muốn đếm. Như vậy, tập các vật cần đếm S(N) phụ thuộc vào tập N . Các vật của S(N) có thể xem như là "được gắn nhãn" hay "được đỡ " bởi tập N . Vì vậy, tập N có thể xem như là tập giá hay ngắn gọn gọi là giá của S(N). Do đó, nếu N và M là các tập hữu hạn khác nhau, tức là N 6= M , thì ta luôn giả thiết rằng S(N)∩S(M) = ∅. Hơn thế nữa, nếu |N | = |M |, thì ta cũng luôn giả thiết rằng |S(N)| = |S(M)|. Khi đó, hàm sinh mũ cho dãy các tập S([0]), S([1]), S([2]), ... hay ngắn gọn {S([n])}∞n=0, được định nghĩa là hàm sinh mũ cho dãy số |S([0])|, |S([1])|, |S([2])|, .... Ta quy ước [0] = ∅. Giả sử {T ([j])}∞j=0 là một dãy các tập các vật khác. Ta định nghĩa tập ST ([j]) là tập bao gồm tất cả các cặp (σ, τ ), ở đây σ là một phần tử của tập S(K) với K là một tập con bất kỳ của [j], còn τ là một phần tử của tập T (K) với K = [j] \K. Khi đó, |ST ([j])| = j∑ k=0 Ckj |S([k])||T ([j− k])| Ký hiệu hàm sinh mũ cho dãy {S([j])}∞j=0,{T ([j])}∞j=0 và {ST ([j])}∞j=0 tương ứng là S(t), T (t) và ST (t). Tức là 49 S(t) = |S(∅)|+ |S([1])| t 1! + |S([2])|t 2 2! + |S([3])|t 3 3! + · · · T (t) = |T (∅)|+ |T ([1])| t 1! + |T ([2])|t 2 2! + |T ([3])|t 3 3! + · · · ST (t) = |ST (∅)|+ |ST ([1])| t 1! + |ST ([2])|t 2 2! + |ST ([3])|t 3 3! + · · · Khi đó theo định nghĩa của ST ([j]) ở trên, ta thấy rằng ST (t) = S(t).T (t). Ví dụ 2.9. Với mỗi z ∈ C ta có ezt = 1 + z t 1! t + z2 t2 2! + z3 t3 3! + · · · Như vậy, ezt là hàm sinh mũ cho dãy số z0, z1, z2, ..., zn, .... Bây giờ ta xét một số ví dụ cụ thể, ở đó hàm sinh mũ đã được áp dụng một cách thành công để giải quyết bài toán đếm. Ví dụ 2.10. Số xáo trộn tổng quát Dn. Giả sử X là một tập hữu hạn và X = {x1, x2, ..., xn}. Ta sẽ đồng nhất hoán vị (a1, a2, ..., an) của các phần tử của X với song ánh ϕ : X → X : xi 7→ ai. Khi đó phần tử xi ∈ X được gọi là điểm bất động của hoán vị ϕ trên X nếu ϕ(xi) = xi. Hoán vị ϕ của X mà không có điểm bất động nào được gọi là một xáo trộn của X. Số tất cả các xáo trộn của tập hữu hạn X lực lượng n được ký hiệu là Dn, gọi là số xáo trộn tổng quát. Bây giờ ta đi tính Dn theo n. Giải: Giả sử P ([n]) là tập tất cả các hoán vị của tập [n] và P (t) là hàm sinh mũ cho dãy P ([0]), P ([1]), ..., P ([n]), ... . Mỗi hoán vị của [n] có thể được phân tích thành tích của các chu trình độc lập, tức là nó có dạng (∗ ∗ · · · ∗)(∗ ∗ · · · ∗) · · · (∗ ∗ · · · ∗)(∗) · · · (∗), ở đây các chu trình (∗) tương ứng với các điểm bất động của hoán vị đó. Vì vậy, mỗi hoán vị ϕ của [n] có thể xem như là cặp (σ, τ ), ở đây σ là một hoán 50 vị không có điểm bất động trên K ⊆ [n] ( một xáo trộn ) và τ là một hoán vị đồng nhất trên K = [n] \K. Chẳng hạn, hoán vị (19573)(46)(2)(8)(10) trên {1, 2, 3, ..., 10} có thể xem là cặp (σ, τ ) với σ = (19573)(46) là một xáo trộn trên {1, 3, 4, 5, 6, 7, 9}, còn τ = (2)(8)(10) là hoán vị đồng nhất trên {2, 8, 10}. Ký hiệu I([n]) là tập các hoán vị đồng nhất trên [n], còn D([n]) là tập các xáo trộn trên [n]. Khi đó |I([n])| = 1 và |D([n])| = Dn cho mọi n = 0, 1, 2, .... Do đó hàm sinh mũ cho dãy {I([n])}∞n=0 và {D([n])}∞n=0 tương ứng là I(t) = 1 + t 1! + t2 2! + t3 3! + · · · = et, D(t) = D0 + D1 t 1! + D2 t2 2! + D3 t3 3! + · · · . Vì |P ([n])| = n! nên hàm sinh mũ cho dãy {P ([n])}∞n=0 là P (t) = 1 + 1! t 1! + 2! t2 2! + 3! t3 3! + · · · = 1 + t + t2 + t3 + · · · Mặt khác, như đã lập luận ở trên, ta có P ([n]) = DI([n]). Vì vậy P (t) = DI(t) = D(t).I(t), ở đây DI(t) là hàm sinh mũ cho dãy {DI([n])}∞n=0. Suy ra D(t) = P (t)(I(t))−1 = P (t)(et) −1 = (1 + t + t2 + t3 + · · · ) ( 1− 1 1! t + 1 2! t2 − 1 3! t3 + · · · ) = 1 + · · · ( 1 − 1 1! + 1 2! − 1 3! + · · ·+ (−1)n 1 n! ) tn + · · · Vì vậy, Dn = n! ( 1− 1 1! + 1 2! − 1 3! + · · ·+ (−1)n 1 n! ) . Xét hàm sinh mũ của dãy các tập {S([n])}∞n=0 : S(t) = |S(∅)|+ |S([1])| t 1! + |S([2])|t 2 2! + |S([3])|t 3 3! + · · · 51 Khi đó, nếu ta ký hiệu đạo hàm của hàm S(t) là S ′ (t) và tập các vật được đếm bởi S ′ (t) với giá [n] bằng S ′ ([n]), thì S ′ (t) = |S([1])|+ |S([2])| t 1! + |S([3])|t 2 2! + |S([4])|t 3 3! + · · · . Đẳng thức trên chứng tỏ rằng S ′ ([n]) = S([n + 1]) cho mọi n ≥ 0. Phần tử "thừa" n + 1 cho tập S ′ ([n]) có nhiều ưu việt mà ta có thể sử dụng để thiết lập các hệ thức mà S(t) cần phải thỏa mãn. Ta minh họa điều này và phương pháp sử dụng hàm sinh mũ cho bài toán đếm ở ví dụ dưới đây. Ví dụ 2.11. Hoán vị trên đường tròn. Có n vị trí trên một đường tròn. Mỗi cách sắp xếp n số của tập [n] = {1, 2, 3, ..., n} vào n vị trí đó được gọi là một hoán vị trên đường tròn của tập [n]. Hai hoán vị trên đường tròn của một tập [n] được coi là như nhau nếu cùng xuất phát từ vị trí chứa số 1 và đi theo chiều quay của kim đồng hồ ta lần lượt gặp các số tương ứng bằng nhau trong hai sắp xếp đó. Bây giờ ta đi tính số hoán vị trên đường tròn của tập [n] theo n. Ký hiệu tập các hoán vị trên đường tròn của tập [n] bằng C([n]). Giả sử C(t) là hàm sinh mũ cho dãy {C([n])}∞n=0 và C ′ (t) là đạo hàm của C(t). Khi đó, như ta đã có nhận xét ở trên đối với đạo hàm của hàm sinh mũ, các hoán vị trên đường tròn của tập [n + 1] được đếm bởi C ′ (t) với giá [n]. Mặt khác, mỗi hoán vị trên đường tròn của tập [n + 1] cũng có thể đồng nhất với một sắp xếp thành hàng ngang của tập [n] bằng cách "cắt" vị trí chứa số n + 1 ra khỏi đường tròn và "căng" các vị trí còn lại của sắp xếp ra "thành hàng ngang" với số đầu tiên là số sau n + 1 trên đường tròn theo chiều kim đồng hồ. Ví dụ, hoán vị trên đường tròn 32154 của tập [5] đươc đồng nhất với sắp xếp thành hàng ngang 4321 của tập [4]. Vì vậy, nếu ta ký hiệu P ([n]) là tập các sắp xếp thành hàng ngang của tập [n] và P (t) là hàm sinh mũ cho dãy 52 {P ([n])}∞n=0, thì C ′ (t) = P (t) với C(0) = 1(vì |C(∅)| = 1). Hiển nhiên là P ([n]) chính là tập các hoán vị của [n] và vì thế |P ([n])| = n!. Do đó, P (t) = ∞∑ n=0 n! tn n! = ∞∑ n=0 tn = 1 1− t . Vậy C ′ (t) = 1 1 − t với C(0) = 1. Suy ra C(t) = − ln(1 − t) + C0 với C0 là một hằng số. Vì C(0) = 1 và ln(1) = 0 nên ta suy ra C0 = 1 và ta nhận được C(t) = 1− ln(1− t) = 1 + ∞∑ n=1 tn n = 1 + ∞∑ n=1 (n − 1)! t n n! . Vậy, số các hoán vị trên đường tròn của tập [n] là |C([n])| = (n− 1)!. Trong phần tiếp theo, ta đi tìm hàm sinh mũ cho các số tổ hợp cơ bản và các số tổ hợp mới vừa tìm được trong Chương 1. Với mỗi n ∈ N, ta đặt Gn(t) = n∑ k=0 Un,kt k = n∑ k=0 Cknk n−ktk. Khi đó, Gn(1) = Gn = n∑ k=0 Cknk n−k. Ta có mệnh đề sau: Mệnh đề 2.2.1. Ta có etxe x = ∞∑ n=0 Gn(t) xn n! . 53 Chứng minh: Ta có : etxe x = ∞∑ k=0 tkxkekx k! = ∞∑ k=0 tk k! (xex)k = ∞∑ k=0 tk k! ( ∞∑ m=0 xm+1 m! )k = ∞∑ k=0 tk k! ( ∞∑ m=0 (m + 1)xm+1 (m + 1)! )k = ∞∑ k=0 tk k! ( ∞∑ i=1 i xi i! )k = ∞∑ k=0 tk k! ( ∞∑ n=0 ( ∑ (i1,i2,...,ik): kP j=1 ij=n ij≥1 i1 i1! · i2 i2! · · · ik ik! ) xn ) = ∞∑ k=0 tk k! ( ∞∑ n=0 n! ( ∑ (i1,i2,...,ik): kP j=1 ij=n ij≥1 i1 i1! · i2 i2! · · · ik ik! ) xn n! ) = ∞∑ n=0 n! ( n∑ k=0 1 k! ( ∑ (i1,i2,...,ik): kP j=1 ij=n ij≥1 i1 i1! · i2 i2! · · · ik ik! ) tk ) xn n! = ∞∑ n=0 ( n∑ k=0 n! k! ( ∑ (i1,i2,...,ik): kP j=1 ij=n ij≥1 i1 i1! · i2 i2! · · · ik ik! ) tk ) xn n! = ∞∑ n=0 ( n∑ k=0 Cknk n−ktk ) xn n! = ∞∑ n=0 Gn(t) xn n! . Hệ quả 2.2.1. Hàm sinh mũ của dãy số Gn là exe x . Chứng minh: Trong biểu thức của Mệnh đề 2.2.1, cho t = 1 ta được exe x = ∞∑ n=0 ( n∑ k=0 Cknk n−k ) xn n! = ∞∑ n=0 Gn xn n! . Vậy ta có điều cần chứng minh. Trong Mệnh đề 2.2.1, lấy x = 1 và t = 1 ta có hệ quả sau 54 Hệ quả 2.2.2. Ta có ee = ∞∑ n=0 1 n! n∑ k=0 Cknk n−k = ∞∑ n=0 n∑ k=0 kn−k k!(n− k)! . Mệnh đề 2.2.2. Với mỗi k ∈ N cố định thì ∞∑ n=0 Sn,k tn n! = 1 k! (et − 1)k . Chứng minh: + Với k = 0 ta có: S0,0 = 1, do đó đẳng thức đúng. + Với k ≥ 1. Ta chỉ cần chứng minh đẳng thức ∞∑ n=1 Sn,k tn n! = 1 k! (et − 1)k. Ta có: et = ∞∑ m=0 tm m! = 1 + ∞∑ m=1 tm m! ⇒ et − 1 = ∞∑ m=1 tm m! . Do đó (et − 1)k = ( ∞∑ m=1 tm m! )k = ∞∑ n=1 [ ∑ (i1,i2,...,ik): kP j=1 ij=n ij≥1 ( 1 i1! · 1 i2! · · · 1 ik! )] tn = ∞∑ n=1 k!Sn,k tn n! . Do đó ∞∑ n=0 Sn,k tn n! = 1 k! (et − 1)k. Vậy mệnh đề được chứng minh xong. Từ Mệnh đề 2.2.2, ta có hệ quả sau Hệ quả 2.2.3. Với mỗi k ∈ N cố định thì hàm sinh mũ cho dãy các số Stirling loại hai {Sn,k}∞n=0 là 1 k! (et − 1)k. Định nghĩa 2.2.2. (theo [5]) Với mỗi n ∈ N, ta đặt en(t) = n∑ k=0 Sn,kt k. Dãy đa thức {en(t)}∞n=0 được gọi là dãy đa thức mũ. 55 Mệnh đề 2.2.3. Ta có ∞∑ n=0 en(t) xn n! = et(e x −1) . Chứng minh: Ta có et(e x −1) = ∞∑ k=0 (ex − 1)k t k k! = ∞∑ k=0 ( ∞∑ m=1 xm m! )k tk k! = ∞∑ k=0 { ∞∑ n=1 [ ∑ (i1,i2,...,ik): kP j=1 ij=n ij≥1 ( 1 i1! · 1 i2! · · · 1 ik! )] xn } tk k! = ∞∑ k=0 [ ∞∑ n=1 k!Sn,k xn n! ]tk k! = ∞∑ k=0 k! [ ∞∑ n=1 Sn,k xn n! ] tk k! = ∞∑ k=0 [ ∞∑ n=1 Sn,k xn n! ] tk = 1 + ∞∑ n=1 ( n∑ k=1 Sn,kt k )xn n! = 1 + ∞∑ n=1 en(t) xn n! = ∞∑ n=0 en(t) xn n! . Nhận xét: Với mỗi t ∈ R cố định thì {en(t)}∞n=0 là dãy số thực. Do đó ta có hệ quả sau Hệ quả 2.2.4. Với mỗi t ∈ R cố định thì hàm sinh mũ của dãy số {en(t)}∞n=0 là et(e x −1). Mệnh đề 2.2.4. Hàm sinh mũ của dãy số Bell {Bn}∞n=0 là ee x −1. Chứng minh: Thay t = 1 vào đẳng thức et(e x −1) = ∞∑ n=0 en(t) xn n! = ∞∑ n=0 ( n∑ k=0 Sn,kt k )xn n! ta nhận được ee x −1 = ∞∑ n=0 ( n∑ k=0 Sn,k )xn n! = ∞∑ n=0 Bn xn n! . Vậy ta có điều phải chứng minh. 56 Trong Mệnh đề 2.2.4, cho x = 1 ta được Hệ quả 2.2.5. ee−1 = ∞∑ n=0 Bn n! . Mệnh đề sau đây cho ta một cách biểu diễn của số Bell Bn. Mệnh đề 2.2.5. (theo [8, 2]) Ta có Bn = 1 e ∞∑ k=0 kn k! (Công thức Dobinski ). Chứng minh: Ta có ee x −1 = 1 e ee x = 1 e ∞∑ k=0 ekx k! = 1 e ∞∑ k=0 1 k! ( ∞∑ n=0 knxn n! ) = 1 e ∞∑ k=0 kn k! ( ∞∑ n=0 xn n! ) = 1 e ∞∑ n=0 ( ∞∑ k=0 kn k! ) xn n! . Mặt khác, theo Mệnh đề 2.2.4 thì ee x −1 = ∞∑ n=0 Bn xn n! . Do đó ta có Bn = 1 e ∞∑ k=0 kn k! . Công thức Dobinski đã được chứng minh trong một số tài liệu tham khảo. Tuy nhiên, ở đây ta đã chứng minh bằng một phương pháp hoàn toàn khác. Trong phần tiếp theo, ta sẽ tìm hàm sinh mũ cho các dãy số {Pn}∞n=0, {Qn}∞n=0 và tìm công thức tường minh cho Pn, Qn. Đặt Pn(t) = n∑ k=0 En,kt k, Qn(t) = n∑ k=0 On,kt k. Khi đó Pn(1) = Pn và Qn(1) = Qn. Ta có mệnh đề sau : 57 Mệnh đề 2.2.6. Ta có a) et(chx−1) = ∞∑ n=0 Pn(t) xn n! , b) et.shx = ∞∑ n=0 Qn(t) xn n! . Chứng minh: Ta đã biết Sn,k = n! k! ∑ (i1,i2,...,ik): kP j=1 ij=n ij≥1 ( 1 i1! · 1 i2! · · · 1 ik! ) . Suy ra En,k = n! k! ∑ (i1,i2,...,ik): kP j=1 ij=n ij≥1;ij :chẵn ( 1 i1! · 1 i2! · · · 1 ik! ) và On,k = n! k! ∑ (i1,i2,...,ik): kP j=1 ij=n ij≥1;ij :lẻ ( 1 i1! · 1 i2! · · · 1 ik! ) . a) Ta có chx− 1 = e x + e−x 2 − 1 = e x − 1 2 + e−x − 1 2 = 1 2   ∞∑ p=1 xp p! + ∞∑ q=1 (−1)qx q q!   = ∞∑ m=1 x2m (2m)! . 58 Suy ra et(chx−1) = ∞∑ k=0 tk k! (chx− 1)k = ∞∑ k=0 tk k! ( ∞∑ m=1 x2m (2m)! )k = ∞∑ k=0 tk k! [ ∞∑ n=1 ( ∑ (i1,i2,...,ik): kP j=1 ij=n ij≥1;ij :chẵn ( 1 i1! · 1 i2! · · · 1 ik! )) xn ] = 1 + ∞∑ k=1 tk k! [ ∞∑ n=1 k!En,k xn n! ] = 1 + ∞∑ n=1 [ n∑ k=1 En,kt k ] xn n! = ∞∑ n=0 ( n∑ k=0 En,kt k ) xn n! = ∞∑ n=0 Pn(t) xn n! b) Ta có shx = ex − e−x 2 = 1 2   ∞∑ p=0 xp p! − ∞∑ q=0 (−1)qx q q!   = ∞∑ m=0 x2m+1 (2m + 1)! . Suy ra et.shx = ∞∑ k=0 tk k! (shx)k = 1 + ∞∑ k=1 tk k! ( ∞∑ m=0 x2m+1 (2m + 1)! )k = 1 + ∞∑ k=1 tk k! [ ∞∑ n=1 ( ∑ (i1,i2,...,ik): kP j=1 ij=n ij≥1;ij :lẻ ( 1 i1! · 1 i2! · · · 1 ik! )) xn ] = 1 + ∞∑ k=1 tk k! [ ∞∑ n=1 k!On,k xn n! ] = 1 + ∞∑ n=1 [ n∑ k=1 On,kt k ] xn n! = ∞∑ n=0 ( n∑ k=0 On,kt k ) xn n! = ∞∑ n=0 Qn(t) xn n! . Từ mệnh đề trên ta có hệ quả sau: 59 Hệ quả 2.2.6. Hàm sinh mũ của các dãy số {Pn}∞n=0 và {Qn}∞n=0 lần lượt là echx−1 và eshx. Chứng minh: Thay t = 1 vào đẳng thức a) và b) của Mệnh đề 2.2.6 ta được echx−1 = ∞∑ n=0 Pn(1) xn n! = ∞∑ n=0 Pn xn n! . eshx = ∞∑ n=0 Qn(1) xn n! = ∞∑ n=0 Qn xn n! . Do đó ta có điều cần chứng minh. Mệnh đề 2.2.7. Ta có (i) Pn(t) = e −t ∞∑ k=0 tk 2kk! k∑ j=0 Cj k (k − 2j)n, (2.4) (ii) Qn(t) = ∞∑ k=0 tk 2kk! k∑ j=0 (−1)jCj k (k − 2j)n. (2.5) Chứng minh: (i). Ta có : etchx = ∞∑ k=0 tk 2kk! ( ex + e−x )k = ∞∑ k=0 tk 2kk! k∑ j=0 C j ke −jxe(k−j)x = ∞∑ k=0 tk 2kk! k∑ j=0 Cj k e(k−2j)x = ∞∑ k=0 tk 2kk! k∑ j=0 Cj k ∞∑ n=0 (k − 2j)nx n n! = ∞∑ n=0   ∞∑ k=0 tk 2kk! k∑ j=0 Cj k (k − 2j)n   xn n! . Suy ra et(chx−1) = e−t ∞∑ n=0   ∞∑ k=0 tk 2kk! k∑ j=0 C j k(k − 2j)n   xn n! . Mặt khác et(chx−1) = ∞∑ n=0 Pn(t) xn n! (Mệnh đề 2.2.6.a). 60 Do đó ta có Pn(t) = e −t ∞∑ k=0 tk 2kk! k∑ j=0 Cj k (k − 2j)n. (ii) Ta có et.shx = ∞∑ k=0 tk 2kk! ( ex − e−x)k = ∞∑ k=0 tk 2kk!   k∑ j=0 (−1)jCj k e−jxe(k−j)x   = ∞∑ k=0 tk 2kk!   k∑ j=0 (−1)jCj k e(k−2j)x   = ∞∑ k=0 tk 2kk!   k∑ j=0 (−1)jCj k ( ∞∑ n=0 (k − 2j)nx n n! ) = ∞∑ n=0   ∞∑ k=0 tk 2kk!   k∑ j=0 (−1)jCjk(k − 2j)n     xn n! . Mặt khác, et.shx = ∞∑ n=0 Qn(t) xn n! (Mệnh đề 2.2.6.b). Do đó Qn(t) = ∞∑ k=0 tk 2kk! k∑ j=0 (−1)jCj k (k − 2j)n. Nhận xét: Theo một công thức đã biết: n∑ k=0 (−1)k(k + a)mCkn = 0, m = 0, . . . , n− 1; ( [6] tr 609) thì ta thấy rằng Qn(t) = ∞∑ k=n tk 2kk! k∑ j=0 (−1)jCjk(k − 2j)n . (2.6) Hệ quả sau đây cho ta công thức tường minh của Pn và Qn. Hệ quả 2.2.7. Ta có (i) Pn = 1 e ∞∑ k=0 1 2kk! k∑ j=0 Cj k (k − 2j)n, (ii) Qn = ∞∑ k=0 1 2kk! k∑ j=0 (−1)jCj k (k − 2j)n. Chứng minh: Thay t = 1 vào trong các đẳng thức (i) và (ii) của Mệnh đề 2.2.7 ta được điều phải chứng minh. 61 Chú ý: Nếu thay t = 1 vào đẳng thức (2.6) ta có Qn = ∞∑ k=n 1 2kk! k∑ j=0 (−1)jCj k (k − 2j)n. ở trang 18, ta đã chứng minh được công thức Bn = n∑ k=0 CknPkQn−k. Bây giờ ta chứng minh lại công thức này bằng phương pháp khác, cụ thể là dựa vào các kết quả về hàm sinh đã có ở trên. Ta có ex − 1 = e x − e−x 2 + ex + e−x 2 − 1 = shx + chx− 1. Do đó et(e x −1) = et(chx−1).etshx. Ta có et(chx−1).etshx = ( ∞∑ n=0 Pn(t) xn n! )( ∞∑ n=0 Qn(t) xn n! ) = ∞∑ n=0 ( n∑ k=0 CknPk(t)Qn−k(t) ) xn n! . Mặt khác, et(e x −1) = ∞∑ n=0 ( n∑ k=0 Sn,kt k ) xn n! (Mệnh đề 2.2.3). Suy ra n∑ k=0 Sn,kt k = n∑ k=0 CknPk(t)Qn−k(t). Thay t = 1 vào đẳng thức này ta được Bn = n∑ k=0 Sn,k = n∑ k=0 CknPkQn−k. 62 Với mỗi n ∈ N, đặt Ln(t) = n∑ k=0 Ln,kt k = n∑ k=0 n! k! Ck−1n−1t k và Ln = n∑ k=0 Ln,k. Vậy Ln là số tất cả các phân hoạch tập n phần tử thành các tập con không rỗng và trong mỗi tập con ta sắp xếp thứ tự các phần tử. Ta có mệnh đề sau: Mệnh đề 2.2.8. Ta có: e tx 1− x = ∞∑ n=0 ( n∑ k=0 n! k! Ck−1n−1t k ) xn n! . Chứng minh: Vì hệ số của xn trong khai triển ( ∞∑ m=1 xm )k chính là số nghiệm nguyên dương của phương trình x1 + x2 + · · · + xk = n, số nghiệm đó là Ck−1n−1. Do đó ta có e tx 1− x = ∞∑ k=0 tk k! ( ∞∑ m=1 xm )k = ∞∑ k=0 tk k! ( ∞∑ n=0 Ck−1n−1x n ) = ∞∑ k=0 tk k! ( ∞∑ n=0 n!Ck−1n−1 xn n! ) = ∞∑ n=0 n! ( ∞∑ k=0 1 k! Ck−1n−1t k ) xn n! = ∞∑ n=0 ( n∑ k=0 n! k! Ck−1n−1t k ) xn n! . Hệ quả 2.2.8. Hàm sinh mũ của dãy số Ln là e x 1− x . Chứng minh: Trong Mệnh đề 2.2.8, cho t = 1 ta được e x 1− x = ∞∑ n=0 ( n∑ k=0 n! k! Ck−1n−1 ) xn n! = ∞∑ n=0 Ln xn n! . Do đó ta có điều cần chứng minh. 63 Chương 3 Một số phương pháp và kỹ thuật đếm cơ bản khác Trong chương này ta sẽ đề cập đến hai phương pháp đếm cơ bản khác. Đó là phương pháp đếm bằng nguyên lý bao hàm và loại trừ và phương pháp đếm bằng công thức ngược. Các phương pháp đếm này cũng tỏ ra hữu hiệu trong nhiều bài toán đếm khác nhau. 3.1 Phương pháp đếm bằng nguyên lý bao hàm và loại trừ. Phương pháp đếm bằng nguyên lý bao hàm và loại trừ là một phương pháp rất cơ bản để giải quyết bài toán đếm. Trước tiên ta chứng minh công thức kinh điển của nguyên lý bao hàm và loại trừ. Định lý 3.1.1. (theo [3, 3.1]) (Nguyên lý bao hàm và loại trừ dạng kinh điển). 64 Giả sử A1, A2, ..., An là các tập hữu hạn bất kỳ. Khi đó |A1 ∪A2 ∪ ... ∪An| = n∑ i=1 |Ai| − ∑ 1≤i<j≤n |Ai ∩Aj| + ∑ 1≤i<j<k≤n |Ai ∩Aj ∩ Ak|+ · · · − · · · + (−1)n+1|A1 ∩A2 ∩ ... ∩An|. (∗) Chứng minh: Ta chứng minh bằng quy nạp theo n. +) Với n = 1 hiển nhiên đẳng thức (*) đúng. +) Với n = 2 ta cũng dễ dàng chứng minh được (*) cũng đúng. +) Ta giả sử (*) đúng cho n ≥ 2 tập hợp tùy ý. Tức là |A1 ∪ A2 ∪ ...∪ An| = n∑ i=1 |Ai| − ∑ 1≤i<j≤n |Ai ∩ Aj| + ∑ 1≤i<j<k≤n |Ai ∩ Aj ∩Ak|+ · · · − · · ·+ (−1)n+1|A1 ∩A2 ∩ ... ∩An| Bây giờ xét n + 1 tập hợp tùy ý A1, A2, ..., An, An+1. Lưu ý rằng (A1 ∪A2 ∪ ... ∪An) ∩An+1 = n⋃ i=1 (Ai ∩An+1) (∗∗) Cho nên ta có |(A1 ∪A2 ∪ ...∪ An) ∩ An+1| = | n⋃ i=1 (Ai ∩An+1)|. Sử dụng (*) cho vế phải của (**), ta thu được (A1 ∪ A2 ∪ ...∪ An) ∩An+1| = n∑ i=1 |Ai ∩An+1| − ∑ 1≤i<j≤n |Ai ∩Aj ∩An+1| + ∑ 1≤i<j<≤n |Ai ∩ Aj ∩Ak ∩ An+1| − · · · + · · ·+ (−1)n+1|A1 ∩A2 ∩ ... ∩An ∩An+1| 65 Đặt A = A1 ∪ A2 ∪ ... ∪ An và B = An+1 và áp dụng đẳng thức |A ∪ B| = |A|+ |B| − |A∩B| ( trường hợp n = 2 ) ta thu được điều cần chứng minh. Sau đây ta xét một số ví dụ cụ thể trong việc áp dụng nguyên lý bao hàm và loại trừ trong việc giải một số bài toán tổ hợp. Ví dụ 3.1. Có bao nhiêu số nguyên dương từ 1 đến 1000 mà không chia hết cho 2, không chia hết cho 3 và cũng không chia hết cho 7 ? Giải : Ta ký hiệu A = {1, 2, ..., 1000}, A2 = {a ∈ A : a chia hết cho 2}, A3 = {a ∈ A : a chia hết cho 3}, A7 = {a ∈ A : a chia hết cho 7}. Khi đó A \ (A2 ∪ A3 ∪ A7) là tập tất cả các số từ 1 đến 1000 mà không chia hết cho 2, không chia hết cho 3 và cũng không chia hết cho 7. Theo nguyên lý bao hàm và loại trừ, ta có |A2 ∪A3 ∪ A7| = |A2|+ |A3|+ |A7| − |A2 ∩A3| − |A2 ∩A7| − |A3 ∩A7|+ |A2 ∩A3 ∩A7|. Nếu ký hiệu [r] là phần nguyên của số thực r thì ta có : |A2| = [ 1000 2 ] = [500] = 500; A3| = [ 1000 3 ] = [333, 3...] = 333 ; |A7| = [ 1000 7 ] = [142, 8] = 142; |A2 ∩A3| = [ 1000 2 × 3 ] = [166, 6] = 166 ; |A2 ∩A7| = [ 1000 2× 7 ] = [71, 4] = 71; |A3 ∩A7| = [ 1000 3× 7 ] = [47, 6] = 47; |A2 ∩A3 ∩A7| = [ 1000 2× 3 × 7 ] = [23, 8] = 23. Do đó, |A2 ∪A3 ∪A7| = 500 + 333 + 142 − 166 − 71 − 47 + 23 = 714 66 Vì (A2 ∪A3 ∪A7) ⊆ A nên |A \ (A2 ∪A3 ∪A7)| = |A| − |A2 ∪A3 ∪ A7| = 1000 − 714 = 286. Vậy có tất cả 286 số thỏa mãn yêu cầu bài toán. Ví dụ 3.2. ϕ - hàm Euler. Hai số nguyên được gọi là nguyên tố cùng nhau nếu chúng không có ước số chung khác 1. Với mỗi số nguyên dương n, ký hiệu ϕ(n) là số các số nguyên dương nhỏ hơn hoặc bằng n mà nguyên tố cùng nhau với n. Hàm ϕ(n) được gọi là ϕ-hàm Euler. Bài toán đặt ra là tính giá trị của ϕ(n) theo n. Giải : Giả sử n = pa11 p a2 2 ...p ak k là phân tích chính tắc của n thành tích của các thừa số nguyên tố, ở đây a1, a2, ..., ak là các số nguyên dương. Ta cũng giả sử A = {1, 2, ..., n}, Api = {a ∈ A : a chia hết cho pi}, i = 1, 2, ..., k. Khi đó |Api| = n pi , |Api ∩ Apj | = n pipj (i 6= j), .... áp dụng nguyên lý bao hàm và loại trừ, ta được ϕ(n) = |A \ (Ap1 ∪Ap2 . . . ∪Apk)| = |A| − |Ap1 ∪Ap2 . . . ∪Apk | = n− ( n p1 + n p2 + · · ·+ n pk − n p1p2 − · · · − n pk−1pk + · · · + (−1)k+1 n p1p2 . . . pk ) = n ( 1− 1 p1 )( 1− 1 p2 ) · · · ( 1− 1 pk ) . Chẳng hạn, theo công thức trên ta có : ϕ(15) = 15 ( 1− 1 3 )( 1− 1 5 ) = 15 · 2 3 · 4 5 = 8 ϕ(18) = 18 ( 1− 1 2 )( 1− 1 3 ) = 18 · 1 2 · 2 3 = 6. 67 Ví dụ 3.3. Số xáo trộn tổng quát Dn. Trong phần trước, ta đã tính số xáo trộn tổng quát Dn bằng phương pháp hàm sinh. Bây giờ ta tính lại Dn bằng phương pháp sử dụng nguyên lý bao hàm và loại trừ. Giả sử A là tập tất cả các hoán vị của tập X = {x1, x2, ..., xn}, Ai = {a ∈ A : xi là điểm bất động của a}. Khi đó A \ (A1 ∪ A2 ∪ . . . ∪ An) là tập tất cả các hoán vị của X mà không có một điểm bất động nào. Theo nguyên lý bao hàm và loại trừ, ta có: |A1∪A2∪ ...∪An| = n∑ i=1 |Ai| − ∑ 1≤i<j≤n |Ai∩Aj|+ · · ·+(−1)n+1|A1∩A2∩ ...∩An|. Ta lại có |A| = n!, |Ai| = (n− 1)!, |Ai1 ∩ Ai2 ∩ . . . ∩ Aik| = (n− k)! cho mọi k = 2, 3, ..., n. Suy ra Dn = |A \ (A1 ∪A2 ∪ . . . ∪ An)| = |A| − |A1 ∪A2 ∪ . . . ∪ An| = n! − [ C1n(n− 1)! − C2n(n− 2)! + · · ·+ (−1)n+1Cnn(n− n)! ] = n! − n! 1! + n! 2! − n! 3! + · · ·+ (−1)nn! n! = n! [ 1 − 1 1! + 1 2! − 1 3! + · · ·+ (−1)n 1 n! ] . Ví dụ 3.4. Có n lá thư và n phong bì ghi sẵn địa chỉ. Bỏ ngẫu nhiên các lá thư vào các phong bì sao cho mỗi phong bì chỉ chứa một lá thư. Hỏi xác suất để xảy ra mọi lá thư đều cho vào phong bì sai địa chỉ của nó bằng bao nhiêu ? Giải: Dễ thấy rằng số các cách xếp thư vào phong bì sao cho mọi lá thư đều cho vào phong bì sai địa chỉ của nó bằng Dn, còn số tất cả các cách xếp thư vào phong bì bằng n!. Do đó, xác suất p cần tìm bằng 68 p = Dn n! = 1− 1 1! + 1 2! − 1 3! + · · ·+ (−1)n 1 n! . Người ta chứng minh được rằng p = Dn n! n→∞−−−→ 1 e ∼= 0, 368 . Ví dụ 3.5. Tính số Stirling loại hai Sn,k qua n và k. Giải: Giả sử N và K là các tập hữu hạn với |N | = n và |K| = k. Khi đó, như ta đã tính trong Chương 1, Mục 1.3.4, số tất cả các hàm toàn ánh từ N đến K bằng k!Sn,k. Bây giờ ta tính số các hàm này bằng một cách khác. Giả sử A là tập tất cả các hàm từ N đến K = {m1, m2, ..., mk}; Ai = {f ∈ A : mi /∈ f(N)}, i = 1, 2, ..., k. Khi đó A \ (A1 ∪ A2 ∪ . . . ∪ Ak) là tập tất cả các hàm toàn ánh từ N đến K. Ta có |A| = kn, |Ai| = (k − 1)n, i = 1, 2, ..., k, |Ai1 ∩ Ai2 ∩ . . . ∩ Aij | = (k − j)n, j = 2, 3, ..., k. Do đó, theo nguyên lý bao hàm và loại trừ, số các hàm toàn ánh từ N đến K bằng |A \ (A1 ∪A2 ∪ . . . ∪Ak)| = |A| − |(A1 ∪A2 ∪ . . . ∪Ak)| = |A| − ( k∑ i=1 |Ai| − ∑ 1≤i<j≤k |Ai ∩Aj|+ · · · + (−1)k+1|A1 ∩A2 ∩ ... ∩Ak| ) = kn − C1k(k − 1)n + C2k(k − 2)n − · · · + (−1)k−1Ck−1k 1n + (−1)kCkk0n = k∑ i=0 (−1)iC ik(k − i)n (Đặtj = k − i) = k∑ j=0 (−1)k−jCk−j k jn = k∑ j=0 (−1)k−jCj k jn . 69 Vì vậy, k!Sn,k = k∑ j=0 (−1)k−jCj k jn. hay Sn,k = 1 k! [ k∑ j=0 (−1)k−jCj k jn ] . 3.2 Phương pháp đếm bằng công thức ngược Trong Chương 1 ta đã chứng minh được rằng mn = m∑ k=0 Ckmk!Sn,k = n∑ k=0 Ckmk!Sn,k. Các đồng nhất thức này có thể sử dụng để tính Sn,k, nhưng việc tính toán rất phức tạp và khó khăn. Trong mục này, ta chỉ ra cách nghịch đảo các đồng nhất thức như thế. Chẳng hạn, bằng cách này ta có thể biểu thị được các số Stirling loại hai qua các lũy thừa bậc n. Ta định nghĩa dãy đa thức là một dãy có thứ tự p0(x), p1(x), p2(x)..., pn(x), ... các đa thức pn(x), n = 0, 1, 2, ..., mà ta đơn giản ký hiệu là {pn(x)}∞n=0, thỏa mãn các điều kiện sau đây: (i) Các hệ số của pn(x) n = 0, 1, 2, ..., đều phải là số thực; (ii) p0(x) là một hằng số khác 0; (iii) Bậc của pn(x), ký hiệu là deg(pn(x)), bằng n. Nếu{qn(x)}∞n=0 là một dãy đa thức khác, thì (q0(x), q1(x), q2(x)..., qn(x)) lập thành một cơ sở cho không gian véc tơ Cn+1[x] tất cả các đa thức trên trường số phức C có bậc nhỏ hơn n + 1. Do đó, với mỗi pn(x), n = 0, 1, 2, ... 70 của dãy đa thức {pn(x)}∞n=0, tồn tại các số an,0, an,1, ..., an,n sao cho pn(x) = n∑ k=0 an,kqk(x). Tương tự, tồn tại các số bn,0, bn,1, ..., bn,n sao cho qn(x) = n∑ k=0 bn,kpk(x), n = 0, 1, 2, ... Các số an,k và bn,k được gọi là các hệ số nối. Biểu diễn của m + 1 đa thức pn(x) đầu tiên qua qk(x) có thể viết dưới dạng ma trận như sau :  p0(x) p1(x) ... pm(x)   =   a0,0 0 · · · 0 a1,0 a1,1 · · · 0 ... ... ... ... am,0 am,1 · · · am,m     q0(x) q1(x) ... qm (x)   hay đơn giản hơn P = AQ, ở đây P và Q là các vectơ cột (pk(x)) m 0 và qk(x)) m 0 , còn A = (ai,j)m+1×m+1 Tương tự, biểu diễn của m + 1 đa thức qn(x) đầu tiên qua pn(x) có thể viết dưới dạng ma trận Q = BP ở đây P,Q là các ma trận cột như trên còn B =   b0,0 0 . . . 0 b1,0 b1,1 . . . 0 ... ... ... ... bm,0 bm,1 . . . bm,m   Từ P = AQ và Q = BP suy ra P = AQ = (AB)P và Q = BP = (BA)Q. Do sự độc lập tuyến tính của các đa thức {pk(x)}mk=0 và {qk(x)}mk=0 suy ra 71 AB = BA = E với E là ma trận đơn vị. Vậy A và B là các ma trận nghịch đảo của nhau. Ta có định lý sau: Định lý 3.2.1. (theo [3, 3.2]) (Công thức ngược) Giả sử A = (ai,j) và B = (bi,j) là các ma trận nhận được từ hai dãy đa thức {pn(x)}∞n=0 và {qn(x)}∞n=0 như nói tới ở trên. Ta cũng giả sử rằng dãy các số {un}∞n=0 và {vn}∞n=0 liên hệ với nhau bằng đẳng thức : un = n∑ k=0 an,kvk cho mọi n = 0, 1, 2, ... Khi đó, vn = n∑ k=0 bn,kuk cho mọi n = 0, 1, 2, ... Chứng minh: Từ un = n∑ k=0 an,kvk cho mọi n = 0, 1, 2, ... ta có   u0 u1 ... un   = A   v0 v1 ... vn   Do đó,   v0 v1 ... vn   = A−1   u0 u1 ... un   = B   u0 u1 ... un   vì A và B là các ma trận nghịch đảo của nhau. Suy ra vn = n∑ k=0 bn,kuk cho mọi n = 0, 1, 2, ... 72 Công thức ngược ở định lý trên có thể áp dụng vào các bài toán đếm như sau. Giả sử {S([n])}∞n=0 là một dãy các tập các vật cần đếm, còn {T ([n])}∞n=0 là một dãy các tập các vật cần đếm khác. Ta cũng giả sử rằng un = |S([n])|, vn = |T ([n])| và các dãy số {un}∞n=0 và {vn}∞n=0 thỏa mãn các điều kiện của Định lý 3.2.1. Khi đó, Định lý này khẳng định rằng nếu ta đã tìm được công thức để tính số các vật trong các tập của một dãy, thì ta cũng tìm được công thức để tính số các vật trong các tập của dãy kia. Ta xem một số trường hợp cụ thể thường gặp của Định lý 3.2.1. 3.2.1 Công thức nghịch đảo nhị thức Dễ thấy rằng các dãy {xn}∞n=0 và {(x− 1)n}∞n=0 là các dãy đa thức. Theo công thức nhị thức ta có xn = ((x− 1) + 1)n = n∑ k=0 Ckn(x− 1)k, (x− 1)n = n∑ k=0 (−1)n−kCknxk. Do đó các ma trận A và B nhận được từ hai dãy đa thức trên là A =   C00 0 . . . 0 C01 C 1 1 . . . 0 ... ... ... ... C0n C 1 n . . . C n n   B =   (−1)0C00 0 . . . 0 (−1)1C01 (−1)0C11 . . . 0 ... ... ... ... (−1)nC0n (−1)n−1C1n . . . (−1)0Cnn   Các ma trận này được gọi là các ma trận của công thức nghịch đảo nhị thức. Theo Định lý 3.2.1, nếu hai dãy số {un}∞n=0 và {vn}∞n=0 liên hệ với nhau bằng 73 đẳng thức un = n∑ k=0 Cknvk thì vn = n∑ k=0 (−1)n−kCknuk. Ví dụ 3.6. Tính số phân hoạch Sn,m của tập [n] = {1, 2, ..., n} thành m tập con không rỗng theo n và m. Giải: Nếu Sn([m]) là tập tất cả các hàm từ tập [n] vào tập [m], còn Tn([m]) là tập tất cả các hàm toàn ánh từ [n] lên [m], thì |Sn([m])| = um = mn, |Tn([m])| = vm = m!Sn,m. Hơn thế nữa, ta có hệ thức sau đây đã được chứng minh ở Chương 1 giữa un và vn : mn = m∑ k=0 Ckmk!Sn,k. áp dụng công thức nghịch đảo nhị thức ở trên ta được m!Sn,m = m∑ k=0 (−1)m−kCkmkn. Do đó Sn,m = 1 m! m∑ k=0 (−1)m−kCkmkn. 3.2.2 Công thức nghịch đảo Stirling Giả sử (x)n = x(x − 1)(x − 2)...(x− n + 1). Ta quy uớc (x)0 = 1. Xét các dãy {xn}∞n=0 và {(x)n}∞n=0. Rõ ràng các dãy này là các dãy đa thức. Ta đã chứng minh trong Chương 1 rằng xn = n∑ k=0 Sn,k(x)k. Mặt khác, theo Định nghĩa 1.5.1 ta có (x)n = n∑ k=0 sn,kx k 74 là biểu diễn của (x)n theo xk. Gọi A và B là các ma trận nhận được từ hai dãy đa thức trên. Khi đó A =   S0,0 0 . . . 0 S1,0 S1,1 . . . 0 ... ... ... ... Sn,0 Sn,1 . . . Sn,n   B =   s0,0 0 . . . 0 s1,0 s1,1 . . . 0 ... ... ... ... sn,0 sn,1 . . . sn,n   Các ma trận A và B ở trên được gọi là các ma trận của công thức nghịch đảo Stirling. Vì AB = E nên ta có đồng nhất thức n∑ k=0 sl,kSk,j = δl,j ở đây δl,j là ký hiệu Kronecker. Tức là δl,j =   0 nếu j 6= l 1 nếu j = l Theo Định lý 3.2.1, nếu hai dãy số {un}∞n=0 và {vn}∞n=0 liên hệ với nhau bằng đẳng thức: un = n∑ k=0 Sn,kvk, thì vn = n∑ k=0 sn,kuk. 75 Chương 4 Dãy nhị thức 4.1 Khái niệm về dãy nhị thức Định nghĩa 4.1.1. (theo [1, 1]) Một dãy các đa thức một biến thực Pn(t) với deg(Pn(t)) ≤ n, n = 0, 1, 2, ... gọi là dãy nhị thức nếu: (i) P0(t) = 1, t ∈ R (ii) Pn(u + t) = n∑ k=0 CknPk(u)Pn−k(t), n = 1, 2, ..., t, u ∈ R. Chú ý: Định nghĩa về dãy nhị thức xuất hiện đầu tiên trong các tài liệu về lý thuyết tổ hợp [5], [8]. Trong các định nghĩa hiện hành, người ta giả thiết deg(Pn(t)) = n, n = 1, 2, ... thay vì deg(Pn(t)) ≤ n, n = 1, 2, .... Sự mở rộng ở đây là có ý nghĩa về mặt ứng dụng. Ví dụ 4.1. Dãy các đa thức Pn(t) với P0(t) = 1, Pn(t) = tn, n = 1, 2, ... thỏa mãn điều kiện (i) và (ii) trong định nghĩa nên Pn(t), n = 0, 1, 2, ... là dãy nhị thức. 4.2 Biểu diễn dãy nhị thức Dễ dàng kiểm tra tính đúng đắn của mệnh đề sau bằng quy nạp toán học. 76 Mệnh đề 4.2.1. (theo [1, 2]) Giả sử Pn(t), n = 1, 2, ... là một dãy nhị thức. Khi đó, Pn(0) = 0, n = 1, 2, ... Từ mệnh đề trên, ta suy ra tồn tại giới hạn lim t→0 Pn(t) t = an, n = 1, 2, .... Định lý 4.2.1. (theo [1, 2]) Dãy các đa thức Pn(t), n = 0, 1, 2, ... là dãy nhị thức khi và chỉ khi tồn tại dãy số thực ak, k = 1, 2, ... sao cho : (a) P0(t) = 1, t ∈ R (b) Pn(t) = n∑ k=1 akC k n t∫ 0 Pn−k(u)du, n = 1, 2, ..., t ∈ R. Chứng minh: Giả sử Pn(t), n = 0, 1, 2, ... là dãy nhị thức. Ta cần chứng minh rằng (b) thỏa mãn. Đặt ak = lim t→0 Pk(t) t , k = 1, 2, .... Ta có : Pn(t + u)− Pn(u) = n∑ k=0 CknPk(t)Pn−k(u)− Pn(u) = n∑ k=1 CknPk(t)Pn−k(u). Từ đó : P ′ n(u) = lim t→0 Pn(t + u)− Pn(u) t = n∑ k=1 akC k nPn−k(u). Vậy Pn(t) = n∑ k=1 akC k n t∫ 0 Pn−k(u)du, n = 1, 2, ..., t ∈ R. Ngược lại giả sử tồn tại dãy số ak, k = 1, 2, ... sao cho các điều kiện (a), (b) thỏa mãn. Ta cần chứng minh rằng (ii) thỏa mãn. Ta chứng minh bằng quy nạp toán học. + Với n = 1 thì P1(t) = a1 t∫ 0 P0(u)du = a1t. Do đó : P1(t + u) = a1(t + u) = a1t + a1u = 1∑ k=0 Ck1Pk(t)Pn−k(u). 77 + Giả sử rằng Pm(t + u) = m∑ k=0 CkmPk(t)Pm−k(u) với 1 ≤ m ≤ n. Khi đó Pn+1(t + u) = n+1∑ k=1 akC k n+1 t+u∫ 0 Pn+1−k(x)dx = n+1∑ k=1 akC k n+1 t∫ 0 Pn+1−k(x)dx + n+1∑ k=1 akC k n+1 t+u∫ t Pn+1−k(x)dx = Pn+1(t) + n+1∑ k=1 akC k n+1 u∫ 0 Pn+1−k(x + t)dx = Pn+1(t) + n+1∑ k=1 akC k n+1 n+1−k∑ j=0 Cj n+1−kPj(t) ∫ u 0 Pn+1−k−j(x)dx = Pn+1(t) + n∑ j=0 Pj(t) n+1−j∑ k=1 akC k n+1C j n+1−k ∫ u 0 Pn+1−k−j(x)dx = Pn+1(t) + n+1∑ k=1 akC k n+1 ∫ u 0 Pn+1−k(x)dx + n∑ j=1 Pj(t) n+1−j∑ k=1 akC k n+1C j n+1−k ∫ u 0 Pn+1−k−j(x)dx = Pn+1(t) + Pn+1(u) + n∑ j=1 Pj(t) n+1−j∑ k=1 akC j n+1C k n+1−j ∫ u 0 Pn+1−k−j(x)dx = Pn+1(t) + Pn+1(u) + n∑ j=1 C j n+1Pj(t) n+1−j∑ k=1 akC k n+1−j ∫ u 0 Pn+1−k−j(x)dx = Pn+1(t) + Pn+1(u) + n∑ j=1 Cjn+1Pj(t)Pn+1−j(u) = n+1∑ j=0 C j n+1Pj(t)Pn+1−j(u). Việc kiểm tra tính duy nhất của Pn(t) hay an khi cho trước dãy còn lại là đơn giản. Như vậy ta thấy rằng có tương ứng một-một giữa dãy nhị thức với dãy số xác định bởi : ak = lim t→0 Pk(t) t , k = 1, 2, .... 78 Tiếp theo ta nêu lên biểu diễn tường minh Pn(t) theo dãy ak đã cho qua định lý sau. Định lý 4.2.2. (theo [1, 2]) Dãy đa thức Pn(t), n = 0, 1, 2, ... là dãy nhị thức khi và chỉ khi tồn tại dãy số thực ak, k = 1, 2, ... sao cho : (α) P0(t) = 1 (β) Pn(t) = n! n∑ k=1 ( ∑ (i1,i2,...,ik): kP j=1 ij=n ij≥1 ai1 i1! ·ai2 i2! · · · aik ik! ) tk k! , n = 1, 2, ... Chứng minh: Giả sử Pn(t) là dãy nhị thức. Ta sẽ chứng minh bằng quy nạp toán học rằng (β) đúng. Việc kiểm tra trường hợp n = 1 là đơn giản . Giả sử với k ≤ n, ta đã có Pk(t) = k! k∑ j=1 ( ∑ (i1,i2,...,ij): jP m=1 im=k im≥1 ai1 i1! ·ai2 i2! · · · aij ij ! ) tj j! , n = 1, 2, ... Khi đó, theo Định lý 4.2.1 ta có : Pn+1(t) = n+1∑ k=1 akC k n+1 t∫ 0 Pn+1−k(x)dx = an+1C n+1 n+1 t + n∑ k=1 akC k n+1 t∫ 0 Pn+1−k(x)dx =an+1Cn+1n+1 t+ n∑ k=1 akC k n+1(n+1−k)! n+1−k∑ j=1 ( ∑ (i1,i2,...,ij): jP m=1 im=n+1−k im≥1 ai1 i1! ·ai2 i2! · · · aij ij ! ) tj+1 (j + 1)! =an+1Cn+1n+1 t+ n∑ j=1 n+1−j∑ k=1 ak (n + 1)! k! ( ∑ (i1,i2,...,ij): jP m=1 im=n+1−k im≥1 ai1 i1! ·ai2 i2! · · · aij ij ! ) tj+1 (j + 1)! =an+1Cn+1n+1 t+(n+1)! n∑ j=1 n+1−j∑ k=1 ( ak k! ∑ (i1,i2,...,ij): jP m=1 im=n+1−k im≥1 ai1 i1! ·ai2 i2! · · · aij ij ! ) tj+1 (j + 1)! =an+1Cn+1n+1 t + (n + 1)! n∑ j=1 ( ∑ (i1,i2,...,ij,ij+1): j+1P m=1 im=n+1 im≥1 ai1 i1! ·ai2 i2! · · · aij ij ! aij+1 ij+1! ) tj+1 (j + 1)! 79 =an+1Cn+1n+1 t + (n + 1)! n+1∑ j=2 ( ∑ (i1,i2,...,ij): j+1P m=1 im=n+1 im≥1 ai1 i1! ·ai2 i2! · · · aij ij ! ) tj j! =(n + 1)! n+1∑ j=1 ( ∑ (i1,i2,...,ij): jP m=1 im=n+1 im≥1 ai1 i1! ·ai2 i2! · · · aij ij ! ) tj j! . Bây giờ giả sử ngược lại rằng tồn tại dãy ak, k = 1, 2, ... sao cho các điều kiện (α), (β) thỏa mãn. Ta cần chứng minh rằng Pn(t) là dãy nhị thức, tức là cần chứng minh rằng (ii) đúng. Từ chứng minh ở bước trước, ta thấy rằng việc kiểm tra điều kiện (b) trong Định lý 4.2.1 bằng quy nạp, xuất phát từ điều kiện (β) là tương tự. Sau đó sử dụng Định lý 4.2.1 ta sẽ hoàn thành chứng minh. Định nghĩa 4.2.1. (theo[1, 2]) Cho trước dãy số thực ak, k = 1, 2, .... Giả sử rằng Pn(t) là dãy các đa thức thỏa mãn (α), (β). Ta gọi Pn(t) là dãy nhị thức sinh bởi dãy ak, k = 1, 2, ... đã cho. 4.3 Dãy nhị thức sinh bởi một hàm số Cho hàm số f có khai triển thành chuỗi lũy thừa f(x) = ∞∑ k=1 ak xk k! (f(0) = 0). Khi đó dãy số ak = f (k)(0), k = 1, 2, ... sẽ xác định một dãy nhị thức Pn(t) theo Định lý 4.2.2. Ta sẽ gọi dãy nhị thức này là dãy nhị thức sinh bởi hàm số f . Nhờ vào Định lý 4.2.2 ta có mệnh đề sau : Mệnh đề 4.3.1. (theo [1, 4]) Giả sử Pn(t) là dãy nhị thức sinh bởi hàm số f . Khi đó, etf(x) = ∞∑ n=0 Pn(t) xn n! . 80 Chứng minh: Ta có : etf(x) = 1 + ∞∑ k=1 [f(x)]k tk k! = 1 + ∞∑ k=1 tk k! ( ∞∑ j=1 aj xj j! )k = 1 + ∞∑ k=1 tk k! ∞∑ n=1 ( ∑ (i1,i2,...,ik): kP j=1 ij=n ij≥1 ai1 i1! ·ai2 i2! · · · aik ik! ) xn = 1 + ∞∑ n=1 [ n! ∞∑ k=1 ( ∑ (i1,i2,...,ik): kP j=1 ij=n ij≥1 ai1 i1! ·ai2 i2! · · · aik ik! ) tk k! ] xn n! = 1 + ∞∑ n=1 [ n! n∑ k=1 ( ∑ (i1,i2,...,ik): kP j=1 ij=n ij≥1 ai1 i1! ·ai2 i2! · · · aik ik! ) tk k! ] xn n! = P0(t) + ∞∑ n=1 Pn(t) xn n! = ∞∑ n=0 Pn(t) xn n! . * Chú ý: Trong các tài liệu hiện hành viết về dãy nhị thức, để kiểm tra Pn(t) là một dãy nhị thức người ta đã sử dụng phương pháp dựa trên các phép tính toán tử. Đây là một phương pháp chính thống và đã đạt được nhiều kết quả. Tuy nhiên phương pháp này chỉ áp dụng với giả thiết deg(Pn(t)) = n. Mệnh đề 4.3.2. Giả sử f(x) = ∞∑ k=1 ak xk k! và Pn(t) là một dãy các đa thức (P0(t) = 1). Nếu etf(x) = ∞∑ n=0 Pn(t) xn n! thì Pn(t) là một dãy nhị thức. Chứng minh: Ta có : etf(x)euf(x) = e(t+u)f(x). Theo giả thiết ta có : e(t+u)f(x) = ∞∑ n=0 Pn(t + u) xn n! 81 Mặt khác etf(x)euf(x) = ( ∞∑ n=0 Pn(t) xn n! )( ∞∑ n=0 Pn(u) xn n! ) = ∞∑ n=0 ( n∑ k=0 CknPk(t)Pn−k(u) ) xn n! . Do đó ta có : Pn(t + u) = n∑ k=0 CknPk(t)Pn−k(u). Vậy Pn(t) là dãy nhị thức. 4.4 Một số ví dụ về dãy nhị thức Ta sẽ vận dụng Mệnh đề 4.3.2 để khảo sát các dãy đa thức trong các ví dụ sau là dãy nhị thức. Trong đó, Ví dụ 4.5 nêu lên hai dãy đa thức hoàn toàn mới chưa có trong tài liệu tham khảo; Ví dụ 4.6 và Ví dụ 4.7 nêu lên hai dãy đa thức đã có nhưng ở đây chúng tôi hình thành hai dãy đa thức này theo con đường khác. Ví dụ 4.2. Dãy các đa thức sn(t) = (t)n = t(t− 1)(t− 2)...(t− n+ 1). Quy ước s0(t) = (t)0 = 1, t ∈ R. Ta có : ∞∑ n=0 (t)n xn n! = 1 + tx 1! + t(t− 1)x2 2! + · · ·+ t(t− 1) . . . (t− n + 1)x n n! + · · · = (1 + x)t = eln(1+x) t = etln(1+x). Do đó sn(t) là dãy nhị thức. Ví dụ 4.3. Dãy các đa thức Cn(t) = (t)n = t(t+1)(t+ 2)...(t+ n− 1). Quy ước C0(t) = (t) 0 = 1, t ∈ R. 82 Ta có : ∞∑ n=0 (t)n xn n! = 1 + tx 1! + t(t + 1)x2 2! + · · ·+ t(t + 1) . . . (t + n− 1)x n n! + · · · = (1 − x)−t = eln(1−x)−t = et(−ln(1−x)). Suy ra Cn(t) là dãy nhị thức. Ví dụ 4.4. Dãy đa thức mũ en(t) = n∑ k=0 Sn,kt k (e0(t) = 1, t ∈ R) là dãy nhị thức. Thật vậy, theo Mệnh đề 2.2.3 ta có ∞∑ n=0 en(t) xn n! = ∞∑ n=0 ( n∑ k=0 Sn,kt k ) xn n! = et(e x −1). Do đó en(t) = n∑ k=0 Sn,kt k là dãy nhị thức. Ví dụ 4.5. Dãy đa thức Pn(t) = n∑ k=0 En,kt k và Qn(t) = n∑ k=0 On,kt k với P0(t) = Q0(t) = 1, t ∈ R là dãy nhị thức. Thật vậy, theo Mệnh đề 2.2.6 ta có : et(chx−1) = ∞∑ n=0 Pn(t) xn n! và et.shx = ∞∑ n=0 Qn(t) xn n! . Do đó Pn(t), Qn(t) là các dãy nhị thức. Ta thấy rằng dãy đa thức Pn(t) = n∑ k=0 En,kt k là dãy nhị thức nhưng deg(Pn(t)) < n (vì En,n = 0 ∀n ≥ 1). Ví dụ 4.6. Dãy đa thức Gn(t) = n∑ k=0 Un,kt k = n∑ k=0 Ckn.k n−ktk với G0(t) = 1, t ∈ R là dãy nhị thức. Thật vậy, theo Mệnh đề 2.2.1 ta có etxe x = ∞∑ n=0 Gn(t) xn n! = ∞∑ n=0 n∑ k=0 Ckn.k n−ktk xn n! . Do đó Gn(t) là dãy nhị thức. 83 Ví dụ 4.7. Dãy đa thức Ln(t) = n∑ k=0 Ln,kt k = n∑ k=0 n! k! Ck−1n−1t k với L0(t) = 1, t ∈ R là dãy nhị thức. Thật vậy, theo Mệnh đề 2.2.8 ta có e tx 1− x = ∞∑ n=0 ( n∑ k=0 n! k! Ck−1n−1t k ) xn n! . Do đó Ln(t) là dãy nhị thức. Từ những ví dụ trên ta thấy rằng có mối liên hệ giữa: Dãy số {an,k}∞n=0 với dãy nhị thức Pn(t) = n∑ k=0 an,kt k và hàm sinh tương ứng với dãy nhị thức: ∞∑ n=0 Pn(t) xn n! . Có nghĩa là với mỗi dãy số an,k ta có dãy nhị thức tương ứng và hàm sinh tương ứng với dãy nhị thức. Ta có một số mối liên hệ sau: 1. Dãy sn,k =⇒ (t)n = n∑ k=0 sn,kt k =⇒ etln(1+x). 2. Dãy Cn,k =⇒ (t)n = n∑ k=0 Cn,kt k =⇒ et(−ln(1−x)). 3. Dãy Sn,k =⇒ en(t) = n∑ k=0 Sn,kt k =⇒ et(ex−1). 4. Dãy En,k =⇒ Pn(t) = n∑ k=0 En,kt k =⇒ et(chx−1). 5. Dãy On,k =⇒ Qn(t) = n∑ k=0 On,kt k =⇒ et.shx. 6. Dãy Un,k = Cknk n−k =⇒ Gn(t) = n∑ k=0 Un,kt k =⇒ etxex. 7. Dãy Ln,k = n! k! Ck−1n−1 =⇒ Ln(t) = n∑ k=0 n! k! Ck−1n−1t k =⇒ e tx 1− x . 84 kết luận Luận văn đã đạt được những kết quả chính sau đây: 1. Thông qua bài toán phân hoạch tập hợp, luận văn đưa ra một số loại số tổ hợp mới (En,k, On,k, Un,k, Ln,k, Pn, Qn, Gn, ...), thiết lập được công thức truy hồi và mối liên hệ giữa các số tổ hợp cơ bản đã biết với các số tổ hợp mới đó. Các Định lý 1.4.1, 1.4.2; Mệnh đề 1.4.1, 1.4.2, 1.4.3, 1.4.4, 1.4.5, 1.4.6, 1.4.7, 1.5.3; Hệ quả 1.4.1, 1.4.2 chưa được đề cập tới trong các tài liệu tham khảo. 2. Luận văn giải quyết được một số bài toán đếm bằng phương pháp hàm sinh. Chúng tôi đã có được một số kết quả mới sau: tìm được hàm sinh mũ cho các số tổ hợp được trình bày trong Chương 1 (Hệ quả 2.2.1, 2.2.6, 2.2.8), đưa ra công thức biểu diễn cho số ee (Hệ quả 2.2.2), mối liên hệ giữa số e với số Bell (Hệ quả 2.2.5), chứng minh được công thức Dobinski (Mệnh đề 2.2.5), mối liên hệ giữa số Bell Bn với các số phân hoạch chẵn (Pn), lẻ (Qn), công thức biểu diễn cho các số tổ hợp Pn, Qn (Hệ quả 2.2.7). 3. Giới thiệu phương pháp đếm bằng nguyên lý bao hàm và loại trừ và phương pháp đếm bằng công thức ngược. Với các phương pháp đếm này, chúng tôi trình bày công thức tính cho các số tổ hợp Dn, Sn,k (số Stirling loại hai) và xây dựng công thức hàm Euler. 4. Kiểm tra một số dãy các đa thức được trình bày trong Chương 2 là dãy nhị thức. Trong đó, Ví dụ 4.5 trình bày hai dãy nhị thức mới, chưa có trong tài liệu tham khảo. Hơn nữa, chúng tôi đưa ra được một số liên hệ giữa dãy số {an,k}∞n=0 với dãy nhị thức Pn(t) = n∑ k=0 an,kt k và hàm sinh tương ứng với dãy nhị thức: ∞∑ n=0 Pn(t) xn n! . 85 tài liệu tham khảo Tiếng Việt [1] Phạm Xuân Bình (2002), " Quá trình đếm ", Báo cáo đề tài nghiên cứu khoa học, Trường ĐH Quy Nhơn. [2] Vũ Đình Hòa (2002), Lý thuyết tổ hợp và các bài toán ứng dụng, NXB Giáo Dục, Hà Nội. [3] Nguyễn Đức Nghĩa, Nguyễn Tô Thành (2003), Toán rời rạc, NXB Đại học Quốc Gia Hà Nội. [4] Ngô Đắc Tân (2003), Lý thuyết tổ hợp và đồ thị, NXB Đại học Quốc Gia Hà Nội. Tiếng Anh [5] Martin Aigner (1997), Combinatorial Theory, Spring Verlag, Berlin Hei- delberg. [6] Proudnikov et al (1981), Intergrals and Series of Elementary Functions, Nauka, Moscou, (In Russian). [7] Richard P.Stanley (2001), Enumerative Combinatorics, Cambridge Uni- versity Press. [8] Karl H.Wehrhahn (1992), Combinatorics An Introductin, Carslaw Publi- cations, Australia. 86 lời cảm ơn. Luận văn được hoàn thành dưới sự hướng dẫn khoa học của PGS.TS. Nguyễn Đức Minh. Tác giả xin bày tỏ lòng biết ơn sâu sắc đến Thầy. Thầy đã tận tình hướng dẫn và động viên tác giả trong suốt quá trình thực hiện luận văn. Tác giả xin bày tỏ lòng biết ơn chân thành đến thầy Phạm Xuân Bình - Khoa Toán - ĐH Quy Nhơn. Một số vấn đề mới trong luận văn này đã được Thầy đặt ra cho chúng tôi giải quyết. Thầy đã giúp cho tác giả có niềm say mê nghiên cứu khoa học, gợi mở cho chúng tôi nhiều ý tưởng hay và truyền đạt nhiều kiến thức quý báu trong quá trình thực hiện luận văn này. Tác giả xin chân thành cảm ơn Ban lãnh đạo Trường Đại học Quy Nhơn, Phòng Quản lý khoa học, Phòng Đào tạo, các thầy cô giáo đã tham gia giảng dạy lớp cao học Toán K8, Trường THPT Nguyễn Chí Thanh- Khánh Hòa và các bạn đồng nghiệp đã tạo điều kiện thuận lợi và giúp đỡ tác giả trong quá trình học tập và hoàn chỉnh luận văn. Đoàn Nhật Thịnh