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

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG…………………….  Luận văn tốt nghiệp Các số tổ hợp liên quan đến số các phân hoạch 1Mục lục mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1 Một số bài toán đếm và các số tổ hợp 5 1.1 Một số quy tắc đếm cơ bản . . . . . . . . . . . . . . . . . . . . 5 1.1.1 Quy tắc tương ứng một-một . . . . . . . . . . . . . . . . 5 1.1.2 Quy tắc cộng . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.3 Quy tắc nhân . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 Một số bài toán đếm cơ bản . . . . . . . . . . . . . . . . . . . . 6 1.2.1 Chỉnh hợp có lặp . . . . . . . . . . . . . . . . . . . . . . 6 1.2.2 Chỉnh hợp không lặp . . . . . . . . . . . . . . . . . . . . 7 1.2.3 Hoán vị . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.4 Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.5 Phân hoạch tập hợp. Số Stirling loại hai và số Bell . . 8 1.3 Một vài ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3.1 Bài toán tính số nghiệm của phương trình . . . . . . . 10 1.3.2 Bài toán đếm tất cả các hàm từ một tập hữu hạn vào một tập hữu hạn . . . . . . . . . . . . . . . . . . . . . . 11 1.3.3 Bài toán đếm tất cả các hàm đơn ánh từ một tập hữu hạn vào một tập hữu hạn . . . . . . . . . . . . . . . . . 12 1.3.4 Bài toán đếm tất cả các hàm toàn ánh từ một tập hữu hạn lên một tập hữu hạn . . . . . . . . . . . . . . . . . 13 21.4 Sự mở rộng về số các phân hoạch . . . . . . . . . . . . . . . . . 17 1.5 Một số kết quả về số Stirling loại một . . . . . . . . . . . . . . 29 2 Phương pháp đếm dùng hàm sinh 37 2.1 Phương pháp đếm dùng hàm sinh thông thường . . . . . . . . 37 2.2 Phương pháp đếm dùng hàm sinh mũ . . . . . . . . . . . . . . 48 3 Một số phương pháp và kỹ thuật đếm cơ bản khác 63 3.1 Phương pháp đếm bằng nguyên lý bao hàm và loại trừ. . . . . 63 3.2 Phương pháp đếm bằng công thức ngược . . . . . . . . . . . . 69 3.2.1 Công thức nghịch đảo nhị thức . . . . . . . . . . . . . . 72 3.2.2 Công thức nghịch đảo Stirling . . . . . . . . . . . . . . . 73 4 Dãy nhị thức 75 4.1 Khái niệm về dãy nhị thức . . . . . . . . . . . . . . . . . . . . . 75 4.2 Biểu diễn dãy nhị thức . . . . . . . . . . . . . . . . . . . . . . . 75 4.3 Dãy nhị thức sinh bởi một hàm số . . . . . . . . . . . . . . . . 79 4.4 Một số ví dụ về dãy nhị thức . . . . . . . . . . . . . . . . . . . 81 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 3mở đầu Tổ hợp như là một lĩnh vực của toán học rời rạc, xuất hiện vào đầu thế kỷ 17 bằng một loạt các công trình nghiên cứu của các nhà toán học xuất sắc như Pascal, Fermat, Leibnitz, Euler.... Mặc dù vậy, tổ hợp vẫn là lĩnh vực mờ nhạt và ít được chú ý tới trong quãng thời gian hơn hai thế kỷ. Tình thế bắt đầu đổi khác khi xuất hiện các máy tính và cùng với nó là sự phát triển của toán hữu hạn. Hiện nay lý thuyết tổ hợp được áp dụng trong nhiều lĩnh vực khác nhau như lý thuyết số, hình học hữu hạn, quá trình ngẫu nhiên, thống kê xác suất,... Hướng nghiên cứu của luận văn là xây dựng các số tổ hợp cơ bản được hình thành từ kết quả của một số bài toán đếm. Chúng tôi xét bài toán phân hoạch tập hợp hữu hạn cùng với các điều kiện được đặt thêm vào. Trên cơ sở đó luận văn đi đến một số kết quả mới về các số tổ hợp có liên quan đến số các phân hoạch. Luận văn được chia làm 4 chương: Chương 1: Một số bài toán đếm và các số tổ hợp. Chương này nhắc lại một số quy tắc và bài toán đếm cơ bản. Thông qua một số bài toán đếm, luận văn xây dựng các số tổ hợp cơ bản. Hơn nữa, thông qua bài toán phân hoạch tập hợp, chúng tôi tìm được các số tổ hợp mới cũng như 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. Chương 2: Phương pháp đếm dùng hàm sinh. Nội dung chính của chương là giới thiệu phương pháp đếm dùng hàm sinh thông thường và hàm sinh mũ. Với phương pháp này, luận văn giải quyết một số bài toán đếm cũng như thiết lập được công thức tính cho các số tổ hợp quan trọng (số xáo trộn tổng quát Dn, số Fibonaci Fn, số Bell Bn,...). Hơn nữa, chúng tôi cũng đưa ra hàm sinh mũ cho các số tổ hợp mới vừa tìm được trong Chương 1. 4Chương 3: Một số phương pháp và kỹ thuật đếm cơ bản khác. Chúng tôi giới thiệu thêm hai phương pháp đếm cơ bản: 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 thiết lập 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. Chương 4: Dãy nhị thức. Sau khi trình bày sơ lược về dãy nhị thức, chúng tôi chứng minh 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. Tuy có nhiều cố gắng nhưng kết quả của luận văn vẫn còn nhiều hạn chế, nội dung và cách trình bày khó tránh khỏi thiếu sót, tác giả rất mong nhận được sự góp ý của các thầy cô giáo và các bạn đồng nghiệp để nâng cao hơn nữa chất lượng của luận văn. Quy Nhơn, tháng 2 năm 2008 Đoàn Nhật Thịnh 5Chương 1 Một số bài toán đếm và các số tổ hợp Trong chương này ta sẽ nhắc lại một số kiến thức cơ bản về tổ hợp. Thông qua một số bài toán ta sẽ tìm hiểu các số tổ hợp cơ bản đã biết, đồng thời tìm ra các số tổ hợp mới. 1.1 Một số quy tắc đếm cơ bản 1.1.1 Quy tắc tương ứng một-một Nếu tồn tại tương ứng một -một giữa các phần tử của các tập hữu hạn A1 và A2 thì A1 và A2 có cùng số phần tử. 1.1.2 Quy tắc cộng Nếu A1, A2,..., An là các tập hữu hạn đôi một rời nhau thì |A1 ∪A2 ∪ ... ∪An| = |A1|+ |A2|+ · · · + |An| ở đây |Ai| là số phần tử của tập Ai. 61.1.3 Quy tắc nhân Nếu A1, A2,..., An là các tập hữu hạn bất kỳ và A1×A2× · · ·×An là tích Descartes của các tập đó thì |A1 ×A2 × · · · × An| = |A1| × |A2| × · · · × |An|. Quy tắc cộng và quy tắc nhân cũng thường được phát biểu dưới dạng tương ứng dưới đây: Quy tắc cộng: Giả sử ta có n hành động loại trừ lẫn nhau H1,H2,...,Hn, tức là không thể xảy ra hai hành động đồng thời. Ta cũng giả sử rằng hành động Hi có ai cách thực hiện. Khi đó hành động H: hoặc H1 xảy ra, hoặc H2 xảy ra,..., hoặc Hn xảy ra, có cả thảy a1 + a2 + · · · + an cách thực hiện. Quy tắc nhân: Giả sử một hành động H bao gồm n giai đoạn kế tiếp và độc lập với nhau, trong đó giai đoạn thứ i là hành động Hi. Ta cũng giả sử rằng hành động Hi có ai cách thực hiện. Khi đó hành động H có cả thảy a1a2...an cách thực hiện. 1.2 Một số bài toán đếm cơ bản 1.2.1 Chỉnh hợp có lặp Định nghĩa 1.2.1. Một chỉnh hợp lặp chập k của n phần tử là một bộ có thứ tự gồm k thành phần lấy từ n phần tử đã cho. Các thành phần có thể được lặp lại. Như thế, một chỉnh hợp lặp chập k của n có thể xem như một phần tử của tích Descartes Ak với A là tập gồm n phần tử đã cho. Theo quy tắc nhân, số tất cả các chỉnh hợp lặp chập k của n sẽ là U(n, k) = nk. 71.2.2 Chỉnh hợp không lặp Định nghĩa 1.2.2. Một chỉnh hợp không lặp chập k của n phần tử là một bộ có thứ tự gồm k thành phần lấy từ n phần tử đã cho. Các thành phần không được lặp lại. Ta thường dùng ký hiệu Akn hay (n)k để chỉ số chỉnh hợp không lặp chập k của n phần tử. Chỉnh hợp không lặp thường được gọi tắt là chỉnh hợp. Để xây dựng một chỉnh hợp không lặp, ta xây dựng dần từ thành phần đầu tiên. Thành phần này có n khả năng chọn. Mỗi thành phần tiếp theo, số khả năng chọn giảm đi 1 so với thành phần đứng trước. Từ đó, theo quy tắc nhân, số chỉnh hợp không lặp chập k của n sẽ là Akn = n(n− 1)...(n− k + 1) = n! (n− k)! · Để tồn tại chỉnh hợp, cần phải thỏa mãn k ≤ n. Ta quy ước A k n = 0 nếu k > n. 1.2.3 Hoán vị Định nghĩa 1.2.3. Ta gọi một hoán vị của n phần tử là một cách xếp thứ tự các phần tử đó. Một hoán vị của n phần tử được xem như một trường hợp riêng của chỉnh hợp không lặp khi k = n. Do đó số hoán vị của n phần tử là Pn = n! Có thể đồng nhất một hoán vị của n phần tử với một song ánh của một tập n phần tử lên chính nó. Một song ánh như vậy còn được gọi là một phép thế. 1.2.4 Tổ hợp Định nghĩa 1.2.4. Một tổ hợp chập k của n phần tử là một bộ không kể thứ tự gồm k thành phần khác nhau lấy từ n phần tử đã cho. Nói cách khác, 8ta có thể coi một tổ hợp chập k của n phần tử là một tập con k phần tử của nó. Ta thường ký hiệu số các tổ hợp chập k của n phần tử là Ckn. Để tính Ckn ta có thể lập luận như sau: Mỗi chỉnh hợp chập k của n phần tử của tập A có thể coi là một cách thực hiện của hành động H "tạo ra chỉnh hợp" bao gồm hai giai đoạn kế tiếp H1 và H2 sau đây: Giai đoạn H1: Tạo ra tập con lực lượng k của A. Theo định nghĩa của tổ hợp, ta thấy ngay rằng có Ckn cách thực hiện giai đoạn H1. Giai đoạn H2: Tạo ra chỉnh hợp chập k của k phần tử của mỗi tập con được tạo ra ở giai đoạn H1. Ta có Akk = k! cách thực hiện giai đoạn H2. Theo quy tắc nhân ta có Akn = C k n.k!. Suy ra C k n = Akn k! . Vì vậy Ckn =   n! (n− k)! : k! = n! k!(n− k)! nếu 1 ≤ k ≤ n 0 nếu k > n. Như đã nói ở trên, mỗi tổ hợp chập k của n phần tử của A có thể được xem như là một tập con lực lượng k của A. Với k = 0, vì chỉ có một tập con của A lực lượng 0 là tập rỗng, nên ta có thể định nghĩa một cách tự nhiên rằng C0n = 1. Khi đó đẳng thức C k n = n! k!(n− k)! cũng đúng cho cả k = 0. 1.2.5 Phân hoạch tập hợp. Số Stirling loại hai và số Bell Định nghĩa 1.2.5. (theo [8, 4]) Cho A là một tập hữu hạn có n phần tử. Một phân hoạch của A thành k phần (khối) là một hệ gồm các tập con không rỗng A1, A2, ..., Ak của A thỏa mãn hai tính chất sau: a) A1 ∪A2 ∪ ... ∪Ak = A, b) Ai ∩Aj = ∅ ∀i 6= j i, j ∈ {1, 2, ..., k}. Mỗi tập con Ai được gọi là một phần (khối) của phép phân hoạch. Số tất cả 9các phân hoạch thành k phần của A được gọi là số Stirling loại hai và được ký hiệu là Sn,k. Dễ thấy rằng Sn,k = 0 nếu k > n và với mọi n ≥ 1 ta có: Sn,0 = 0, Sn,1 = 1, Sn,n = 1. Ta cũng thừa nhận rằng S0,0 = 1 vì theo định nghĩa họ rỗng các khối là phân hoạch của tập rỗng. +) Số Bn = Sn,0 + Sn,1 + · · ·+ Sn,n được gọi là số Bell thứ n. Như vậy, số Bell thứ n là số tất cả các phân hoạch của tập A lực lượng n. Ví dụ: Các phân hoạch của tập A = {a, b, c, d} thành ba khối là: {{a}, {b}, {c, d}}; {{a}, {b, c}, {d}}; {{a}, {b, d}, {c}} {{b}, {a, c}, {d}}; {{b}, {a, d}, {c}}; {{c}, {a, b}, {d}} Từ ví dụ này ta có S4,3 = 6. Ta có thể tính được các số Sn,k dựa vào hệ thức truy hồi trong định lý sau: Định lý 1.2.1. (theo [3, 1.3]) Ta có Sn+1,k = k.Sn,k + Sn,k−1. Chứng minh: Xét tập bất kì có n+1 phần tử, chẳng hạn tập A = {x1, x2, ..., xn+1}. Theo định nghĩa có Sn+1,k phân hoạch tập A thành k khối. Mặt khác ta có thể chia tập B tất cả các phân hoạch trên thành hai tập con B1 và B2 rời nhau như sau: B1 gồm tất cả các phân hoạch tập A thành k khối, trong đó có một khối là {xn+1}, còn B2 bao gồm tất cả các phân hoạch tập A thành k khối trong đó không có khối nào là {xn+1}. Khi đó mỗi phân hoạch thuộc B1 sẽ chia tập {x1, x2, ..., xn} thành (k − 1) khối và có Sn,k−1 cách chia như thế. Do đó |B1| = Sn,k−1. Nếu {xn+1} không là một khối thì xn+1 sẽ nằm trong một khối với ít nhất một phần tử khác của A. Vì có Sn,k cách phân hoạch tập {x1, x2, ..., xn} thành k khối và xn+1 có thể thuộc một khối bất kì trong k khối đó, nên ta có tất cả là k.Sn,k cách phân hoạch tập A thành k khối sao cho {xn+1} không là một khối của phân hoạch. Do đó |B2| = kSn,k. Vì B = B1∪B2 10 và B1 ∩B2 = ∅ nên theo quy tắc cộng ta có Sn+1,k = |B| = |B1|+ |B2| = Sn,k−1 + kSn,k. Dựa vào hệ thức truy hồi trên, ta tính được các số Sn,k và Bn. Sau đây là bảng cho cụ thể với một vài giá trị n đầu tiên. * Bảng các số Stirling loại hai và số Bell: Sn,k k=0 k=1 k= 2 k=3 k=4 k=5 k=6 k=7 k=8 Bn n=0 1 1 n=1 0 1 1 n=2 0 1 1 2 n=3 0 1 3 1 5 n=4 0 1 7 6 1 15 n=5 0 1 15 25 10 1 52 n=6 0 1 31 90 65 15 1 203 n=7 0 1 63 301 350 140 21 1 877 n=8 0 1 127 966 1701 1050 266 28 1 4140 1.3 Một vài ứng dụng Trong mục này, ta áp dụng các kết quả đếm ở mục trước để giải một số bài toán đếm thường gặp khác. 1.3.1 Bài toán tính số nghiệm của phương trình Bài toán 1.1. Tính số nghiệm nguyên dương của phương trình x1 + x2 + · · ·+ xk = n . 11 Giải: Xét dãy có độ dài n + k − 1 bao gồm n phần tử x và k − 1 số 0 có dạng sau : x · · ·x︸ ︷︷ ︸ x1 0x · · · x︸ ︷︷ ︸ x2 0 · · · 0x . . . x︸ ︷︷ ︸ xk (∗) Trong đó, số kí tự x ở đoạn thứ i (được ngăn cách bởi các số 0) tương ứng là xi, x1 + x2 + · · ·+ xk = n, xi ≥ 1 ∀i = 1, 2, ..., k. Ta thấy rằng có một tương ứng một- một giữa mỗi nghiệm nguyên dương (x1, x2, . . . , xk) của phương trình đã cho với mỗi dãy dạng (*) xác định như trên. Tương ứng này cho ta song ánh từ tập tất cả các nghiệm nguyên dương của phương trình đã cho vào tập tất cả các dãy dạng (*). Mặt khác số các dãy dạng (*) tương ứng với cách chọn k−1 vị trí cho k−1 số 0 (là một tập con k−1 phần tử) của tập hợp n−1 vị trí của dãy dạng (*). Do đó, số các dãy dạng (*) là Ck−1n−1. Vậy số nghiệm nguyên dương của phương trình x1 + x2 + · · ·+ xk = n là Ck−1n−1. Nhận xét : Nếu x1 + x2 + · · ·+ xk = n với x1, x2, ..., xk ≥ 0. Khi đó : (x1 + 1) + (x2 + 1) + · · ·+ (xk + 1) = n + k và (xi + 1) > 0 ∀ i = 1, k. Đảo lại, nếu y1 + y2 + · · ·+ yk = n + k với yj > 0 ∀j = 1, k thì (y1 − 1) + (y2 − 1) + · · · + (yk − 1) = n với yj ≥ 0 ∀j = 1, k. Vì vậy số nghiệm nguyên không âm của phương trình x1 +x2 + · · ·+xk = n là Ck−1n+k−1 = Cnn+k−1. 1.3.2 Bài toán đếm tất cả các hàm từ một tập hữu hạn vào một tập hữu hạn Bài toán 1.2. Giả sử M và N là hai tập hữu hạn với |N | = n và |M | = m. Hãy tìm số các hàm từ N đến M. Giải: Giả sử N = {a1, a2, ..., an}. Khi đó một hàm f : N → M tương ứng với đúng một bộ có thứ tự gồm n thành phần là (f(a1), f(a2), ..., f(an)) với f(a1), f(a2), ..., f(an) ∈ M . Do đó số các hàm từ N đến M bằng số chỉnh hợp 12 có lặp chập n của m phần tử của M , tức là, bằng U(m,n) = mn. Vậy ta có Số tất cả các hàm từ N đến M bằng U(m,n) = mn. 1.3.3 Bài toán đếm tất cả các hàm đơn ánh từ một tập hữu hạn vào một tập hữu hạn Bài toán 1.3. Giả sử M và N là hai tập hữu hạn với |N | = n và |M | = m. Hãy tìm số các hàm đơn ánh từ N đến M. Giải: Giả sử N = {a1, a2, ..., an}. Khi đó một hàm đơn ánh f : N → M tương ứng với đúng một bộ có thứ tự gồm n thành phần là (f(a1), f(a2), ..., f(an)) với f(a1), f(a2), ..., f(an) ∈ M và f(ai) 6= f(aj) nếu i 6= j. Do đó số các hàm đơn ánh từ N đến M bằng số chỉnh hợp chập n của m phần tử của M , tức là bằng Anm. Vậy ta có Số tất cả các hàm đơn ánh từ N đến M bằng Anm. Nói riêng, khi |N | = |M | = m thì một hàm đơn ánh f : N → M cũng là hàm toàn ánh. Do đó, f cũng là song ánh từ N lên M . Ngược lại, mỗi song ánh f : N → M cũng là một hàm đơn ánh từ N vào M . Như vậy, ta có tương ứng một-một giữa các phần tử của tập tất cả các hàm đơn ánh và tập tất cả các hàm song ánh từ N vào M . Vậy ta có: Nếu N và M là các tập hữu hạn với |N | = |M | = m thì số tất cả các hàm song ánh từ N đến M bằng Amm = m!. 13 1.3.4 Bài toán đếm tất cả các hàm toàn ánh từ một tập hữu hạn lên một tập hữu hạn Bài toán 1.4. Giả sử M và N là hai tập hữu hạn với |N | = n và |M | = m. Hãy tìm số các hàm toàn ánh từ N đến M. Giải: Giả sử M = {b1, b2, ..., bm} và f : N → M là một hàm toàn ánh. Ta định nghĩa quan hệ f∼ trên N như sau: a1 f∼ a2 khi và chỉ khi f(a1) = f(a2). Dễ thấy rằng quan hệ f∼ là một quan hệ tương đương trên N . Vì thế mà các lớp tương đương của f∼ tạo thành một phân hoạch của N . Vì f là hàm toàn ánh nên phân hoạch này có đúng m khối. Ta có thể coi phân hoạch đó là tập Nf = {N1, N2, ..., Nm} với các Ni (i = 1, 2, ..., m) là các khối của phân hoạch. Hơn thế nữa hàm f cảm sinh hàm f : N f → M : Ni 7→ f (Ni) = f(ai) với ai ∈ Ni. Dễ thấy rằng f là một song ánh giữa Nf và M . Ngược lại, một phân hoạch N của N thành m khối cùng với một song ánh g : N → M xác định đúng một hàm toàn ánh f : N → M : ai 7→ f(ai) = g([ai]) với [ai] là khối của phân hoạch N chứa ai. Tóm lại, một hàm toàn ánh f : N → M có thể coi là một cách thực hiện hành động H "tạo ra hàm toàn ánh" bao gồm hai giai đoạn H1 và H2 như sau: Giai đoạn H1: Tạo ra một phân hoạch N của N gồm m khối. Theo định nghĩa của số Stirling loại hai, ta có Sn,m cách thực hiện giai đoạn H1. Giai đoạn H2: Với mỗi phân hoạch N tạo ra từ giai đoạn H1, tạo ra một hàm song ánh f : N → M . Như ta đã tính ở Bài toán 1.3, ta có m! cách thực hiện giai đoạn H2. Theo quy tắc nhân, ta có: Số tất cả các hàm toàn ánh từ N đến M bằng m!Sn,m. 14 Bây giờ ta có thể chứng minh một kết quả tổ hợp quan trọng sau đây. Định lý 1.3.1. (theo [3, 1.4]) mn = n∑ k=0 Sn,k(m)k . Chứng minh: Giả sử N và M là các tập hợp với |N | = n và |M | = m và F là tập tất cả các hàm từ N đến M . Ký hiệu Fk = {f ∈ F : |f(N)| = k}, k = 1, 2, ..., m. Khi đó Fi ∩ Fj = ∅ nếu i 6= j và F = F1 ∪ F2 ∪ · · · ∪ Fm. Theo quy tắc cộng, ta có: |F | = |F1|+ |F2|+ · · ·+ |Fm|. Mỗi f ∈ Fk có thể coi là một cách thực hiện hành động H "tạo ra các hàm thuộc Fk" bao gồm hai giai đoạn H1 và H2 như sau: Giai đoạn H1: Tạo ra tập con K ⊆ M lực lượng k. Theo định nghĩa của tổ hợp, ta có Ckm cách thực hiện H1. Giai đoạn H2: Tạo ra một hàm toàn ánh từ N đến K. Theo Bài toán 1.4, có k!.Sn,k cách thực hiện giai đoạn H2. Theo quy tắc nhân ta có |Fk| = Ckm.k!.Sn,k = Sn,k(m)k. Do đó |F | = m∑ k=1 Sn,k(m)k. Theo Bài toán 1.2, ta có |F | = mn. Vì Sn,0 = 0 nếu n > 1, Sn,k = 0 nếu k > n, (m)k = 0 nếu k > m, nên ta nhận được mn = |F | = Sn,0(m)0 + n∑ k=1 Sn,k(m)k = n∑ k=0 Sn,k(m)k . Theo Định lý 1.3.1, 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. 15 Từ đẳng thức này, ta có thể thiết lập được hệ thức truy hồi cho các số Bell được thể hiện trong định lý sau: Định lý 1.3.2. Ta có Bn+1 = n∑ k=0 CknBk, (B0 = 1). Chứng minh: Ta xây dựng phiếm hàm tuyến tính L : R[x] → R xác định bởi (x)k = x(x− 1)...(x− k + 1) 7→ L((x)k) = 1 với mọi k = 0, 1, 2, .... Ta có xn = n∑ k=0 Sn,k(x)k. Do đó L(xn) = n∑ k=0 Sn,kL((x)k) = n∑ k=0 Sn,k = Bn. Ta có (x)n+1 = x(x− 1)....(x− n) = x(x− 1)n. Suy ra L((x)n+1) = L((x)n) = L(x(x− 1)n). Do đó L(p(x)) = L(xp(x− 1)) ∀p(x) ∈ R[x]. Với p(x) = (x + 1)n ta được L((x + 1)n) = L(xn+1) ⇔ n∑ k=0 CknL(x k) = Bn+1 ⇔ n∑ k=0 CknBk = Bn+1. Vậy ta có Bn+1 = n∑ k=0 CknBk . Mệnh đề 1.3.1. Ta có Sn,k = n! k! ∑ (i1,i2,...,ik): kP j=1 ij=n ij≥1 ( 1 i1! · 1 i2! · · · 1 ik! ) . Chứng minh: Ta xét số các hàm toàn ánh từ N đến K với |N | = n và K = {b1, b2, ..., bk}. Theo Bài toán 1.4, số các hàm toàn ánh như trên là k!Sn,k. Bây giờ ta đếm số các hàm toàn ánh theo một cách khác. 16 Giả sử f : N → K là một hàm toàn ánh bất kỳ. Ta đặt Aj = f−1(bj), j = 1, 2, ..., k. Giả sử |Aj| = ij, j = 1, 2, ..., k. Vì f là toàn ánh nên ta có Ai∩Aj = ∅ ∀i 6= j, N = A1∪A2∪· · ·∪Ak, ij ≥ 1 ∀j = 1, k và n = i1+ i2+ · · ·+ ik. Như vậy, để tạo hàm toàn ánh như trên ta có thể thực hiện theo k bước : + Bước 1: Chọn i1 phần tử từ tập N gồm n phần tử là tạo ảnh của b1, có C i1n cách. + Bước 2: Chọn i2 phần tử từ tập gồm n − i1 phần tử còn lại của N là tạo ảnh của b2, có C i2n−i1 cách. ............................................................... + Bước k: Chọn ik phần tử từ tập gồm n− i1 − i2 − · · · − ik−1 phần tử còn lại của N là tạo ảnh của bk, có C ik n−i1−i2−···−ik−1 cách. Theo quy tắc nhân, số các hàm toàn ánh f : N → K mà f(Aj) = bj là C i1n C i2 n−i1 ...C ikn−i1−i2−···−ik−1 = n! i1!i2!...ik! . Vì các số ij thay đổi thỏa mãn n = i1 + i2 + · · ·+ ik, ij ≥ 1 ∀j = 1, k nên số tất cả các hàm toàn ánh từ N đến K là : ∑ (i1,i2,...,ik): kP j=1 ij≥1 ij=n n! i1!i2! . . . ik! Vậy ta nhận được k!Sn,k = ∑ (i1,i2,...,ik): kP j=1 ij≥1 ij=n n! i1!i2! . . . ik! . Từ đây ta suy ra Sn,k = n! k! ∑ (i1,i2,...,ik): kP j=1 ij=n ij≥1 ( 1 i1! · 1 i2! · · · 1 ik! ) . 17 1.4 Sự mở rộng về số các phân hoạch Trong phần này, chúng tôi giới thiệu một số kết quả mới có liên quan đến số các phân hoạch được chứng minh chỉ bằ