Tài liệu 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ẻ

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG…………………….  Luận văn thạc sỹ 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ẻ 1 Mục lục mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Kiến thức chuẩn bị 3 5 1.1 Các quy tắc đếm cơ bản . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Một số bài toán đếm và kết quả tổ hợp cơ bản . . . . . . . . . . 10 1.2.1 Chỉnh hợp - hoán vị - tổ hợp . . . . . . . . . . . . . . . . 10 1.2.2 Phân hoạch của tập hợp. Số Stirling loại hai và số Bell . 13 1.2.3 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 . . . . . . . . . . . . . . . . . . . . . . . 1.2.4 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. . . . . . . . . . . . . . . . . . . 1.2.5 15 16 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 . . . . . . . . . . . . . . . . . . 2 Hàm sinh và công thức sàng 16 20 2.1 Hàm sinh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.2 Hàm sinh mũ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.3 Công thức sàng . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.3.1 Nguyên lý bù trừ . . . . . . . . . . . . . . . . . . . . . . . 32 2.3.2 Công thức ngược . . . . . . . . . . . . . . . . . . . . . . . 35 2.3.3 Công thức sàng . . . . . . . . . . . . . . . . . . . . . . . . 40 3 Biến thể của công thức sàng Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 62 2 tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3 mở đầu lý thuyết tổ hợp xuất hiện vào thế kỷ 17. Trong một thời gian dài nó nằm ngoài hướng phát triển chung và những ứng dụng của toán học. Song tình hình đã thay đổi hẳn sau khi máy tính điện tử ra đời và tiếp theo sau đó là sự phát triển nhảy vọt của toán học hữu hạn. Cùng với sự phát triển với tốc độ nhanh của công nghệ thông tin, lý thuyết tổ hợp đã trở thành lĩnh vực toán học quan trọng và cần thiết cho nhiều lĩnh vực khoa học và ứng dụng. Một trong những ảnh hưởng mạnh mẽ nhất của lý thuyết tổ hợp là phần tính toán với các tập hữu hạn. Trong chương trình toán ở bậc phổ thông hiện nay, đã có sự chú trọng đặc biệt đến phần kiến thức về tổ hợp. Các bài toán về tổ hợp cũng thường xuất hiện trong các kỳ thi học sinh giỏi Toán quốc gia và quốc tế. Hướng nghiên cứu của luận văn là giới thiệu về phương pháp dùng hàm sinh, hàm sinh mũ để giải một số bài toán tổ hợp và giới thiệu về một công thức sàng lọc số phần tử của một tập hữu hạn theo hướng các phần tử này có mặt trong đúng chẵn (lẻ) tập con của tập đã cho mà ta gọi là công thức sàng . Từ tính hữu dụng của kỹ thuật hàm sinh và ý tưởng về việc sàng lọc theo hướng chẵn (lẻ) của công thức sàng, trong luận văn chúng tôi đưa ra công thức tính cho số phân hoạch chẵn (lẻ) của một tập hợp hữu hạn cho trước mà nó sẽ được gọi là một biến thể của công thức sàng . Đặc biệt, mối liên hệ giữa số tất cả các 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ẻ (thành các tập con không rỗng) của một tập hữu hạn là vấn đề mà chúng tôi rất quan tâm. Luận văn gồm có ba chương, phần kết luận và tài liệu tham khảo. Chương 1. Kiến thức chuẩn bị Trong chương này, chúng tôi trình bày về một số quy tắc đếm, bài toán đếm và một vài kết quả cơ bản về tổ hợp. Chương 2. Hàm sinh và công thức sàng Chương này gồm ba phần. - Hàm sinh thường: Giới thiệu về hàm sinh thường và áp dụng vào giải một 4 vài bài toán tổ hợp điển hình. - Hàm sinh mũ: Giới thiệu về hàm sinh mũ và áp dụng vào giải một vài bài toán tổ hợp điển hình. - Công thức sàng: Dùng công thức ngược cho các đồng nhất thức tổ hợp, kết hợp với nguyên lý bù trù trừ để xây dựng công thức sàng. Chương 3. Biến thể của công thức sàng Trong chương này, chúng tôi đưa ra cách tính số tất cả các cách phân hoạch một tập hợp hữu hạn thành các tập con không rỗng sao cho mỗi tập con có một số chẵn (một số lẻ) phần tử bằng cách áp dụng kỹ thuật hàm sinh mũ kết hợp với các phép biến đổi giải tích. Hơn nữa, chúng tôi cũng sẽ xác định các số này bằng con đường sơ cấp hơn qua các công thức tính truy hồi. Mối liên hệ giữa số tất cả các phân hoạch chẵn, số tất cả các phân hoạch lẻ này với số tất cả các phân hoạch một tập hữu hạn thành các tập con không rỗng mà chúng ta đã biết trong một số tài liệu về tổ hợp cũng sẽ được đưa ra. Sau cùng là một vài ví dụ. Tác giả xin bày tỏ lòng biết ơn sâu sắc đến thầy Nguyễn Thái Hòa -Trường ĐHQN. Thầy đã tận tình hướng dẫn, động viên, giúp đỡ trong quá trình nghiên cứu và hoàn chỉnh luận văn. Tác giả xin bày lòng biết ơn sâu sắc đến thầy Phạm Xuân Bình -Trường ĐHQN. Các vấn đề mới của luận văn được thực hiện dựa trên ý tưởng ban đầu mà thầy đã gợi ý cho tác giả. Tác giả xin chân thành cám ơn đế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 khóa 8, Sở Giáo dục và Đào tạo tỉnh Bình Định, Trường THPT An Lương - Bình Định, cùng tất cả các bạn bè đồng nghiệp đã tạo điều kiện, giúp đỡ cho tác giả trong suốt thời gian học tập và thực hiện luận văn này. Quy Nhơn, 2008 Phạm Triều Đại 5 Chương 1 Kiến thức chuẩn bị Trong chương này chúng tôi sẽ trình bày một số quy tắc đếm, bài toán đếm và một số kết quả liên quan đến số tất cả các phân hoạch 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. (Xem [1], [3], [4], [6], [9]). 1.1 Các quy tắc đếm cơ bản Quy tắc tương ứng một -một ([1], tr 46). Cho hai tập hợp hữu hạn X và Y : X = {1, 2, . . . , n}, Y = {a1 , a2 , . . . , am }, |X| = n |Y | = m. Một ánh xạ ϕ từ X vào Y là một phép tương ứng, ký hiệu   1 2 ··· n  ϕ= ai1 ai2 · · · ain cho ứng mỗi phần tử j ∈ X với duy nhất một phần tử aij ∈ Y, j = 1, n. - Ánh xạ ϕ được gọi là một toàn ánh nếu mỗi a ∈ Y , tồn tại ít nhất một i ∈ X sao cho a = ϕ(i). Nếu tồn tại một toàn ánh từ X đến Y thì |X| ≥ |Y |. - Ánh xạ ϕ được gọi là một đơn ánh nếu với mọi i, j ∈ X nếu i 6= j thì ϕ(i) 6= ϕ(j). 6 Nếu tồn tại một đơn ánh từ X đến Y thì |X| ≤ |Y |. - Ánh xạ ϕ được gọi là một song ánh (hoặc tương ứng 1-1) nếu ϕ là đơn ánh và toàn ánh. Quy tắc tương ứng 1-1: Nếu tồn tại tương ứng 1-1 giữa các phần tử của các tập hữu hạn X và Y thì X và Y có cùng số phần tử. Ví dụ 1.1. Cho tập hợp X gồm n phần tử phân biệt. Có bao nhiêu cách chọn 2 phần tử bất kỳ của tập hợp X . Chứng minh. Gọi A là số cách chọn 2 phần tử bất kỳ trong tập hợp X . Bây giờ trong mặt phẳng, cho n điểm A1 , A2 , . . . , An sao cho không có 3 điểm nào thẳng hàng và nối tất cả các điểm đó lại với nhau từng đôi một. Ta nhận xét rằng: với 1 điểm bất kỳ nối với n − 1 điểm còn lại ta được n − 1 đoạn thẳng. Vì có n điểm nên ta có n(n − 1) đoạn thẳng nhưng khi đó mỗi đoạn thẳng được n(n − 1) đoạn thẳng. Gọi B là tập hợp tất cả các đoạn 2 n(n − 1) thẳng này, |B| = . Rõ ràng tồn tại một song ánh (một tương ứng 1-1) 2 giữa hai tập hợp A và B . Do đó ta có tính hai lần, do vậy có |A| = |B| = n(n − 1) . 2 Quy tắc cộng ([3], tr 27). Nếu có m1 cách chọn đối tượng x1 , m2 cách chọn đối tượng x2 , . . . , mn cách chọn đối tượng xn và nếu cách chọn đối tượng xi không trùng với bất kỳ cách chọn đối tượng xj nào (i 6= j, i, j = 1, n) thì có m1 + m2 + · · · + mn cách chọn một trong các đối tượng đã cho. Ta chứng minh quy tắc cộng trên cơ sở của lý thuyết tập hợp như sau. Định lý 1.1. Cho n tập hợp hữu hạn Xi (i = 1, n) với |Xi | = mi , Xi ∩ Xj = ∅, i 6= j. Khi đó số cách chọn một phần tử thuộc tập n S i=1 S  n  Xi là  Xi  và n n [  X   |Xi |.  Xi = i=1 i=1 i=1 (1.1) 7 Chứng minh. Ta chứng minh quy nạp theo n với n ≥ 2. Nếu n = 2 thì |X1 ∪ X2 | = |X1 | + |X2 | − |X1 ∩ X2 | = |X1 | + |X2 |. (do X1 ∩ X2 = ∅) Giả sử (1.1) đúng với n = k, (k ≥ 2). Ta sẽ chứng minh (1.1) đúng với n = k + 1, nghĩa là  k+1 k+1 [  X Xi = |Xi |.  i=1 (1.2) i=1 Thật vậy ta có X1 ∪ X2 ∪ · · · ∪ Xk ∪ Xk+1 = (X1 ∪ X2 ∪ · · · ∪ Xk ) ∪ Xk+1 . Vì Xi ∩ Xj = ∅, i 6= j; i, j = 1, 2, . . . , k, k + 1 nên (X1 ∪ X2 ∪ · · · ∪ Xk ) ∩ Xk+1 = (X1 ∩ Xk+1 ) ∪ (X2 ∩ Xk+1 ) ∪ · · · ∪ (Xk ∩ Xk+1 ) = ∅. Vậy |X1 ∪ X2 ∪ · · · ∪ Xk ∪ Xk+1 | = |(X1 ∪ X2 ∪ · · · ∪ Xk ) ∪ Xk+1 | = |X1 ∪ X2 ∪ · · · ∪ Xk | ∪ |Xk+1 | k X |Xi | + |Xk+1 |. = i=1 = k+1 X |Xi |. i=1 Suy ra (1.2) được chứng minh. Theo nguyên lý quy nạp toán học, quy tắc cộng là đúng với mọi n ∈ N, n ≥ 2. Ví dụ 1.2. Từ các chữ số 1, 2, 3 có thể lập được bao nhiêu số khác nhau có những chữ số khác nhau. Chứng minh. Từ các chữ số 1, 2, 3 có thể lập được: - Ba số khác nhau có một chữ số là 1, 2, 3. Trong trường hợp này có 3 cách lập. - Sáu số khác nhau, mỗi số có hai chữ số là 12, 13, 21, 23, 31 và 32. Trong trường hợp này có 6 cách lập. - Sáu số khác nhau, mỗi số có ba chữ số là 123, 132, 213, 231, 312 và 321. Trong 8 trường hợp này có 6 cách lập. Các cách lập trên đôi một không trùng nhau. Vậy theo quy tắc cộng có 3 + 6 + 6 = 15 cách lập những số khác nhau có những chữ số khác nhau từ các chữ số 1, 2, 3. Quy tắc nhân ([3], tr 28.) Nếu tồn tại tương ứng 1-1 giữa các phần tử của các tập hữu hạn X và Y thì X và Y có cùng số phần tử Nếu có m1 cách chọn đối tượng x1 , sau đó với mỗi cách chọn đối tượng x1 như thế có m2 cách chọn đối tượng x2 , sau đó với mỗi cách chọn x1 và x2 như thế có m3 cách chọn đối tượng x3 ,. . . , cuối cùng, với mỗi cách chọn x1 , x2 , . . . , xn−1 như thế có mn cách chọn đối tượng xn , thì có m1 m2 . . . mn cách chọn dãy các đối tượng "x1 rồi x2 rồi x3 ...rồi xn ". Ta chứng minh quy tắc nhân trên cơ sở của lý thuyết tập hợp như sau. Định lý 1.2. Giả sử có n tập hữu hạn Xi , i = 1, n, |Xi | = mi . Chọn một bộ gồm n phần tử (a1 , a2 , . . . , an ) với ai ∈ Xi . Khi đó số cách chọn khác nhau là |X1 × X2 × · · · × Xn | và |X1 × X2 × · · · × Xn | = n Y mi . (1.3) i=1 Chứng minh. Ta chứng minh (1.3) bằng phương pháp quy nạp theo n, n ≥ 2 như sau. Với n = 2, ta có |X1 | = m1 , |X2 | = m2 . Giả sử X1 = {a1 , a2 , . . . , am1 } và X2 = {b1 , b2 , . . . , bm2 } thì X1 × X2 = {(ai , bj ) : 1 ≤ i ≤ m1 , 1 ≤ j ≤ m2 , ai ∈ X1 , bj ∈ X2 }. Ta viết X1 × X2 dưới dạng bảng sau (a1 , b1 ) (a1 , b2 ) · · · · · · (a1 , bm2 ) (a2 , b1 ) (a2 , b2 ) · · · · · · (a2 , bm2 ) 9 .. . .. . (am1 , b1 ) .. . .. . (am1 , b2 ) · · · · · · (am1 , bm2 ) Đặt Ei = {(ai , b1 ), (ai , b2 ), . . . , (ai , bm2 ) : 1 ≤ i ≤ m1 } =⇒ |Ei | = m2 . Ta có X1 × X2 = E1 ∪ E2 ∪ · · · ∪ Em1 với Ei ∩ Ej = ∅, i 6= j. Theo quy tắc cộng ta được |X1 × X2 | = |E1 ∪ E2 ∪ · · · ∪ Em1 | = m1 X |Ei | = m1 m2 . i=1 Vậy công thức (1.3) đúng cho trường hợp n = 2. Giả sử (1.3) đúng với trường hợp n = k, (k ≥ 2), tức là |X1 × X2 × · · · × Xk | = m1 .m2 . . . mk . Ta chứng minh (1.3) đúng cho trường hợp n = k + 1, có nghĩa là |X1 × X2 × · · · × Xk × Xk+1 | = m1 .m2 . . . mk .mk+1 . Thật vậy, xét một phần tử bất kỳ (a1 , a2 , . . . , ak , ak+1 ) của tích Descartes X1 × X2 × · · · × Xk × Xk+1 . Đặt α = (a1 , a2 , . . . , ak ). Rõ ràng giữa tập hợp các bộ có dạng (a1 , a2 , . . . , ak , ak+1 ) và tập hợp các cặp có dạng (α, ak+1 ) có tương ứng 1 − 1. Vậy có bao nhiêu bộ (a1 , a2 , . . . , ak , ak+1 ) thì có bấy nhiêu cặp (α, ak+1 ). Nếu ta ký hiệu tập hợp tất cả các α là X , thì ta có thể nói rằng tập hợp X1 × X2 × · · · × Xk × Xk+1 có bao nhiêu phần tử thì tập hợp X × Xk+1 có bấy nhiêu phần tử, tức là |X1 × X2 × · · · × Xk × Xk+1 | = |X × Xk+1 |. Theo chứng minh cho trường hợp n = 2 ta có |X × Xk+1 | = |X||Xk+1 |. Theo cách dựng thì X chính là tích Descartes X1 × X2 × · · · × Xk . Áp dụng giả thiết quy nạp ta có |X × Xk+1 | = |X||Xk+1 | = |X1 × X2 × · · · × Xk | × |Xk+1 | = m1 m2 . . . mk mk+1 . Vậy |X1 × X2 × · · · × Xk × Xk+1 | = m1 m2 . . . mk mk+1 . Theo nguyên lý quy nạp toán học, công thức (1.3) đúng với mọi n ∈ N, n ≥ 2. Ví dụ 1.3. Có bao nhiêu số gồm 3 chữ số khác nhau có thể lập từ các chữ số 0, 2, 4, 6, 8. 10 Chứng minh. Số cần lập có dạng a1 a2 a3 . Ta có 4 cách chọn a1 , (vì a1 6= 0). ứng với mỗi cách chọn a1 có 4 cách chọn a2 . ứng với mỗi cách chọn a1 , a2 có 3 cách chọn a3 . Theo quy tắc nhân ta có 4.4.3 = 48 số cần lập. 1.2 Một số bài toán đếm và kết quả tổ hợp cơ bản 1.2.1 Chỉnh hợp - hoán vị - tổ hợp Định nghĩa 1.1. Cho tập hữu hạn X = {a1 , a2 , a3 , ..., an } và một số tự nhiên k 6 n. Khi đó (i) Bộ k phần tử (ai1 , ai2 , ..., aik ), aij ∈ X được gọi là bộ có thứ tự nếu đổi vị trí các phần tử ta được bộ một bộ mới. Ngược lại, bộ k phần tử (ai1 , ai2 , ..., aik ), aij ∈ X được gọi là bộ không có tính thứ tự. (ii) Bộ k phần tử (ai1 , ai2 , ..., aik ), aij ∈ X được gọi là bộ không lặp nếu aij 6= ail , ∀j, l ∈ {1, ..., k}, j 6= l.. Ngược lại, bộ k phần tử (ai1 , ai2 , ..., aik ), aij ∈ X được gọi là bộ có lặp. Định nghĩa 1.2. Cho tập hợp X gồm m phần tử và số nguyên dương n với 1 6 n 6 m. Một chỉnh hợp chập n của m phần tử đã cho là một bộ có thứ tự gồm n phần tử khác nhau được chọn từ m phần tử của X . Theo định nghĩa, ta thấy rằng số các chỉnh hợp chập n của X chính là số các cách chọn ra n phần tử từ X theo cách chọn có thứ tự và không lặp. Số này được ký hiệu Anm hoặc (m)n và được tính như sau: Ta có m cách chọn phần tử thứ nhất. Vì chọn không lặp nên ta có m − 1 cách chọn phần tử thứ hai. Tiếp tục lý luận đó ta có m − n + 1 cách chọn phần tử thứ n. Theo quy tắc nhân, số các cách chọn là m(m − 1)...(m − n + 1). 11 Vậy ta có Anm = (m)n = m(m − 1)...(m − n + 1) = m! (m − n)! (1.4) Định nghĩa 1.3. Một chỉnh hợp lặp chập n của m phần tử đã cho là một bộ có thứ tự gồm n phần tử được chọn từ m phần tử đã cho, trong đó mỗi phần tử có thể lặp lại một số lần tùy ý. Theo định nghĩa ta thấy rằng số các chỉnh hợp lặp chập n của m phần tử đã cho chính là số các cách chọn ra n phần tử từ m phần tử đã cho theo cách chọn có lặp và có thứ tự. Theo quy tắc nhân và do tính có lặp của phép chọn ta tìm được số các chỉnh hợp lặp chập n của m phần tử đã cho là mn . Định nghĩa 1.4. Một hoán vị của m phần tử đã cho là một bộ có thứ tự gồm m phần tử , trong đó mỗi phần tử có mặt đúng một lần. Số tất cả các hoán vị của tập hợp gồm m phần tử cho trước ký hiệu là Pm . Theo quy tắc nhân, Pm = m! Định nghĩa 1.5. Một tổ hợp chập n của m phần tử cho trước là một bộ không có thứ tự gồm n phần tử khác nhau lấy từ m phần tử đã cho (n 6 m). Từ định nghĩa ta thấy rằng một tổ hợp chập n của một tập hợp gồm m phần tử cho trước chính là một tập con gồm n phần tử của tập gồm m phần tử cho trước. Như vậy số tất cả các tổ hợp chập n của m phần tử đã cho chính là số cách chọn ra n phần tử từ một tập hợp gồm m phần  tửcho trước theo n hoặc  cách chọn không lặp và không thứ tự. Ký hiệu Cm m n . Ta có nhận xét rằng ứng với mỗi tổ hợp chập n của m phần tử, có thể thành lập được n! chỉnh hợp chập n của m phần tử. Suy ra n Cm = 1 n m! Am = n! n!(m − n)! (1.5) Nhận xét. Cho tập hữu hạn X có |X| = n. Khi đó số tập con có k phần tử (0 6 k 6 n) của X sẽ là Cnk . 12 Định nghĩa 1.6. Một tổ hợp lặp chập n của m phần tử cho trước là một bộ không có thứ tự gồm n phần tử lấy từ m phần tử đã cho, mỗi phần tử có thể có mặt nhiều lần. Từ định nghĩa ta có kết quả sau đây. Mệnh đề 1.3. Số tất cả các tổ hợp lặp chập n của m phần tử cho trước là n Cm+n−1 . Chứng minh. Ký hiệu N (m, n) là số các tổ hợp lặp chập n của tập X = {a1 , a2 , ..., am } ( tập m phần tử cho trước). Ta tiến hành chứng minh quy nạp theo. Trước hết, với l tùy ý sao cho 1 6 l 6 m thì N (l, 1) = l = Cl1 . k+1 k Giả sử N (l, k) = Cl+k−1 , 1 6 l 6 m, ta cần chứng minh rằng N (m, k+1) = Cm+k . Để tiện cho việc chứng minh ta hãy xét một thứ tự nào đó trên tập X , chẳng hạn ta hãy gán thứ tự sau: a1 < a2 < a3 < · · · < am . Khi đó mỗi tổ hợp lặp [ai1 , ..., aik+1 ] , aij ∈ X, j = 1, k + 1 có thể viết duy nhất dưới dạng bộ n- thứ tự (ai1 , ..., aik+1 ) trong đó aij 6 aih khi i 6 h (tức là ai1 6 ai2 6 · · · 6 aik+1 ) Ngược lại, với bộ n thứ tự như trên, ta xác định duy nhất một tổ hợp lặp chập n của m phần tử đã cho. Nói cách khác ta đã xác định được một tương ứng 1-1 giữa tập hợp gồm tất cả các tổ hợp lặp chập n của m phần tử với tập hợp gồm tất cả các bộ (k + 1)-thứ tự như trên, tức là N (m, k + 1) chính là số tất cả bộ (k + 1)-thứ tự (ai 1, ..., ai k + 1) với ai1 6 ai2 6 · · · 6 aik+1 . Ta thấy rằng nếu ai1 = aj , 1 6 j 6 m thì số các bộ (k + 1)-thứ tự như trên chính là N (m − j + 1, k) theo như giả thiết quy nạp. Theo quy tắc cộng ta có N (m, k + 1) = m X j=1 N (m − j + 1, k) = m X j=1 k Cm+k−j = m h X k+1 Cm+k+1−j k+1 − Cm+k−j i k+1 = Cm+k j=1 (1.6) Theo nguyên lý quy nạp ta có điều cần chứng minh. 13 1.2.2 Phân hoạch của tập hợp. Số Stirling loại hai và số Bell Định nghĩa 1.7. 1) Một phân hoạch của một tập hữu hạn X thành k phần là một họ các tập con khác rỗng X1 , X2 , . . . , Xk của X thoả các tính chất sau i) Hợp tất cả các tập hợp Xi , i = 1, k tạo thành tập hợp X , tức là X1 ∪ X2 ∪ · · · ∪ Xk = X. ii) Các tập hợp này đôi một giao nhau bằng tập hợp rỗng, tức là Xi ∩ Xj = ∅, i 6= j. 2) Số tất cả các phân hoạch thành k phần của một tập X có n phần tử được gọi là số Stirling loại hai và được ký hiệu là Sn,k . Số Bn = n X Sn,k được gọi là số Bell. k=0 Nhận xét. Từ định nghĩa ta có i) Sn,k = 0 nếu k > n. Ta cũng quy ước rằng S0,0 = 1 và Sn,0 = 0 nếu n >1. ii) Số Bell chính là số tất cả các phân hoạch của tập X có n phần tử. Ví dụ 1.4. Phân hoạch của tập hợp {a, b, c, d} thành 3 phần có thể được biểu thị như tập hợp: {{a}, {b}, {c, d}}; {{a}, {b, d}, {c}}; {{a, d}, {b}, {c}} {{a}, {b, c}, {d}}; {{a, c}, {b}, {d}}; {{a, b}, {c}, {d}} hoặc viết đơn giản hơn a|b|cd a|bd|c ad|b|c a|bc|d ac|b|d ab|c|d Như vậy S4,3 = 6. Ta cũng có S4,0 = 0; S4,0 = 0; S4,1 = 1; S4,2 = 7; S4,4 = 1. Do đó B4 = S4,0 + S4,1 + S4,2 + S4,3 + S4,4 = 0 + 1 + 7 + 6 + 1 = 15. 14 Ta chứng minh hệ thức truy hồi sau cho số Stirling loại hai. Định lý 1.4. ([9], tr 17). Với các kí hiệu nêu trên, khẳng định sau là đúng Sn,k = Sn−1,k−1 + kSn−1,k . Chứng minh. Xét một tập hợp tùy ý có n phần tử {x1 , x2 , . . . , xn }. Ta đếm các phân hoạch của tập hợp này thành k phần (hay khối). Chúng ta có thể đếm chúng bằng cách phân lớp các phân hoạch theo khối có chứa tập hợp {xn } hay không. Nếu {xn } là một khối của phân hoạch, chúng ta cần chia tập hợp {x1 , x2 , . . . , xn−1 thành k − 1 phần và có Sn−1,k−1 cách làm như vậy. Nếu {xn } không là một khối thì xn phải được chứa trong một khối với ít nhất một phần tử khác của tập hợp. Có Sn−1,k cách phân hoạch {x1 , x2 , . . . , xn−1 } thành k khối và xn có thể nằm trong bất cứ một trong các khối này. Do đó có kSn−1,k cách mà trong đó tập hợp ban đầu có thể phân hoạch thành k khối mà không có {xn } là một khối. Từ đó ta nhận được công thức xác lập mối liên hệ giữa các số Stirling loại 2 là Sn,k = Sn−1,k−1 + kSn−1,k . Từ định nghĩa số Stirling loại 2 ta có Sn,0 = 0; Sn,1 = 1; Sn,n = 1, với n ≥ 1 và Sn,k = 0, ∀k > n. Kết quả trên đây cho ta tam giác của các số Stirling loại 2. Trừ các giá trị ở mép bằng 1, còn các giá trị khác của Sn,k được tính như tổng của số nằm trên nó nhân với k (kSn−1,k ) và số nằm trên nó ở bên trái (Sn−1,k−1 ). S1,1 1 S2,1 S2,2 1 S3,1 S3,2 S3,3 S4,1 S4,2 S4,3 S4,4 S5,1 S5,2 S5,3 S5,4 1 S5,5 1 1 3 1 1 7 6 1 15 25 10 1 năm hàng đầu tiên cho số stiling loại hai 15 1.2.3 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 ([4], tr 36). Giả sử N và M là hai tập hợp hữu hạn với |N | = n và |M | = m. Hãy tìm số các hàm f : N −→ M. Chứng minh. Trước tiên ta chú ý rằng với n là một số nguyên dương, ta viết [n] = {1, 2, . . . , n}- tập hợp chứa n số nguyên dương đầu tiên. Để thực hiện việc đếm các ánh xạ, thường có hai cách mô tả thuận lợi sau đây: Mô tả một ánh xạ bởi một ma trận và mô tả bởi một dãy. Trong cách đầu tiên, chúng ta biểu diễn N như một hàng đầu tiên của ma trận và viết f (x) dưới mỗi phần tử x ∈ N . Giả thiết N = {a, b, c, . . . , d}, ta viết  f = a b c ···  d  f (a) f (b) f (c) · · · f (d) Nếu |N | = n thì số ánh xạ f : N −→ M bằng số ánh xạ f : [n] −→ M . Ta quy ước viết các ánh xạ f : [n] −→ M dưới dạng  f = 1 2 ··· 3 n f (1) f (2) f (3) · · · f (n)   (∗) Chúng ta có thể rút gọn (∗) bằng cách khử hàng đầu tiên và viết f như một dãy f (1)f (2)f (3) · · · f (n) hay m1 m2 m3 . . . mn , trong đó f (i) = mi ∈ M . Do đó, số các ánh xạ cần tính bằng số các dãy. Theo quy tắc nhân số các dãy là n m.m.m | {z . . . m} = m . n Vậy ta có Số tất cả các hàm f : N 7→ M với |N | = n và |M | = m bằng |M ||N | = mn . 16 1.2.4 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 ([4], tr 37). Giả sử N và M là hai tập hợp hữu hạn với |N | = n và |M | = m. Hãy tìm số các hàm đơn ánh Chứng minh. Để ý rằng các đơn ánh f : N −→ M (|N | ≤ |M |) tương ứng với những dãy các phần tử của M có độ dài n mà không chứa những phần tử của M xuất hiện lần thứ hai. Từ đó ta có tổng số các đơn ánh f : N −→ M là m(m − 1)(m − 2) · · · (m − n + 1) = m! = (m)n = Anm (m − n)! Số (m)n còn được gọi là giai thừa giảm của m. Trong trường hợp |N | = |M | = m thì có m! đơn ánh f : N −→ M . Đó cũng chính là số song ánh f : M −→ M . Mỗi song ánh từ M lên M là một hoán vị của M . 1.2.5 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 ([6], tr 37). Giả sử N và M là hai tập hợp hữu hạn với |N | = n và |M | = m. Hãy tìm số các hàm toàn ánh f : N −→ M. Chứng minh. Cho N và M là hai tập hợp hữu hạn khác rỗng, |N | = n, |M | = m, n ≥ m. Với một phân hoạch của tập hợp N thành m phần và xem mỗi phần như một phần tử (N ≡ [m]) thì ta có m! đơn ánh f : N −→ M . Do số phân hoạch của tập hợp N thành m phần là Sn,m nên theo quy tắc nhân số toàn ánh f : N −→ M bằng m!Sn,m . Bây giờ ta có thể chứng minh một kết quả tổ hợp quan trọng sau đây. 17 Mệnh đề 1.5. ([4], tr 38). n m = n X Sn,k (m)k . k=1 Chứng minh. Giả sử N và M là các tập hợp với |N | = n, |M | = m. Chúng ta hãy đếm tập hợp các ánh xạ f : N −→ M theo hai cách. Đầu tiên là những dãy như trong 1.2.3 ta được kết quả là mn . Thứ hai ta phân loại các ánh xạ theo lực lượng ảnh của chúng. Số các ánh xạ có ảnh f (N ) = K ⊂ M là số những toàn ánh f : N −→ K , theo trong 1.2.5 bằng k!Sn,k với |K| = k . Do đó số các ánh xạ f : N −→ M với ảnh có lực lượng k bằng tích các k -tập hợp con K k k!S của M với các toàn ánh f : N −→ K và bằng Cm n,k . Vì lực lượng ảnh của f có thể là 1, 2, . . . , n phần tử nên chúng ta thu được đồng nhất thức tổ hợp: n n X X k n Sn,k (m)k . Cm k!Sn,k = m = k=1 k=1 Mệnh đề sau đây cho ta một cách tính khác cho số Stirling loại 2. Mệnh đề 1.6. Sn,k = n! k! 1
1 1 · ··· . i1 ! i2 ! ik ! X (i1 ,i2 ,...,ik ): k P ij =n j=1 ij ≥1 Chứng minh. Giả sử có bộ số (i1 , i2 , · · · , ik ) sao cho k P ij = n, ij > 1.Ta sẽ j=1 xác định số cách phân hoạch tập X thành k tập con không rỗng sao cho số phần tử của các tập là ij , j ∈ {1, 2, ..., k}. Ta có: Số cách chọn i1 phần tử từ n phần tử của tập X là Cni1 , i2 Với mỗi cách chọn i1 phần tử thì có Cn−i cách chọn i2 phần tử; 1 i3 Với mỗi cách chọn i1 phần tử và i2 phần tử thì có Cn−i cách chọn i3 phần 1 −i2 tử; .................................................................... ik Với mỗi cách chọn i1 phần tử,..., ik−1 phần tử thì có Cn−i cách chọn 1 −i2 −···−ik−1 ik phần tử. Hơn nữa, các tập con của phân hoạch không phân biệt thứ tự, tức là bộ số 18 (i1 , i2 , · · · , ik ) không phân biệt thứ tự. Do đó số cách phân hoạch tập X thành k tập con không rỗng sao cho số phần tử của các tập là ij , j ∈ {1, 2, ..., k} bằng: 1 1 n! n! 1 i2 · · · C = · Cni1 Cn−i · = · n−i −i −···−i 1 2 k−1 1 k! k! i1 !i2 ! · · · ik ! k! i1 ! · · · ik ! Suy ra số cách phân hoạch tập X thành k tập con không rỗng sẽ là: n! 1 1 1
n! · ··· = k! i1 ! i2 ! ik ! k! X (i1 ,i2 ,...,ik ): k P ij =n 1
1 1 · ··· i1 ! i2 ! ik ! X (i1 ,i2 ,...,ik ): k P ij =n j=1 j=1 ij ≥1 ij ≥1 Số Stirling loại hai Sn,k còn có thể tính theo n và k bởi công thức Sn,k = k P 1 (−1)k−j Ckj .j n . Công thức này sẽ được chứng minh trong chương sau. k! j=0 Mệnh đề sau đây cho ta công thức tính truy hồi cho số Bell. Mệnh đề 1.7. ([6], tr 92). Bn+1 = n X Cnk Bk , (B0 = S0,0 = 1) . k=0 Chứng minh. Xét hàm sốL : R [x] → R (x)k 7→ L(x)k = 1 mn Theo mệnh đề 1.5 ta có này nghĩa là đa thức của đại số ta được xn xn − − n X = n X n X ∀ k ∈ N∗ Sn,k (m)k với mọi số nguyên dương m. Điều k=1 Sn,k (x)k có vô số nghiệm. Theo định lý cơ bản k=1 xn n X Sn,k (x)k = 0 hay = Sn,k (x)k . k=1 k=1 ! n n n X X X n Suy ra L(x ) = L Sn,k (x)k = Sn,k L(x)k = Sn,k = Bn . k=1 k=1 Mặt khác, (x)n+1 = x(x − 1)n . Suy ra L(x)n+1 = L(x)n = Lx(x − 1)n k=0 19 Vì mọi dãy đa thức đều là một cơ sở của không gian vectơ các đa thức R [x] nên từ đẳng thức trên ta suy ra : ∀p(x) ∈ R [x] , Lp(x) = Lxp(x − 1) Lấy p(x) = (x + 1)n , ta được L(x + 1)n = Lxxn = Lxn+1 n Trong đó L(x + 1) = L Do đó Bn+1 = n X n X Cnk xk k=0 = n X Cnk Lxk = k=0 n X Cnk Bk còn Lxn+1 = Bn+1 k=0 Cnk Bk . k=0 Ta có điều cần chứng minh. Số Bell Bn còn có thể được tính theo n và k bởi công thức Bn = 1 X kn ( Công thức Dobinski ). e n! k≥0 Công thức này sẽ được chứng minh ở chương 2. Áp dụng các công thức trên ta thu được bảng các số Bell như sau: n Bn 0 1 1 2 1 3 2 4 5 15 5 52 6 7 203 877 8 4140