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

Chia sẻ: Paradise_12 Paradise_12 | Ngày: | Loại File: PDF | Số trang:87

Thêm vào BST

Báo xấu

73
lượt xem 26
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

A càng nhiều phần tử, càng có nhiều cách chia (phân hoạch). Mỗi một cách chia có thể chia để các phần trong nó có nhiều phần tử, hoặc ít phần tử. Phân hoạch ∏1 được coi là ≤ Phân hoạch ∏2 khi: - Mỗi tập trong phân hoạch ∏1 đều là tập con của tập trong phân hoạch ∏2

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

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
1 M cl 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 hp ............................ 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 tt ph uh 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
2 1.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
3 m đ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.
4 Chươ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
5 Chươ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 .
6 1.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ì | A 1 × A 2 × · · · × A n | = | A 1 | × | A 2 | × · · · × |A n | . 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 .
7 1.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 Ak hay (n)k đ ch s ch nh h p không l p ch p n 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à Ak = n(n − 1)...(n − k + 1) = n n! · Đ t n t i ch nh h p, c n ph i th a mãn k ≤ n. Ta quy ư c Ak = 0 n (n − k )! 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 hp Đ 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,
8 ta 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à Cn . Đ tính k Cn 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 k 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ó Cn cách th c hi n giai đo n H1 . k 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ó Ak = k ! cách th c hi n giai đo n H2 . k Ak n Theo quy t c nhân ta có Ak = Cn .k !. Suy ra Cn = . Vì v y k k n k!  n! n!  n u 1≤k≤n : k! =   (n − k )! k !(n − k )! k Cn =   n u k > n. 0 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 n! 0 r ng Cn = 1. Khi đó đ ng th c Cn = cũng đúng cho c k = 0. k k !(n − k )! 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 = 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
9 cá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: k=0 k=1 k= 2 k=3 k=4 k=5 k=6 k=7 k=8 Sn,k 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 0 x · · · x 0 · · · 0 x . . . x (∗ ) x1 x2 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 (*) k −1 là Cn−1 . V y s nghi m nguyên dương c a phương trình x1 + x2 + · · · + xk = n k −1 là Cn−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 k −1 nguyên không âm c a phương trình x1 + x2 + · · · + xk = n là Cn+k−1 = Cn+k−1 . n 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 ) = f (aj ) n u i = 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 An . V y ta có m S t t c các hàm đơn ánh t N đ n M b ng An . m 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 Am = m!. 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 f f đ nh nghĩa quan h ∼ trên N như sau: a1 ∼ a2 khi và ch khi f (a1 ) = f (a2 ). f D th y r ng quan h ∼ là m t quan h tương đương trên N . Vì th mà các f l p tương đương c a ∼ 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 N f = {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 → f (Ni ) = f (ai ) v i ai ∈ Ni . D th y r ng f là m t song ánh gi a N f 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 → 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. n Đ nh lý 1.3.1. (theo [3, 1.4]) mn = Sn,k (m)k . k=0 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 = j và F = F1 ∪ F2 ∪ · · · ∪ Fm . Theo quy t c c ng, ta có: |F | = |F 1 | + |F 2 | + · · · + |F m |. 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ó Cm cách th c hi n H1 . k 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 . m Theo quy t c nhân ta có |Fk | = Cm .k !.Sn,k = Sn,k (m)k . Do đó |F | = Sn,k (m)k . k k=1 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 n n n m = |F | = Sn,0 (m)0 + Sn,k (m)k = Sn,k (m)k . k=1 k=0 n Theo Đ nh lý 1.3.1, mn = Sn,k (m)k v i m i s nguyên dương m, t c k=0 n là đa th c xn − Sn,k (x)k có vô s nghi m. Theo Đ nh lý cơ b n c a đ i s , k=0 ta có n n x− Sn,k (x)k = 0, k=0 Suy ra n n x= Sn,k (x)k . k=0
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ó n k Bn+1 = Cn Bk , (B0 = 1). k=0 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) → L((x)k ) = 1 v i m i k = 0, 1, 2, .... n Ta có xn = Sn,k (x)k . Do đó k=0 n n Sn,k = Bn . L(xn ) = Sn,k L((x)k ) = k=0 k=0 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 n Cn Bk = Bn+1 . Cn L(xk ) = Bn+1 ⇔ k k ⇔ k=0 k=0 V y ta có n k Bn+1 = Cn Bk . k=0 M nh đ 1.3.1. Ta có n! 11 1 · ··· Sn,k = . k! i1 ! i2 ! ik ! k P (i1 ,i2 ,...,ik ): ij =n j =1 ij ≥1 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 = 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ó Cn1 i 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 i nh c a b2 , có Cn2−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 i c a N là t o nh c a bk , có Cnk−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à n! i i i Cn1 Cn2−i1 ...Cnk i1−i2 −···−ik−1 = . − 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à : n! i1 !i2 ! . . . ik ! k P (i1 ,i2 ,...,ik): ij =n j =1 ij ≥1 V y ta nh n đư c n! k !Sn,k = . i1 !i2 ! . . . ik ! k P (i1 ,i2 ,...,ik): ij =n j =1 ij ≥1 T đây ta suy ra n! 11 1 · ··· Sn,k = . k! i1 ! i2 ! ik ! k P (i1 ,i2 ,...,ik): ij =n j =1 ij ≥1
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 ng các phương pháp sơ c p. Ta ch y u xét bài toán đ m s phân ho ch m t t p h u h n cùng v i các đi u ki n đư c đ t thêm vào m t cách t nhiên. Ta s d ng th ng nh t các ký hi u sau: * Un,k : s cách phân ho ch t p n ph n t thành k t p con không r ng và trong m i t p con ta ch n ra m t ph n t đ i di n. Ta quy ư c U0,0 = 1 và Un,0 = 0, n ≥ 1. Ví d : Xét A = {a, b, c}, n = 3. Xét các phân ho ch t p A thành 2 t p con không r ng và trong m i t p con ta ch n ra m t ph n t đ i di n. Khi đó, ta có các phân ho ch là: {{a}, {b, c}}; {{a}, {b, c}}; {{b}, {c, a}} {{b}, {c, a}}; {{c}, {a, b}}; {{c}, {a, b}} T ví d trên ta có U3,2 = 6. n * Gn = Un,k : s t t c các cách phân ho ch t p n ph n t thành các t p k=0 con không r ng và trong m i t p con ta ch n ra m t ph n t đ i di n. * En,k : 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 . Quy ư c E0,0 = 1. * On,k : 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 . Quy ư c O0,0 = 1. n n *Pn = En,k ; Qn = On,k . k=0 k=0 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 . Rõ ràng E2n+1,k = 0 ∀n, k ∈ N. Do đó, P2n+1 = 0, n = 0, 1, 2, .... Ta g i Pn (Qn ) là các s phân ho ch ch n (l ). Trong th c t , ta có th g p các s t h p v a nói trên trong các tình
18 hu ng như: Trong m t l p h c có n h c sinh ta c n chia l p ra thành các nhóm đ t ch c chơi trò chơi (không nh t thi t m i nhóm có cùng s h c sinh) và m i nhóm ta ch n ra m t em làm nhóm trư ng; hay chia l p ra thành các nhóm mà m i nhóm có m t s l (ch n) h c sinh. S cách chia trong các trư ng h p trên s cho ta các s t h p v a đư c trình bày. Ta s thi t l p các công th c truy h i và ch ra các m i liên h gi a các s nói trên v i các s t h p cơ b n. Đ nh lý 1.4.1. Ta có n k Bn = Cn Pk Qn−k . k=0 Ch ng minh: Trong n ph n t ta ch n ra k ph n t đ th c hi n phân ho ch ch n và n − k ph n t còn l i đ th c hi n phân ho ch l . Như v y, n k Bn = Cn Pk Qn−k . k=0 Nh n xét. 1) N u đ ý r ng Pk =0 v i k l thì có th vi t l i n– » 2 2 Cnk P2k Qn−2k . Bn = k=0 Trong đó ký hi u [x] dùng đ ch ph n nguyên c a x. 2) Ta th y r ng các s Bell Bn đư c bi u di n qua các s phân ho ch ch n Pn và các s phân ho ch l Qn . Cũng tương t như các s Bell, vi c l p công th c tư ng minh cho các s phân ho ch ch n và l g p nhi u khó khăn. Ta ph i tính chúng thông qua các s En,k và On,k .
19 M nh đ 1.4.1. Ta có n 2j C2n (E2j +2,2 − 1 − 2E2j,2 )E2n−2j,k−1 E2n+2,k+1 = E2n,k + (k + 1)E2n,k+1 + j =1 ∀ n ∈ N, ∀ k ∈ N. 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ó m t s ch n ph n t . Ta xem t p g m 2n + 2 ph n t như là t p ban đ u 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ó m t s 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 mà m i t p có m t s ch n ph n t sao cho a và b n m trong hai t p khác nhau. + G i σ 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 mà m i t p có m t s ch n ph n t . Khi đó |σ | = E2j +2,2 . + σ1 = {τ ∈ σ : {a, b} là m t t p c a phép phân ho ch τ } ⇒ |σ1| = 1. + σ2 = {τ ∈ σ : 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