Luận văn Mối liên hệ giữa các số phân hoạch, số tất cả các phân hoạch chẵn , số tất cả các phân hoạch lẻ

rong phần này chúng ta xem xét một phương pháp rất hữu hiệu trong việc nghiên cứu những dãy số, bằng việc xem các số trong dãy số như là hệ số trong một chuỗi lũy thừa hình thức. (Xem [4], [6], [9]). 2.1 Hàm sinh Định nghĩa 2.1. ([9], tr 30). Nếu a0, a1, ..., an, .. là dãy số thì G(t) = a0 + a1t + a2t 2 + ..... + ant n + · · · được gọi là hàm sinh thường (hay hàm sinh) của dãy số {an}∞n=1. Hàm sinh có thể được nhân vô hướng với số thực hoặc phức. Hàm sinh có thể được cộng hoặc nhân với nhau như các chuỗi vô hạn. Ví dụ 2.1. Hàm sinh của dãy các hệ số nhị thức C0n;C 1 n;C 2 n; ...;C n n . Theo định nghĩa, hàm sinh của dãy số hữu hạn trên sẽ là G(t) = C0n + C 1 nt + C 2 nt 2 + ... + Cnn t n.  21 Ví dụ 2.2. Số Fibonacci ([9], tr 31). Xét dãy Fibonacci {Fn}∞n=0, xác định bởi công thức truy hồi Fn+2 = Fn+1 + Fn với điều kiện ban đầu F0 = 0, F1 = 1. Gọi G(t)=F0 + F1t+ F2t2 + F3t3 + ...+ Fntn + ....là hàm sinh của dãy Fibonacci. Suy ra tG(t) = F0t + F1t 2 + F2t 3 + ... + Fnt n+1 + ..... t2G(t) = F0t 2 + F1t 3 + F2t 4 + ... + Fnt n+2 + ... Do đó G(t)− tG(t)− t2G(t) = F0 + (F1 − F0)t + (F2 − F1 − F0)t2 + ... + (Fn+2 − Fn+1 − Fn)tn+2 + ... = t Suy ra (1 − t− t2)G(t) = t Suy ra G(t) = t 1 − t− t2 Vế phải của đẳng thức trên có thể phân tích thành 1√ 5 1 − at − 1√ 5 1 − bt , trong đó a = 1 + √ 5 2 và b = 1 −√5 2 Theo đó G(t) = 1√ 5 ( 1 1 − at − 1 1 − bt ) = 1√ 5 ( 1 + at + a2t2 + ... ) − 1√ 5 ( 1 + bt + b2t2 + ... ) = a− b√ 5 t a2 − b2√ 5 + a3 − b3√ 5 + ... + an − bn√ 5 tn + ... Do đó ta thu được công thức cho số Fibonacci thứ n như sau: Fn = an − bn√ 5 = 1√ 5 [( 1 + √ 5 2 )n − ( 1 −√5 2 )n] .  Ví dụ 2.3. Số Catalan ([9], tr 32 ). Ta định nghĩa số Catalan thứ n, ký hiệu cn, là số cách chèn n cặp ngoặc tròn vào tích x1x2 · · ·xn+1 của n + 1 số sao cho mỗi lần nhân chỉ có đúng hai thừa số. Chẳng hạn, ta có các cách chèn các cặp ngoặc tròn vào tích x1x2x3x4 như sau (x1(x2(x3x4))), ((x1x2)(x3x4)), (((x1x2)x3)x4), ((x1(x2x3))x4), (x1((x2x3)x4)). Như vậy, c3 = 5. Ta cũng tính được c1 = 1, c2 = 2. 22 Ta định nghĩa c0 = 1. Ta có nhận xét rằng mỗi cách chèn n cặp ngoặc tròn vào tích x1x2 · · ·xn+1 của n + 1 số chứa một cặp ngoặc ngoài cùng mà thực hiện phép nhân tích của k + 1 số đầu x1x2 · · ·xk+1 với tích của n− k số sau xk+2xk+3 · · ·xn+1, ở đây k có thể là 0, 1, ..., n− 1. Số cách chèn các cặp ngoặc tròn vào tích x1x2 · · ·xk+1 là ck, còn số cách chèn các cặp ngoặc tròn vào tích xk+2xk+3 · · ·xn+1 là cn−k−1. Vì vậy ta nhận được cn = c0cn−1 + c1cn−2 + c2cn−3 + · · · + cn−1c0 = n−1∑ k=0 ckcn−k−1. Đây là hệ thức truy hồi không tuyến tính. Ta sẽ tìm công thức tính cn qua n bằng cách xét hàm sinh của dãy {cn}∞n=0. Gọi G(t) = c0 + c1t+ c2t2 + ...+ cntn + ... là hàm sinh của dãy {cn}∞n=0. Khi đó, G(t)2 = c20 + (c0c1 + c1c0)t + (c0c2 + c1c1 + c2c0)t 2 + · · · + (c0cn−1 + c1cn−2 + · · · + cn−1c0)tn−1 + · · · = c1 + c2t + c3t 2 + c4t 3 + · · · Do đó tG(t)2 = c1t + c2t2 + c3t3 + · · · = G(t) − 1 Suy ra tG(t)2 −G(t) + 1 = 0 Giải phương trình bậc hai này G(t)ta thu được G(t) = 1 + √ 1 − 4t 2t và G(t) = 1 −√1 − 4t 2t Trong đó √ 1 − 4t = (1 − 4t) 1 2 = 1 + ( 1 2 ) 1! (−4t) + ( 1 2 )(−1 2 ) 2! (−4t)2 + ( 1 2 )(−1 2 )(−3 2 ) 3! (−4t)3 + · · · Do đó G(t) = 1 −√1 − 4t 2t = 1 2t [ 2t + 1 22.2! 42t2 + 1.3 23.3! 43t3 + · · · + 1.3.5...(2n− 3) 2n.n! 4ntn + · · · ] = 1 + 2t 2! + 1.3 3! 22t2 + 1.3.5 4! 23t3 + · · · + 1.3.5...(2n− 3) n! 2n−1tn−1 23 + 1.3.5...(2n− 1) (n + 1)! 2ntn · · · . Suy ra cn = 1.3.5...(2n− 1) (n + 1)! 2ntn = 1.2.3.4.5...(2n− 1)(2n) (n + 1)!.n!.2n 2n = 1.3.5.(2n− 1)(2n) (n + 1)!n! 2ntn = (2n)! (n + 1)!n! = 1 n + 1 Cn2n. Ta có tính một vài số đầu tiên bằng công thức trên: c1 = 1 2 C12 = 1 c2 = 1 3 C24 = 2 c3 = 1 4 C36 = 5 c4 = 1 5 C48 = 14 c5 = 1 6 C510 = 42.  2.2 Hàm sinh mũ Định nghĩa 2.2. ([9], tr 38). Hàm sinh mũ cho dãy số {an}∞n=0 là chuỗi lũy thừa hình thức f(t) = a0 + a1 t 1! + · · · + an t n n! + · · · 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. Có nghĩa là 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 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 |S(N)|=|S(M)|. 24 Khi đó, hàm sinh mũ của dãy các tập S([0]), S([1]), S([2]), ... (hay (S([n])∞0 ), được định nghĩa là hàm sinh mũ của dãy số |S([0])|, |S([1])|, |S([2])|, ... Gọi S(t) = |S([0])| + |S([1])| t 1! + |S([2])|t 2 2! + |S([3])|t 3 3! + · · · là hàm sinh mũ của dãy các dãy các tập các vật (S([n])∞0 và T (t) = |T ([0])| + |T ([1])| t 1! + |T ([2])|t 2 2! + |T ([3])|t 3 3! + · · · là hàm sinh mũ của dãy các tập các vật (T ([n])∞0 . Ta định nghĩa ST ([n]) là tập bao gồm tất cả các cặp (σ, τ), trong đó σ 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 [n], còn τ là một phần tử của của tập T (K) với K = [n] \K. Khi dó, |ST ([n])| = n∑ k=0 Ckn|S([k])||T ([n− k])| Nếu gọi ST (t) là hàm sinh mũ của dãy các tập các vật ST ([n]) thì ta có ST (t) = |ST (∅)| + |ST ([1])| t 1! + |ST ([2])|t 2 2! + |ST ([3])|t 3 3! + ... + |ST ([n])|t n n! + · · · , trong đó hệ số của tn n! là n∑ k=0 Ckn|S([k])||T ([n− k])|. Mặt khác, S(t)T (t) = |S(∅)||T (∅)| + ( |S(∅)||T ([1])| 1 0! 1 1! + |S([1])||T (∅)| 1 1! 1 0! ) t + ( |S(∅)||T ([2])| 1 0! 1 2! + |S([1])||T ([1])| 1 1! 1 1! + |S([2])||T (∅)| 1 2! 1 0! ) t2 + · · · + ( |S(∅)||T ([n])| 1 0! 1 n! + |S([1])||T ([n− 1])| 1 1! 1 (n− 1)! + |S([2])||T ([n− 2])| 1 2! 1 (n− 2)! + · · · + |S([k])||T ([n− k])| 1 k! 1 (n− k)! + · · · + |S([n− 2])||T ([2])| 1 (n− 2)! 1 2! + |S([n− 1])||T ([1])| 1 (n− 1)! 1 1! + |S([n])||T (∅)| 1 n! 1 0! ) tn + · · · 25 = |S(∅)||T (∅)| + ( |S(∅)||T ([1])| 1! 0!.1! + |S([1])||T (∅)| 1! 1!0! ) t 1! + ( |S(∅)||T ([2])| 2! 0!2! + |S([1])||T ([1])| 2! 1!1! + |S([2])||T (∅)| 2! 2!0! ) t2 2! + · · · + ( |S(∅)||T ([n])| n! 0!n! + |S([1])||T ([n− 1])| n! 1!(n− 1)! + |S([2])||T ([n− 2])| n! 2!(n− 2)! + · · · + |S([k])||T ([n− k])| n! k!(n− k)! + · · · + |S([n− 2])||T ([2])| n! (n− 2)!2! + |S([n− 1])||T ([1])| n! (n− 1)!1! + |S([n])||T (∅)| n! n!0! ) tn n! + · · · = ∞∑ n=0 ( n∑ k=0 Ckn|S([k])||T ([n− k])| ) tn n! Do đó ta được ST (t) = S(t)T (t). Sau đây, ta sẽ xét một vài ví dụ cụ thể, trong đó hàm sinh mũ đã được áp dụng để giải quyết bài toán đếm. Ví dụ 2.4. (Số các xáo trộn) ([9], tr 39). Giả sử X là một tập hữu hạn và X = {x1, x2, x3, ..., xn}. Ta sẽ đồng nhất mỗi hoán vị (a1, a2, a3, .., 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. Ta kí hiệu Dn là số tất cả các xáo trộn của tập hữu hạn X, có lực lượng n. Vấn đề được đặt ra ở đây là tính Dn. 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ũ của dãy P ([0]), P ([1]), P ([2]), ..., P ([n]), ... Mỗi hoán vị của [n] có thể 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 26 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, ..., 10} có thể được xem là cặp (σ, τ) với σ = (19573)(46) là một xáo trộn trên {1, 3, 4, 5, 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]))∞0 và (D([n]))∞0 tương ứng là i(t) = 1+ 1 1! t+ 1 2! t2+ 1 3! t3+· · · = et, =⇒ i(t)−1 = e−t = 1− t 1! + t2 2! −t 3 3! +· · ·+(−1)n t n n! +· · · d(t) = D0 + D1 1! t + D2 2! t2 + D3 3! t3 + · · · . Vì |P ([n])| = n!, nên hàm sinh mũ cho dãy (P ([n]))∞0 sẽ là p(x) = 1 + 1! 1! t + 2! 2! t2 + 3! 3! t3 + · · · = 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]))∞0 . Suy ra, d(t) = p(t)(i(t))−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 (S([n]))∞0 : s (t) = |S(∅)| + |S ([1])| 1! t + |S ([2])| 2! t2 + |S ([3])| 3! t3 + · · · 27 Khi đó nếu kí hiệu D (s (t))bằng 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])| 1! t + |S ([3])| 2! t2 + |S ([4])| 3! t3 + · · · Đẳng thức trên chứng tỏ rằng S′ ([n]) = S ([n + 1]) với 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 (x) 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 ở hai ví dụ tiếp sau đây. Ví dụ 2.5. (Hoán vị vòng quanh) ([3], tr 100). Có n vị trí trên một vòng tròn. Mỗi cách sắp xếp của n số của tập [n] = {1, 2, ..., n} vào n vị trí đó được gọi là hoán vị vòng quanh của tập [n]. Hai hoán vị vòng quanh của 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ố bằng nhau trong hai sắp xếp đó. Ta cũng quy ước rằng số hoán vi vòng quanh của tập [0] bằng 1. Vấn đề đặt ra là tính số hoán vị vòng quanh của tập [n] theo n. Ký hiệu tập các hoán vị vòng quanh của tập [n] bằng C ([n]). Giả sử c(t) là hàm sinh mũ cho dãy (C ([n]))∞0 và c ′(t) = D ((t)). Khi đó, như đã nhận xét ở trên đối với đạo hàm của hàm sinh mũ, các hoán vị vòng quanh của tập [n + 1] được đếm bởi c′ (t) với giá [n]. Mặt khác,hoán vị vòng quanh của tập [n + 1] cũng có thể được đồ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 vò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 vòng tròn theo chiều kim đồng hồ. Chẳng hạn, hoán vị vòng quanh 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 (P ([n]))∞0 , thì c′ (t) = p (t) 28 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! n! tn = ∞∑ n=0 tn = 1 1 − t Vậy c′ (t) = 1 1 − t Suy ra c (t) = −ln (1 − t) + c0 với c0 là hằng số. Vì c(0) = |c(∅)| = 1 =⇒ c0 = 1 Do đó c(t) = 1 − ln(1 − t) = 1 + t + t 2 2 + 2! t3 3! + · · · + (n− 1)!t n n! + · · · Vậy |C ([n])| = (n− 1)!.  Ví dụ 2.6. ( E- hoán vị của tập [2n + 1] (n > 0) ) ([3], tr 101). Hoán vị (a1, a2, ..., a2n+1) của tập [2n + 1] được gọi là E-hoán vị của tập [2n + 1] nếu ak > ak−1 cho k chẵn và ak a3 · · · a2n+1). Vấn đề đặt ra là tính số E-hoán vị của tập [2n + 1] theo n. Gọi S ([2n + 1]) là tập các E-hoán vị của tập [2n + 1] , n > 0. Bằng cách xem S ([2n]) = ∅, (n > 0), ta xét dãy các tập (S([n]))∞0 . Đặt sn = |S ([n])|, ở đây s2n+1 = |S ([2n + 1])|; s2n = |S ([2n])| = 0. Gọi s(t) là hàm sinh mũ cho dãy các tập (S ([n]))∞0 , thì s (t) = s0 + s1 t 1! + s2 t2 2! + s3 t3 3! + s4 t4 4! + s5 t5 5! + · · · + +sn t n n! + · · · = s1 t 1! + s3 t3 3! + s5 t5 5! + · · · + s2n+1 t 2n+1 (2n + 1)! + · · · Ký hiệu s′ (t) là đạo hàm của s (t) theo biến t. Ta có, s′ (t) = s1 + s3 t2 2! + s5 t4 4! + · · · + s2n+1 t 2n (2n)! + · · · Như vậy, các E-hoán vị của tập [2n + 1] được đếm bởi s′ (t) với giá [2n]. Ta thấy rằng trong mỗi E-hoán vị (a1, a2, a3, a2n+1) của tập [2n + 1], số 2n+1 cần phải ở vị trí chẵn ( vì 2n + 1 là số lớn nhất trong tập [2n + 1] ) . Do đó, với n > 1 phần 29 bên trái của 2n+1 trong một E-hoán vị α của tập [2n + 1] tạo thành một E-hoán vị σ của tập con K có lực lượng lẻ nào đó của tập [2n]; còn phần bên phải của 2n + 1 trong α tạo thành một E-hoán vị τ của tập [2n] \K. Tương ứng mỗi α với cặp (α, τ) nói trên là tương ứng 1-1. Chẳng hạn, phần tử α = (3, 4, 1, 5, 2) của S [5] tương ứng với cặp (σ, τ) = ((3, 4, 1) (2)), ở đây σ = (3, 4, 1) là một hoán vị của tập {1, 3, 4}, còn τ = (2) là một hoán vị của tập {2}. Như vậy, ta nhận được tương ứng 1-1 giữa các phần tử của S ([2n + 1]) và S2 ([2n]) với mọi n > 1. Ta có s2(t) = |S2([0])|+ |S2([1])| t 1! + |S2([2])|t 2 2! + |S2([3])|t 3 3! + · · ·+ |S2([n])|t n n! + · · · trong đó |S2([n])| = n∑ k=0 Ckn|S([k])||S([n− k])|. Ta thấy rằng khi n là số lẻ thì k là số chẵn hoặc n− k là số chẵn. Điều này cho ta |S([k])| = 0 hoặc |S([n − k])| = 0, suy ra |S2([n])| = 0. Ngoài ra, khi n = 0 thì |S2([0])| = n∑ k=0 Ckn|S([0])||S([0])| = 0. Do đó s2(t) = |S2([2])|t 2 2! + |S2([4])|t 4 4! + · · · + |S2([2n])| t 2n (2n)! + · · · Do tương ứng 1-1 giữa các phần tử của S ([2n + 1]) và S2 ([2n]) với mọi n > 1 nên ta có s2(t) = s3 t2 2! + s5 t4 4! + s7 t6 6! + · · · + s2n+1 t 2n (2n)! + · · · Hơn nữa, hệ số tự do của s′ (t) là s1 = |S([1])| = 1. Do đó ta nhận được phương trình vi phân s′ (t) = 1 + s2 (t) với điều kiện ban đầu s(0) = 0. Giải phương trình vi phân này ta được s(t) = tan(t) Vì tan(t) là hàm số lẻ nên ta có tan(t) = ∞∑ n=1 Tn (2n− 1)!x 2n−1 . Vì tan(t)cos(t) = sin(t) nên ta có( ∞∑ n=1 Tn (2n− 1)!t 2n−1 )( ∞∑ n=0 (−1)n t 2n (2n)! ) = ∞∑ n=1 t2n−1 (2n− 1)! 30 Khai triển và đồng nhất hệ số ta được Tn (2n− 1)! − Tn−1 (2n− 3)! . 1 2! + Tn−2 (2n− 5)! . 1 4! − · · · = (−1)n−1 1 (2n− 1)! Suy ra Tn − C22n−1Tn−1 + C42n−1Tn−2 − · · · = (−1)n−1 Từ đó T1 = 1, T2 = 2, T3 = 16, T4 = 272, T5 = 7936, ... Cuối cùng ta được T (t) = tant = t + 2 t3 3! + 16 t5 5! + 272 t7 7! + 7936 t9 9! + · · · = t + 1 3 t3 + 2 15 t5 + 17 315 t7 + 62 2835 t9 + · · · Vậy s2n+1 = |S[(2n+1)]| chính là hệ số tương ứng với lũy thừa t2n+1 trong khai triển hàm tan(t).  Ví dụ 2.7. (Công thức Dobinski). Trong ví dụ này, ta sẽ dùng công cụ hàm sinh để xây dựng công thức Dobinski cho số Bell Bn = 1 e ∞∑ k=0 kn k! . Chứng minh. Đặt en(t) = n∑ k=0 Sn,kt k Trước hết, hàm sinh của dãy {en(t)}∞n=0 sẽ là et(e x−1). Thật vậy, Ta có et(e x−1) = ∞∑ k=0 [f(x)]k tk k! Hơn nữa, ex = ∞∑ m+0 xm m! = 1 + ∞∑ m=1 xm m! =⇒ ex − 1 = ∞∑ m=1 xm m! 31 =⇒ (ex − 1)k = ( ∞∑ m=1 xm m! )k = ∞∑ n=1  ∑ (i1,i2,...,ik): k P j=1 ij=n ij≥1; ( 1 i1! 1 i2! · · · 1 ik! ) xn  Do đó et(e x−1) = ∞∑ k=0  ∞∑ n=1  ∑ (i1,i2,...,ik): k P j=1 ij=n ij≥1 ( 1 i1! 1 i2! · · · 1 ik! ) x n  tk k! = ∞∑ k=0  ∞∑ n=1 n! ∑ (i1,i2,...,ik): k P j=1 ij=n ij≥1 ( 1 i1! 1 i2! · · · 1 ik! )  xn n!  tk k! = ∞∑ k=0 ( ∞∑ n=1 k!Sn,k xn n! ) tk k! = ∞∑ k=0 ( ∞∑ n=1 Sn,k xn n! ) tk = 1 + ∞∑ k=1 ( ∞∑ n=1 Sn,k xn n! ) tk = 1 + ∞∑ n=1 ( ∞∑ k=1 Sn,kt k ) xn n! = 1 + ∞∑ n=1 ( n∑ k=1 Sn,kt k ) xn n! (vìSn,k = 0, với k > n) = ∞∑ n=0 ( n∑ k=0 Sn,kt k ) xn n! = ∞∑ n=0 en(t) xn n! 32 Do vậy, hàm sinh của dãy {en(t)}∞n=0 t là et(e x−1). Tiếp theo ta khai triển hàm et(e x−1) thành chuỗi lũy thừa: Ta có ete x = ∞∑ k=0 1 k! (tex)k = ∞∑ k=0 tk k! ekx = ∞∑ k=0 tk k! ( ∞∑ n=0 1 n! knxn ) = ∞∑ k=0 tk k! ( ∞∑ n=0 kn xn n! ) = ∞∑ n=0 ( ∞∑ k=0 kn k! tk ) xn n! =⇒ et(ex−1) = e−t ∞∑ n=0 ( ∞∑ k=0 kn k! tk ) xn n! = ∞∑ n=0 ( e−t ∞∑ k=0 kn k! tk ) xn n! =⇒ en(t) = e−t ∞∑ k=0 kn k! tk Cho t = 1 ta thu được en(1) = e−1 ∞∑ k=0 kn k! . Trong đó, en(1) = n∑ k=0 Sn,k = Bn Vậy, Bn = 1 e ∞∑ k=0 kn k! . 2.3 Công thức sàng Trong mục này chúng ta sẽ dùng phương pháp đếm bằng nguyên lý bù trừ kết hợp phương pháp đếm bằng công thức ngược để chứng minh công thức sàng. (Xem [4], [9]). 2.3.1 Nguyên lý bù trừ Đây là một trong những phương pháp đếm cơ bản thường được sử dụng trong các bài toán đếm. Định lý 2.1. Giả sử A1, A2, ..., An là các tập hữu hạn bất kỳ. Khi đó |A1 ∪ A2 ∪ ... ∪ An| = ∑ 16i16n |Ai1 | − ∑ 16i1<i26n |Ai1 ∩ Ai2| + ... + (−1)k+1 ∑ 16i1<i2<...<ik6n |Ai1 ∩ Ai2 ∩ ... ∩ Aik | + ... + (−1)n+1|A1 ∩ A2 ∩ ... ∩ An|. 33 Chứng minh. Ta chứng minh công thức trên bằng quy nạp theo n. Với n = 1 công thức trên hiển nhiên đúng. Ta chứng minh rằng nó cũng đúng cho n = 2. Ta có, A1 = (A1 ∩ A2) ∪ (A1 \ (A1 ∩ A2)), A2 = (A1 ∩ A2) ∪ (A1 \ (A2 ∩ A2)), A1 ∪ A2 = (A1 ∩ A2) ∪ (A1 \ (A1 ∩ A2)) ∪ (A2 \ (A1 ∩ A2)). Hợp ở các vế phải là hợp của tập đôi một rời nhau. Vì vậy theo quy tắc cộng ta có, |A1| = |A1 ∩ A2| ∪ |A1 \ (A1 ∩ A2)|, |A2| = |A1 ∩ A2| ∪ |A1 \ (A2 ∩ A2)|, |A1 ∪ A2| = |A1 ∩ A2| ∪ |A1 \ (A1 ∩ A2)| ∪ |A2 \ (A1 ∩ A2)|. Từ ba đẳng thức này ta thu được |A1 ∪ A2| = |A1| + |A2| − |A1 ∩ A2| Vậy định lý đúng cho n = 2. Giả sử công thức đã được chứng minh cho n = m và A1, A2, ..., Am, Am+1 là m+1 tập hữu hạn bất kỳ đã cho. Vì công thức đã được chứng minh cho n = 2 nên |A1 ∪ A2 ∪ ... ∪ Am ∪ Am+1| = |(A1 ∪ A2 ∪ ... ∪ Am) ∪ Am+1| =|A1 ∪ A2 ∪ ... ∪ Am| + |Am+1| − |(A1 ∪ A2 ∪ ... ∪ Am) ∩ Am+1| =(Theo giả thiết quy nạp) [ ∑ 16i16m |Ai1| − ∑ 16i1<i26m |Ai1 ∩ Ai2|+ ... + (−1)k+1 ∑ 16i1<i2<...<ik6n |Ai1 ∩ Ai2 ∩ ... ∩ Aik |+ ... + (−1)m+1|A1 ∩ A2 ∩ ... ∩ Am| ] + |Am+1| − |(A1 ∪ A2 ∪ ... ∪ Am) ∩ Am+1| 34 Mặt khác, |(A1 ∪ A2 ∪ ... ∪ Am) ∩ Am+1| = |(A1 ∩ Am+1) ∪ (A2 ∩ Am+1) ∪ ... ∪ (Am ∩ Am+1| = = (Theo giả thiết quy nạp) ∑ 16i16m |Ai1 ∩ Am+1| − ∑ 16i1<i26m |Ai1 ∩ Ai2 ∩ Am+1|+ ... + (−1)k+1 ∑ 16i1<i2<...<ik6m |Ai1 ∩ ... ∩ Aik ∩ Am+1|+ ... + (−1)m+1|A1 ∩ A2 ∩ ... ∩ Am ∩ Am+1| Thay kết quả này vào đẳng thức trên ta thu được |A1 ∪ A2 ∪ ... ∪ Am+1| = ∑ 16i16m+1 |Ai1| − ∑ 16i1<i26m+1 |Ai1 ∩ Ai2| + ... + (−1)k+1 ∑ 16i1<i2<...<ik6m+1 |Ai1 ∩ Ai2 ∩ ... ∩ Aik | + ... + (−1)(m+1)+1|A1 ∩ A2 ∩ ... ∩ Am+1|. Do đó định lý đúng với n = m+1 Theo nguyên lý quy nạp ta có điều cần chứng minh. Ví dụ 2.8. Trong phần trước, ta đã định nghĩa một xáo trộn của tập X = {x1, x2, ..., xn} là một hoán vị ϕ của X mà không có điểm bất động nào. Ta cũng đã tính số Dn tất cả các xáo trộn của tập X bằng phương pháp hàm sinh mũ. Trong ví dụ này ta sẽ tính lại số Dn bằng phương pháp sử dụng nguyên lý bù trừ. Chứng minh. Giả sử A là tập tất cả các hoán vị của tập X,Ai = {a ∈ A|xi là điểm bất động của a}. Khi đó, A\ (A1∪ ...∪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ý bù trừ, ta có |A1 ∪ ... ∪ An| = ∑ 16i6n |Ai| − ∑ 16i<j6n |Ai ∩ Aj | + ... + (−1)n+1|A1 ∩ ... ∩ An|, |A| = n!, |Ai| = (n− 1)!, |Ai1 ∩Ai2 ∩ ...∩Aik | = (n− k)! với mọi k=2,3,...,n và ij ∈ {1, 2, ..., n}, j = 1, k Suy ra, Dn = |A \ (A1 ∪ ... ∪ An)| = |A| − |A1 ∪ ... ∪ An| = n! − [ C1n(n− 1)! − C2n(n− 2)! + ... + (−1)n−1Cnn(n− n)! ] 35 = n! − n! 1! + n! 2! − n! 3! + ... + (−1)nn! n! = n! [ 1 − 1 1! + 1 2! − 1 3! + ... + (−1)n 1 n! ] . 2.3.2 Công thức ngược Ta đã chứng minh được rằng mn = n∑ k=1 Ckmk!Sn,k = n∑ k=1 Sn,k(m)k Các đồng nhất thức này có thể được sử dụng để tính Sn,k. Trong mục này ta sẽ xây dựng công thức ngược cho các đồng nhất thức như thế. Chẳng hạn, bằng cách này có thể biểu thị các số Stirling qua các lũy thừa bậc n. Phương pháp này cùng với nguyên lý bù trừ sẽ được dùng để thiết lập công thức sàng. Ta sẽ sử dụng ma trận nghịch đảo và công cụ đa thức để nhận được công thức ngược. Ta định nghĩa dãy đa thức là một dãy có thứ tự p0(x), p1(x), p2(x), p3(x), ... các đa thức pn(x), n = 0, 1, 2, ..., mà ta đơn giản kí hiệu là (pn(x))∞0 , thỏa mãn các điều kiện sau: (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) bằng n. Nếu (qn(x)) ∞ 0 là một dãy đa thức khác, thì (q0(x), q1(x), ..., qn(x)) lập thành một cơ sở cho không gian vectơ các đa thức có bậc không quá n. Do đó, với mỗi pn(x), n = 0, 1, 2, ... của dãy (pn(x))∞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) = ∑ bn,kpk(x) n = 0, 1, 2, .... 36 Các số an,k và bn,k cũng được gọi là các hệ số liên hệ. 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) ... pn(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 = (aij)m×m Tương tự, biểu diễn của m + 1 đa thức qn(x) đầu tiên qua pn(x) có thể được viết dưới dạng ma trận Q = PA, ở đây P và Q là các vectơ cột đã nói trên, còn B = (bij)m×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)) m 0 và (qk(x)) m 0 suy ra 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. Định lý 2.2. (Công thức ngược cho các đồng nhất thức tổ hợp). Giả sử A = (aij) và B = (bij) 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 . Ta cũng giả sử rằng có dãy các số (un) ∞ 0 và (vn) ∞ 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,... 37 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 nhau nên vn = n∑ k=0 bn,kuk cho mọi n=0,1,2,... Nhận xét. Công thức ngược cho các đồng nhất thức tổ hợp trong định lý 2.2 có thể áp dụng vào các dạng bài toán đếm như sau: " Giả sử (S([n]))∞0 là một dãy các tập các vật cần đếm, còn (T ([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)∞0 và (vn) ∞ 0 thỏa mãn các điều kiện trong định lý 2.2. Khi đó theo định lý, nếu đã 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". Sau đây ta sẽ xem xét một số trường hợp cụ thể của định lý 2.2. 38 Công thức nhị thức ngược. Ta xét các dãy đa thức (xn)∞0 và ((x− 1)n)∞0 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ừ các đa thức trên là A =  C00 0 · · · 0 C01 C 1 1 · · · 0 ... ... ... ... C0n C 1 n · · · 0  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 nhị thức ngược. Áp dụng định lý 2.2, nếu có hai dãy số (un) ∞ 0 và (vn) ∞ 0 liên hệ với nhau bằng đẳng thức un = n∑ k=0 Cknvk thì vn = n∑ k=0 (−1)n−kCknuk Ví dụ 2.9. Tính số phân hoạch Sn,m của tập [n] thành k khối theo n và k. Chứng minh. Nếu ký hiệu Sn([k]) là tập tất cả các hàm từ tập [n] vào tập [k], còn Tn([k]) là tập tất cả các toàn ánh từ [n] lên [k], thì |Sn([k])| = uk = kn, |Tn([k])| = vm = m!Sn,k ( chương 1) 39 Hơn nữa, ta có hệ thức sau cũng đã có ở chương 1 giữa un và vn: kn = k∑ j=0 Cjkj!Sn,j . Áp dụng công thức nhị thức ngược ở trên ta thu được k!Sn,k = k∑ j=0 (−1)k−jCjkjn Do đó số phân hoạch của của tập n phần tử thành k tập con không rỗng là Sn,k = 1 m! k∑ j=0 (−1)k−jCjkjn Công thức ngược cho các số Stirling Đặt (x)n = x(x− 1)(x− 2)...(x− n + 1) Xét dãy (xn)∞0 và ((x)n)∞0 . Các dãy này là các dãy đa thức. Trong chương 1 ta đã biết mn = n∑ k=0 Sn,k(m)k với mọi số nguyên dương m, tức là đa thức xn − n∑ k=0 Sn,k(x)k có vô số nghiệm. Theo định lý cơ bản của đại số ta có xn − n∑ k=0 Sn,k(x)k = 0 Suy ra, xn − n∑ k=0 Sn,k(x)k Mặt khác giả sử (x)n = n∑ k=0 sn,kx k. là biểu diễn của (x)n theo xk. Các hệ số nối sn,k trong đẳng thức này được gọi là số Stirling loại một. 40 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 Stirling ngược. Vì BA = 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. Theo định lý 2.2, nếu có hai dãy số (un) ∞ 0 và (vn) ∞ 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. 2.3.3 Công thức sàng Ta áp dụng phương pháp nghịch đảo để thiết lập một loại công thức đặc biệt gọi là công thức sàng. Giả sử X là một tập hữu hạn và A1, A2, ..., An là các tập con của X. Ta định nghĩa hai dãy các số s0, s1, ..., sn và e0, e1, ..., en liên kết với các tập A1, A2, ..., An và X như sau. 41 s0 = |X| s1 = |A1| + |A2| + · · · + |An|, s2 = |A1 ∩ A2| + |A1 ∩ A3| + · · · + |An−1| ∩ An| ................................................... sk = ∑ 16i1<i2<···<ik6n |Ai1 ∩ Ai2 ∩ · · · ∩ Aik |, .............................................. sn = |A1 ∩ A2 ∩ · · · ∩ An|, còn ek là số các phần tử của X chứa trong đúng k tập con trong số các tập con A1, A2, ..., An của X, k = 0, 1, 2, ..., n. Khi đó theo nguyên lý bao hàm và loại trừ ta có e0 = |X| \ |A1 ∪ A2 ∪ · · · ∪ An| = s0 − s1 + s2 − · · · + (−1)ksk + · · · + (−1)nsn. Trong mục này ta muốn tìm công thức để biểu thị ek, k = 0, 1, 2, ..., n qua các số s0, s1, ..., sn. Để làm điều đó trước hết ta biểu thị s0, s1, ..., sn qua e0, e1, · · · , en; sau đó ta dùng công thức nghịch đảo để biểu thị e0, e1, · · · , en qua s0, s1, · · · , sn. Ta có s0 = |X| = e0 + e1 + e2 + · · · + en. Mặt khác, một phần tử x chứa trong đúng m tập con là Ai1 , · · · · · · , Aim sẽ được tính trong sk tổng cộng là Ckm lần vì có C k m số hạng trong công thức tính sk = ∑ 16j1<j2<···<jk6n |Aj1 ∩ Aj2 ∩ · · · ∩ Ajk | với tất cả các tập con Ajt được chọn từ Ai1 , · · · · · · , Aim. Do đó sk = C k kek + C k k+1ek+1 + · · · + Cknen. 42 Dưới dạng ma trận ta có thể viết s0 s1 ... sn  =  C00 C 0 1 C 0 2 · · · C0n 0 C11 C 1 2 · · · C1n ... ... ... ... ... 0 0 0 · · · Cnn   e0 e1 ... en  Nếu ta ký hiệu s là vectơ cột của các sk, k = 1, 2, ..., n; e là vectơ cột của các ek, k = 1, 2, ..., n còn A1 là ma trận trong phương trình trên thì phương trình này có thể viết ngắn gọn thành s = A1e. Vì ma trận A1 là ma trận chuyển vị của ma trận A trong công thức nghịch đảo nhị thức nên A−11 = (A t) −1 = (A−1)t = Bt, ở đây B là ma trận của công thức nghịch đảo nhị thức còn Bt là ma trận chuyển vị của B. Suy ra A−11 = B t =  (−1)0C00 (−1)1C01 (−1)2C02 · · · (−1)nC0n 0 (−1)0C11 (−1)1C12 · · · (−1)n−1C1n ... ... ... ... ... 0 0 0 · · · (−1)0Cnn  Từ phương trình s = A1e ta suy ra e = A −1 1 s = B ts. Do đó ta có mệnh đề sau đây. Mệnh đề 2.3. (Công thức sàng). ek = sk − Ckk+1sk+1 + Ckk+2sk+2 − · · · + (−1)n−kCknsn. (2.1) Từ công thức sàng ta có thể chứng minh được công thức tính số phần tử của tập X chứa trong một số chẵn hay một số lẻ các tập con A1, A2, · · · , An của X qua mệnh đề sau. Mệnh đề 2.4. e0 + e2 + e4 + · · · = 1 2 [ s0 + n∑ k=0 (−2)ksk ] , (2.2) e1 + e3 + e5 + · · · = 1 2 [ s0 − n∑ k=0 (−2)ksk ] (2.3) 43 Chứng minh. Giả sử G(t) là hàm sinh thường cho dãy (ej) ∞ 0 . Vì ej = 0 cho j > n, nên G(t) = e0 + e1t + e2t 2 + · · · + entn. Thay biểu thức cho ek qua si trong công thức sàng vào g(t) ta thu được G(t) = [s0 − s1 + s2 − · · · + (−1)ksk + · · · (−1)nsn] + [s1 − C12s2 + · · · + (−1)k − 1C1ksk + · · · + (−1)n− 1C1nsn]t + [s2 + · · · + (−1)k−2C2ksk + · · · + (−1)n−2C2nsn]t2+ · · · · · · · · · · · · · · · + [sk + · · · + (−1)n−kCknsn]tk · · · · · · · · · · · · · · · + snt n. Suy ra, G(t) = s0 + s1(t− 1) + s2(t− 1)2 + · · · + sk(t− 1)k + · · · + sn(t− 1)n. Vì vậy, G(1) = s0 G(−1) = s0 − 2s1 + 22s2 + · · · + (−1)n2nsn. Mặt khác từ G(t) = e0 + e1t + e2t2 + · · · + entn ta lại có G(1) = e0 + e1 + · · · + en, G(−1) = e0 − e1 + · · · + (−1)nen Suy ra, e0 + e2 + e4 + · · · = 1 2 [G(1) + G(−1)] = 1 2 [ s0 + n∑ k=0 (−2)ksk ] , e1 + e3 + e5 + · · · = 1 2 [G(1) −G(−1)] = 1 2 [ s0 − n∑ k=0 −2ksk ] 44 Sau đây ta xét một vài dụ áp có dụng công thức sàng. Ví dụ 2.10. Một dãy RNA bao gồm các phân tử uracil, adenine, cytosine và quanine mà ta sẽ viết tắt là U, A, C và Q. Hãy tính số các dãy RNA độ dài n có số các phân tử A là chẵn. Chứng minh. Gọi X là tập tất cả các RNA độ dài n được tạo ra từ 4 loại phân tử U, A, C và Q, Ai = {x ∈ X|x có phân tử A ở vị trí thứ i}, i = 1, 2, · · · , n. Khi đó |X| = 4n, |Ai| = 4n−1, |Ai ∩ Aj | = 4n−2, · · · Vì vậy, s0 = 4n, s1 = n4n−1, · · · , sk = Ckn4n−k, · · · . Do đó số các dãy RND dộ dài n có số các phân tử A là chẵn bằng e0 + e2 + e4 + · · · = 1 2 [4n + ∞∑ k=0 (−2)kCkn4n−k] = 1 2 [4n + n∑ k=0 Ckn(−2)k4n−k] = 1 2 [4n + (−2 + 4)n] = 1 2 [4n + 2n]. 45 Chương 3 Biến thể của công thức sàng Công thức sàng trong mệnh đề 2.3 đã cho ta một cách xác định số phần tử chứa trong đúng k tập con trong số n các tập con A1, · · · , An cho trước của một tập hữu hạn X. Mệnh đề 2.4 cho ta công thức tính tổng số phần tử của X chứa trong một số chẵn hay một số lẻ các tập con nói trên của X. Nói cách khác, các công thức (2.1), (2.2), (2.3) cho ta một phương pháp sàng lọc số phần tử của một tập hợp hữu hạn. Trong mục này, chúng ta sẽ quan tâm đến một vấn đề liên quan đến số cách phân hoạch một tập hợp thành các tập con không rỗng. Đó là vấn đề về số cách phân hoạch một tập hợp hữu hạn X thành các tập con không rỗng sao cho mỗi tập con có một số chẵn(lẻ) phần tử và các mối liên hệ giữa chúng. Nói cách khác, đây là một phương pháp sàng lọc các tập con của một tập hợp hữu hạn mà ta có thể tạm gọi là một biến thể của công thức sàng. Thực chất ở đây là ta sẽ "phân tích chẵn(lẻ)" số các phân hoạch và là một vấn đề mới. Các kết quả chính ở phần này sẽ được công bố trên Tạp Chí Khoa Học của Trường Đại Học Quy Nhơn. 46 Trước hết chúng ta sẽ sử dụng một số ký hiệu sau đây: En,k (n, k ∈ N): số cách phân hoạch tập n phần tử thành k tập con không rỗng sao cho mỗi tập con có một số chẵn phần tử. Khi đó En,k = 0 nếu k > n. Quy ước E0,0 = 1 và En,0 = 0, ∀n > 1. On,k (n, k ∈ N): số cách phân hoạch tập n phần tử thành k tập con không rỗng sao cho mỗi tập con có một số lẻ phần tử. Khi đó On,k = 0 nếu k > n. Quy ước O0,0 = 1 và On,0 = 0 ∀n > 1. Pn = n∑ k=0 En,k; Qn = n∑ k=0 On,k. Như vậy, Pn (Qn) chính là số tất cả các phân hoạch của tập n phần tử sao cho mỗi tập con đều có một số chẵn (lẻ) phần tử. Ta gọi Pn(Qn) là các số phân hoạch chẵn (lẻ). Nhận xét. 1) Vì tổng các số chẵn là số chẵn nên E2n+1,k = 0 ∀n, k ∈ N. Do đó, P2n+1 = 0, n = 0, 1, 2, .... 2) Tương tự, O2n,2k+1 = 0 (∀n > 1,∀k > 0) và O2n+1,2k = 0 (∀n, k > 0). Trước hết, từ mệnh đề 1.6 ta có kết quả sau. Bổ đề 3.1. Cho tập X gồm n phần tử. Xét phép phân hoạch tập X thành k tập con không rỗng. Giả sử số phần tử trong mỗi tập là ij , j = 1, k. Khi đó (i) En,k = n! k! ∑ (i1,i2,...,ik): k P j=1 ij=n ij≥1;ij :chẵn ( 1 i1! · 1 i2! · · · 1 ik! ) . (3.1) (ii) On,k = n! k! ∑ (i1,i2,...,ik): k P j=1 ij=n ij≥1;ij :lẻ ( 1 i1! · 1 i2! · · · 1 ik! ) . (3.2) Đặt Pn(t) = n∑ k=1 En,kt k và Qn(t) = n∑ k=1 On,kt k. Khi đó ta có mệnh đề sau. 47 Mệnh đề 3.2. Các khẳng định sau là đúng. (i) et(chx−1) là hàm sinh của dãy {Pn(t)}∞n=0 (ii) et.shx là hàm sinh của dãy {Qn(t)}∞n=0 Chứng minh. (i) Theo bổ đề 3.1, En,k = n! k! ∑ (i1,i2,...,ik): k P j=1 ij=n ij≥1;ij :chẵn ( 1 i1! · 1 i2! · · · 1 ik! ) Xét khai triển et(chx−1) 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)q x q q!  = ∞∑ m=1 x2m (2m)! 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): k P 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! 48 = ∞∑ n=0 [ n∑ k=1 En,kt k ] xn n! = ∞∑ n=0 Pn(t) xn n! Đẳng thức et(chx−1) = ∞∑ n=0 Pn(t) xn n! cho ta kết luận et(chx−1) là hàm sinh mũ của dãy {Pn(t)}∞n=0 (ii) Cũng theo bổ đề 3.1, On,k = n! k! ∑ (i1,i2,...,ik): k P j=1 ij=n ij≥1;ij :lẻ ( 1 i1! · 1 i2! · · · 1 ik! ) Xét khai triển hàm et.shx ta có: shx = ex − e−x 2 = 1 2  ∞∑ p=1 xp p! − ∞∑ q=1 (−1)q x 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): k P 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! 49 Đẳng thức et(shx) = ∞∑ n=0 Qn(t) xn n! cho ta kết luận et.shx là hàm sinh mũ của dãy {Qn(t)}∞n=0. Bằng phương pháp hàm sinh ta chứng minh được mệnh đề cho công thức tính số Pn và Qn dưới đây. Mệnh đề 3.3. Ta có các công thức sau đây (i) Pn = 1 e ∞∑ k=0 1 2kk! k∑ j=0 Cjk(k − 2j)n (3.3) (ii) Qn = ∞∑ k=0 1 2kk! k∑ j=0 (−1)jCjk(k − 2j)n (3.4) Chứng minh. (i) Theo mệnh đề 3.2, et(chx−1) là hàm sinh mũ của dãy {Pn(t)}∞n=0. Do đó ta có thể viết et(chx−1) = ∞∑ n=0 Pn(t) xn n! . Mặt khác, etchx = ∞∑ k=0 tk 2kk! (ex + e−x)k = ∞∑ k=0 tk 2kk! k∑ j=0 Cjke −jxe(k−j)x = ∞∑ k=0 tk 2kk! k∑ j=0 Cjke (k−2j)x = ∞∑ k=0 tk 2kk! k∑ j=0 Cjk ∞∑ n=0 (k − 2j)nx n n! = ∞∑ n=0  ∞∑ k=0 tk 2kk! k∑ j=0 Cjk(k − 2j)n  xn n! Suy ra et(chx−1) = e−t ∞∑ n=0  ∞∑ k=0 tk 2kk! k∑ j=0 Cjk(k − 2j)n  xn n! = ∞∑ n=0 e−t ∞∑ k=0 tk 2kk! k∑ j=0 Cjk(k − 2j)n  xn n! 50 Do đó Pn(t) = e −t ∞∑ k=0 tk 2kk! k∑ j=0 Cjk(k − 2j)n. Cho t = 1 ta được Pn(1) = e−1 ∞∑ k=0 1 2kk! k∑ j=0 Cjk(k − 2j)n. Hơn nữa Pn(1) = n∑ k=1 En,k = Pn. Do đó Pn = 1 e ∞∑ k=0 1 2kk! k∑ j=0 Cjk(k − 2j)n. (ii) Theo mệnh đề 3.2, et.shx là hàm sinh mũ của dãy {Qn(t)}∞n=0. Tức là et.shx = ∞∑ n=0 Qn(t) xn n! .Mặt khác et.shx = ∞∑ k=0 tk 2kk! (ex − e−x)k = ∞∑ k=0 tk 2kk!  k∑ j=0 (−1)jCjke−jxe(k−j)x  = ∞∑ k=0 tk 2kk!  k∑ j=0 (−1)jCjke(k−2j)x  = ∞∑ k=0 tk 2kk!  k∑ j=0 (−1)jCjk ( ∞∑ n=0 (k − 2j)nx n n! ) = ∞∑ n=0  ∞∑ k=0 tk 2kk!  k∑ j=0 (−1)jCjk(k − 2j)n  xn n! Do đó Qn(t) = ∞∑ k=0 tk 2kk! k∑ j=0 (−1)jCjk(k − 2j)n (3.5) Cho t = 1 ta được Qn(1) = ∞∑ k=0 1 2kk! k∑ j=0 (−1)jCjk(k − 2j)n Hơn nữa Qn(1) = n∑ k=0 On,k. Do đó Qn = ∞∑ k=0 1 2kk! k∑ j=0 (−1)jCjk(k − 2j)n. 51 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; ( [7], tr 609) thì ta thấy rằng Qn(t) = ∞∑ k=n tk 2kk! k∑ j=0 (−1)jCjk(k − 2j)n (3.6) Do đó công thức cho Qn trong mệnh đề 3.3 có thể viết lại như sau: Qn = ∞∑ k=n 1 2kk! k∑ j=0 (−1)jCjk(k − 2j)n Trong phần trước ta đã biết đến số Bell Bn. Một điều rất thú vị là giữa số Bell và các số Pn, Qn có mối liên hệ với nhau. Mệnh đề 3.4. Ta có Bn = n∑ k=0 CknPkQn−k. (3.7) Chứng minh. Trong ví dụ 2.7 (chương 2), ta đã đặt en(t) = n∑ k=0 Sn,kt k và đã chứng minh được rằng et(e x−1) là hàm sinh của dãy {en(t)}∞n=0, tức là et(e x−1) = ∞∑ n=0 en(t) xn n! . Theo mệnh đề 3.2, et(chx−1) là hàm sinh của dãy {Pn(t)}∞n=0 và et.shx là hàm sinh của dãy {Qn(t)}∞n=0. Để ý rằng et(e x−1) = et(chx−1).etshx ( Vì chx − 1 + shx = e x + e−x 2 − 1 + ex − e−x 2 = ex − 1) ) . Do đó ∞∑ n=0 en(t) xn n! = ( ∞∑ n=0 Pn(t) xn n! )( ∞∑ n=0 Qn(t) xn n! ) = ∞∑ n=0 ( n∑ k=0 CknPk(t)Qn−k(t) ) xn n! (3.8) 52 Suy ra en(t) = n∑ k=0 CknPk(t)Qn−k(t) Thay t = 1 vào đẳng thức trên ta nhận được en(1) = n∑ k=0 CknPk(1)Qn−k(1) Hơn nữa, en(1) = n∑ k=0 Sn,k = Bn;Pk(1) = Pk;Qn−k(1) = Qn−k. Do đó Bn = n∑ k=0 CknPkQn−k . Ta có điều cần chứng minh. Như vậy, với các công thức (3.3) và (3.4) ta có thể tính được số phân hoạch chẵn và số phân hoạch lẻ của một tập hữu hạn cho trước. Tuy nhiên, việc tính toán với các công thức trên tương đối phức tạp. Vấn đề đặt ra: Tìm phương pháp đơn giản hơn để xác định các số phân hoạch chẵn và số phân hoạch lẻ của một tập hữu hạn. Ta biết rằng Pn = n∑ k=0 En,k và Qn = n∑ k=0 On,k. Do đó, nếu xác định được các số phân hoạch thành k tập chẵn(En,k) và số phân hoạch thành k tập lẻ (On,k) thì có thể xác định được Pn và Qn. Sau đây, chúng ta sẽ thiết lập các công thức truy hồi cho các số En,k và On,k. Trước hết ta có các trường hợp đơn giản sau. Mệnh đề 3.5. Ta có (i) E2m,2 = 2 2(m−1) − 1 (ii) E2m,m = (2m− 1)!! 53 Chứng minh. (i) Mỗi cách phân hoạch tập 2m phần tử thành hai tập con không rỗng gồm hai bước : + Bước 1 : Chọn 2j phần tử từ 2m phần tử cho tập thứ nhất, có C2j2m cách. + Bước 2 : Chọn 2m− 2j phần tử còn lại cho tập thứ hai, có 1 cách. Do j có thể nhận các giá trị 1, 2, ...,m− 1 và số cách chọn ứng với mỗi j được tính 2 lần nên ta có E2m,2 = 1 2 m−1∑ j=1 C2j2m Khai triển nhị thức (1 + x)2m sau đó cho x = 1, x = −1 ta nhận được E2m,2 = 1 2 m−1∑ j=1 C2j2m = 2 2(m−1) − 1 (ii) Ta có E2m,m = 1 m! C22mC 2 2m−2 · · ·C24C22 = 1 m! · (2m)! 2!(2m− 2)! · (2m− 2)! 2!(2m− 4)! · · · 4! 2!2! 2! 2! = 1 m! · (2m)! 2m = (2m− 1)!! . Mệnh đề 3.6. Ta có (i) O2n,2 = 2 2(n−1) (3.9) (ii) On,n−2 = C3n = n(n− 1)(n− 2) 6 , n ≥ 4 (3.10) Chứng minh. (i) Lập luận tương tự như cách tính E2n,2 ta cũng có được công thức O2n,2 = 1 2 n∑ j=1 C2j−12n = 2 2(n−1) (ii) Khi phân hoạch tập n phần tử thành n− 2 tập con không rỗng mà mỗi tập có số lẻ phần tử thì sẽ có một tập có 3 phần tử và n− 3 tập còn lại mỗi tập có 54 một phần tử. + Có C3n cách chọn 3 phần tử để tạo thành một tập có 3 phần tử. + Có duy nhất một cách phân hoạch n−3 phần tử thành n−3 tập không rỗng, mỗi tập có 1 phần tử. Do đó theo quy tắc nhân ta có On,n−2 = C3n = n(n− 1)(n− 2) 6 , n ≥ 4. Tiếp theo ta chứng minh công thức truy hồi cho các số Pn,k và Qn,k. Mệnh đề 3.7. Ta có E2n+2,k+1 = E2n,k + (k + 1)E2n,k+1 + n∑ j=1 C2j2n(E2j+2,2 − 1 − 2E2j,2)E2n−2j,k−1, ∀n ∈ N,∀k ∈ N. (3.11) Chứng minh: Xét phép phân hoạch tập có 2n+2 phần tử thành k+1 tập con không rỗng sao cho mỗi tập con có số chẵn phần tử. Ta xem tập gồm 2n+2 phần tử như là tập có 2n phần tử và thêm vào hai phần tử mới a và b. Tùy theo sự có mặt của a và b trong các tập con của phép phân hoạch mà ta có các trường hợp sau : a) Trường hợp 1: {a, b} là một tập con riêng lẻ của phép phân hoạch. Khi đó, số phép phân hoạch xét trên bằng số phép phân hoạch tập 2n phần tử thành k tập con, mỗi tập con có chẵn phần tử. Tức là bằng E2n,k cách. b) Trường hợp 2: Cả a và b cùng có mặt trong một tập con (với các phần tử khác trong 2n phần tử còn lại) của phép phân hoạch. Có E2n,k+1 cách phân hoạch tập 2n phần tử thành k+1 tập. Với mỗi cách phân hoạch như thế, a và b có thể nằm trong một tập bất kì trong số k + 1 tập của phép phân hoạch. Do đó, có tất cả là (k + 1)E2n,k+1 cách phân hoạch. c) Trường hợp 3: a và b có mặt trong hai tập khác nhau trong số (k + 1) tập con của phép phân hoạch. Gọi 2j + 2 là số phần tử của cả hai tập chứa a và b ( bao gồm cả a và b, j = 1, 2, ...n). Ta tìm số cách phân hoạch tập gồm 2j + 2 phần tử này thành 2 tập con có chẵn phần tử, sao cho a và b nằm trong hai tập khác nhau. + Gọi A là tập tất cả các phép phân hoạch tập 2j +2 phần tử thành 2 tập con 55 có chẵn phần tử. Khi đó |A| = E2j+2,2. + A1 = {f ∈ A : {a, b} là một tập của phép phân hoạch f} =⇒ |A1| = 1. + A2 = {f ∈ A : a và b cùng với các phần tử khác tạo thành một tập của phép phân hoạch f} =⇒ |A2| = 2E2j,2. + A3 = {f ∈ A : a và b nằm trong hai tập khác nhau của phép phân hoạch f}. Rõ ràng A = A1 ∪ A2 ∪ A3 và Ai ∩ Aj = ∅ ∀i 6= j; i, j ∈ {1, 2, 3}. Do đó |A| = |A1| + |A2| + |A3| =⇒ |A3| = |A| − |A1| − |A2| = E2j+2,2 − 1 − 2E2j,2. Như vậy, số phép phân hoạch tập có 2j + 2 phần tử này thành 2 tập con có chẵn phần tử, sao cho a và b nằm trong hai tập khác nhau là E2j+2,2−1−2E2j,2. Khi đó, 2n− 2j phần tử còn lại phải được phân hoạch thành k− 1 tập con, mỗi tập có chẵn phần tử và số cách phân hoạch là E2n−2j,k−1. Hơn nữa, Với mỗi j = 1, 2, 3, ..., n ta có C2j2n cách chọn 2j phần tử từ 2n phần tử. Do đó, số cách phân hoạch trong trường hợp 3 là n∑ j=1 C2j2n(E2j+2,2 − 1 − 2E2j,2)E2n−2j,k−1 Từ ba trường hợp trên, ta có điều cần chứng minh. Mệnh đề 3.8. Ta có On+2,k+1 = (k + 1)On,k+1 + n 2  ∑ j=0 C2jn (O2j+2,2 − 2O2j,2)On−2j,k−1, (3.12) trong đó ký hiệu [x] dùng để chỉ phần nguyên của x. Chứng minh. Ta thấy rằng O2n,1 = 0, O2n+1,1 = 1, O2n+1,2 = 0. Để thiết lập công thức (3.12), ta xem tập n + 2 phần tử như là tập ban đầu có n phần tử và thêm vào hai phần tử mới, giả sử đó là a và b. Tùy theo sự phân bố của a và b trong các tập con của phép phân hoạch, ta có các trường hợp sau. 56 a) Trường hợp 1: a và b cùng với các phần tử khác tạo thành một tập của phép phân hoạch. Có On,k+1 cách phân hoạch tập có n phần tử thành k+1 tập. Do a và b có thể nằm trong một tập bất kì trong số k + 1 tập đó nên có tất cả là (k + 1)On,k+1 cách. b) Trường hợp 2: a và b nằm trong hai tập khác nhau. Gọi 2j + 2 là số phần tử của cả hai tập này ( bao gồm cả a và b). Ta phân hoạch tập gồm 2j+2 phần tử này thành 2 tập con mà mỗi tập có số lẻ phần tử. + Gọi B là tập tất cả các phân hoạch tập 2j + 2 phần tử thành 2 tập con mà mỗi tập có số lẻ phần tử. Khi đó |B| = O2j+2,2. + Gọi B1 = {f ∈ B :a và b cùng với các phần tử khác tạo thành một tập của phép phân hoạch f}. Khi đó |B1| = 2O2j,2. + Gọi B2 = {f ∈ B : a và b nằm trong hai tập khác nhau của phép phân hoạch f}. Rõ ràng B = B1 ∪B2 và B1 ∩B2 = ∅. Suy ra |B2| = |B| − |B1| = O2j+2,2 − 2O2j,2. Do đó số cách phân hoạch tập gồm 2j +2 phần tử thành 2 tập con sao cho mỗi tập có số lẻ phần tử mà a và b nằm trong hai tập khác nhau là O2j+2,2 − 2O2j,2. Khi đó, n − 2j phần tử còn lại được phân hoạch thành k − 1 tập con sao cho mỗi tập có số lẻ phần tử, có On−2j,k−1 cách. Hơn nữa, có C2jn cách chọn 2j phần tử từ n phần tử. Do mỗi tập có số lẻ phần tử nên {a}, {b} cũng có thể là các tập, vì vậy j nhận các giá trị là 0, 1, ..., [n 2 ] . Do đó số cách phân hoạch trong trường hợp 2 là n 2  ∑ j=0 C2jn (O2j+2,2 − 2O2j,2)On−2j,k−1 Từ hai trường hợp a) và b) ta có On+2,k+1 = (k + 1)On,k+1 + n 2  ∑ j=0 C2jn (O2j+2,2 − 2O2j,2)On−2j,k−1. Từ các kết quả trên ta có thể tính truy hồi cho các số phân hoạch chẵn và lẻ. Dưới đây là bảng số phân hoạch chẵn (lẻ) cho các giá trị n, k đầu tiên. 57 58 * Bảng các phân hoạch chẵn : En,k k=0 k=1 k= 2 k=3 k=4 k=5 k=6 k=7 k=8 Pn n=0 1 1 n=1 0 0 0 n=2 0 1 0 1 n=3 0 0 0 0 0 n=4 0 1 3 0 0 4 n=5 0 0 0 0 0 0 0 n=6 0 1 15 15 0 0 0 31 n=7 0 0 0 0 0 0 0 0 0 n=8 0 1 63 210 105 0 0 0 0 379 * Bảng các phân hoạch lẻ : On,k k=0 k=1 k= 2 k=3 k=4 k=5 k=6 k=7 k=8 Qn n=0 1 1 n=1 0 1 1 n=2 0 0 1 3 n=3 0 1 0 1 2 n=4 0 0 4 0 1 5 n=5 0 1 0 10 0 1 12 n=6 0 0 16 0 20 0 1 37 n=7 0 1 0 91 0 35 0 1 128 n=8 0 0 64 0 366 0 56 0 1 457 Mệnh đề sau đây cho ta mối liên hệ giữa các số Sn,k, En,k và On,k. 59 Mệnh đề 3.9. Sn,k = k∑ j=0 n∑ i=0 CinEi,jOn−i,k−j . Chứng minh. Trong số n phần tử phân hoạch thành k tập con không rỗng, gồm có i phần tử được phần hoạch chẵn thành j tập con không rỗng và n− i phần tử được phần hoạch lẻ thành k−j tập con không rỗng, ở đây i = 0, 1, · · · , n và j = 0, 1, · · · , k. Do đó ta có Sn,k = k∑ j=0 n∑ i=0 CinEi,jOn−i,k−j . Từ kết quả mệnh đề 4.9 ta suy ra hệ quả sau. Hệ quả 3.10. Bn = n∑ k=0 Sn,k = n∑ k=0 k∑ j=0 n∑ i=0 CinEi,jOn−i,k−j . Sau đây chúng tôi đưa ra một vài ví dụ thực tế, mang tính chất áp dụng, liên quan đến vấn đề tính số phân hoạch chẵn và số phân hoạch lẻ một tập hữu hạn. Ví dụ 3.1. Phân phối n quả cầu phân biệt vào m hộp giống nhau. Có bao nhiêu cách phân phối sao cho mỗi hộp có chứa một số chẵn quả cầu và bao nhiêu cách phân phối sao cho mỗi hộp có chứa một số lẻ quả cầu? Chứng minh. Vì các quả cầu là phân biệt nhau và các hộp là giống nhau nên số cách phân phối để mỗi hộp có một số chẵn (lẻ) phần tử bằng số cách phân hoạch tập n phần tử thành m tập con sao cho mỗi tập có một số chẵn (lẻ) phần tử. Do đó số cách phân phối sao cho mỗi hộp có chứa một số chẵn quả cầu sẽ bằng En,m cách và số cách phân phối sao cho mỗi hộp có chứa một số lẻ quả cầu sẽ bằng On,m cách. 60 Ví dụ 3.2. Phân phối n quả cầu phân biệt vào k hộp phân biệt. Có bao nhiêu cách phân phối sao cho mỗi hộp có chữa một số chẵn quả cầu và có bao nhiêu cách phân phối sao cho mỗi hộp có chứa một số lẻ quả cầu?. Chứng minh. Giả sử các hộp là giống nhau. Theo bài trên, số cách phân phối sao cho mỗi hộp có chứa một số chẵn quả cầu bằng En,k và số cách phân phối sao cho mỗi hộp có chứa một số lẻ quả cầu sẽ bằng On,k. Với mỗi cách phân phối này, bằng cách hoán vị, mỗi lần hoán vị ta sẽ được một phân phối vào k hộp khác nhau. Do đó, số cách phân phối n quả cầu phân biệt vào k hộp phân biệt sao cho mỗi hộp có chứa một số chẵn quả cầu bằng k!En,k và số cách phân phối n quả cầu phân biệt vào k hộp phân biệt sao cho mỗi hộp có chứa một số lẻ quả cầu sẽ bằng k!On,k. Ví dụ 3.3. Có bao nhiêu cách phân phối 5 đồ vật khác nhau vào 3 hộp giống nhau sao cho mỗi hộp chứa một số chẵn đồ vật?. Có bao nhiêu cách phân phối 5 đồ vật khác nhau vào 3 hộp giống nhau sao cho mỗi hộp chứa một số lẻ đồ vật?. Chứng minh. Vì các đồ vật là khác nhau và các hộp là giống nhau nên số cách phân phối 5 đồ vật khác nhau sao cho mỗi tập có một số chẵn phần tử vào 3 hộp khác nhau bằng số cách phân hoạch tập có 5 phần tử phân biệt thành 3 tập con sao cho mỗi tập con có một số chẵn phần tử và bằng E5,3 = 0. Tương tự, số cách phân phối 5 đồ vật khác nhau vào 3 hộp giống nhau sao cho mỗi hộp có một số lẻ phần tử bằng O5,3 = 10. Ví dụ 3.4. Trong một giải bóng đá, tại vòng 1/8 ban tổ chức cần chia các 16 đội thành 8 cặp thi đấu và các đội tiến hành bốc thăm. Hỏi có bao nhiêu trường hợp như thế?. Chứng minh. Số trường hợp các đội bắt thăm chính là số phân hoạch tập gồm có 8 phần tử phân biệt thành 4 tập con không rỗng sao cho mỗi tập con có chẵn phần tử. Do đó số trường hợp các đội bốc thăm được sẽ là E16,8 = 15!! = 2027025. 61 Ví dụ 3.5. Có 20 vận động viên trong một cuộc thi đấu cầu lông. Ban tổ chức cần chia các vận động viên thành 10 cặp thi đấu. Hỏi ban tổ chức có bao nhiêu cách chia ?. Chứng minh. Số cách chia 20 vận động viên thành 10 cặp thi đầu chính là số phân hoạch tập 20 phần tử thành 10 tập con sao cho mỗi tập con có một số chẵn phần tử. Do đó số cách chia sẽ bằng E20,10 = 19!! = 654729075. 62 kết luận Trong luận văn, chúng tôi đã trình bày một số vấn đề sau đây 1. Các quy tắc đếm, một số bài toán đếm cơ bản và một số kết quả liên quan đến vấn đề số phân hoạch của một tập hợp hữu hạn thành các tập con không rỗng (số Stirling loại 2, số Bell). 2. Khái niệm về hàm sinh, hàm sinh mũ và các ví dụ điển hình mà trong đó áp dụng kỹ thuật hàm sinh, hàm sinh mũ để giải quyết chúng. 3. Công thức ngược và áp dụng công thức ngược để thiết lập công thức sàng. 4. Chứng minh được công thức tính tổng số phần tử của một tập hữu hạn X mà chứa trong một số chẵn (hay một số lẻ) các tập con cho trước của X. 5. Thiết lập công thức tính trực tiếp cho số phân hoạch chẵn Pn và số phân hoạch lẻ Qn. 6. Chỉ ra được hệ thức liên hệ giữa số phân hoạch chẵn Pn, số phân hoạch lẻ Qn và Số Bell Bn. 7. Bằng lập luận sơ cấp chứng minh được công thức tính truy hồi cho số En,k, On,k và chỉ ra được mối liên với số Stirling loại 2 - Sn,k. Sau cùng là một số bài tập áp dụng. 63 Tài liệu tham khảo [1] Lê Hạnh (1995), 120 Bài tập giải tích tổ hợp, NXB Giáo Dục, TPHCM. [2] Vũ Đình Hoà (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] Ngô Thúc Lanh (1998), Tìm hiểu đại số tổ hợp phổ thông, NXB Giáo Dục, 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, Hà Nội. [5] Hoàng Chí thành, (2001), Giáo trình tổ hợp, NXB Đại Học Quốc Gia Hà Nội. [6] Martin Aigner (1997), Combinatorial Theory, Spring Verlag, Berlin Hei- delberg. [7] Proudnikov et al (1981), Intergrals and Series of Elementary Functions, Nauka, Moscou, (In Russian). [8] Richard P.Stanley (2001), Enumerative Combinatorics, Cambridge Univer- sity Press, 2001. [9] Karl H.Wehrhahn (1992), Combinatorics An Introductin, Carslaw Publi- cations, Australia.