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ẻ

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

Thêm vào BST

Báo xấu

96
lượt xem 23
download

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

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ảu 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 sự phát triển nhảy vọt của toán học hữa hạn....

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 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ẻ

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 cl c m đ u ................................... 3 1 Ki n th c chu n b 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 tt ph uh n . . . . . . . . . . . . . . . . . . . . . . . 15 1.2.4 Bài toán đ m t t c các hàm đơn ánh t mttph u h n vào m t t p h u h n. . . . . . . . . . . . . . . . . . . 16 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 . . . . . . . . . . . . . . . . . . 16 2 Hàm sinh và công th c sàng 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 45 ................................. 62 K t lu n
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). X = {1, 2, . . . , n}, |X | = n Cho hai t p h p h u h n X và Y : Y = {a1 , a2 , . . . , am }, |Y | = m. M t ánh x ϕ t X vào Y là m t phép tương ng, ký hi u   2 ··· n 1 ϕ=  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 = j thì ϕ(i) = ϕ(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) tính hai l n, do v y có đ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ó n(n − 1) |A| = |B | = . 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 = 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 = j. n n Khi đó s cách ch n m t ph n t thu c t p Xi là Xi và i=1 i=1 n n |Xi |. (1.1) Xi = i=1 i=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 |Xi |. (1.2) Xi = i=1 i=1 Th t v y ta có X1 ∪ X2 ∪ · · · ∪ Xk ∪ Xk+1 = (X1 ∪ X2 ∪ · · · ∪ Xk ) ∪ Xk+1 . Vì Xi ∩ Xj = ∅, i = j ; i, j = 1, 2, . . . , k, k + 1 nên (X1 ∪ X2 ∪ · · · ∪ Xk ) ∩ Xk+1 = (X1 ∩ Xk+1 ) ∪ (X2 ∩ Xk+1 ) ∪ · · · ∪ (Xk ∩ Xk+1 ) = ∅. |X1 ∪ X2 ∪ · · · ∪ Xk ∪ Xk+1 | = |(X1 ∪ X2 ∪ · · · ∪ Xk ) ∪ Xk+1 | Vy = |X1 ∪ X2 ∪ · · · ∪ Xk | ∪ |Xk+1 | k |Xi | + |Xk+1 |. = i=1 k+1 |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à n |X1 × X2 × · · · × Xn | = (1.3) mi . 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 , b2 ) · · · · · · (a1 , bm2 ) (a1 , b1 ) (a2 , b2 ) · · · · · · (a2 , bm2 ) (a2 , b1 )
9 . . . . . . . . . . . . (am1 , b2 ) · · · · · · (am1 , bm2 ) (am1 , b1 ) Đ 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 = j. Theo quy t c c ng ta đư c m1 |X1 × X2 | = |E1 ∪ E2 ∪ · · · ∪ Em1 | = |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 . |X1 × X2 × · · · × Xk × Xk+1 | = m1 m2 . . . mk mk+1 . Vy 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 = 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ơ bn 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 n. Khi đó k (ai1 , ai2 , ..., aik ), aij ∈ X đư c g i là b (i) B k ph n t có th t nu đ i v trí các ph n t ta đư c b mtb 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. (ai1 , ai2 , ..., aik ), aij ∈ X đư c g i là b (ii) B k ph n t không l p n u aij = ail , ∀j, l ∈ {1, ..., k }, j = 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 m. 1 n 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 An ho c (m)n và đư c tính như sau: Ta có m cách ch n ph n m 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ó m! An = (m)n = m(m − 1)...(m − n + 1) = (1.4) m (m − n)! Đ 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 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 t  trư c theo n cho m n cách ch n không l p và không th t . Ký hi u Cm ho c  . 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 1n m! n (1.5) Cm = Am = n!(m − n)! n! 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 k (0 n) c a X s là Cn . k
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. m thì N (l, 1) = l = Cl1 . Trư c h t, v i l tùy ý sao cho 1 l m, ta c n ch ng minh r ng N (m, k +1) = Cm+1 . k Gi s N (l, k ) = Clk k−1 , 1 l + +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 sau: a1 < a2 < a3 < · · · < am . Khi đó m i t h p l p h n ta hãy gán th t [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 aih khi i h (t c là ai1 ai2 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 aik+1 . ai2 Ta th y r ng n u ai1 = aj , 1 m thì s các b (k + 1)-th t như trên j chính là N (m − j + 1, k ) theo như gi thi t quy n p. Theo quy t c c ng ta có m m m Cm+1 +1−j − Cm+1 −j = Cm+1 k k k k N (m − j + 1, k ) = N (m, k + 1) = Cm+k−j = +k +k +k j =1 j =1 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 = 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 n là s Stirling lo i hai và đư c ký hi u là Sn,k . S Bn = 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 1 S3,1 S3,2 S3,3 1 3 1 S4,1 S4,2 S4,3 S4,4 1 7 6 1 S5,1 S5,2 S5,3 S5,4 S5,5 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 tt ph uh 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   ··· a b c d f =  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   ··· 1 2 3 n (∗) f =  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) trong đó f (i) = mi ∈ M . hay m1 m2 m3 . . . mn , 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à m.m.m . . . m = mn . n V y ta có S t t c các hàm f : N → 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 tt 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 hai. T đó ta có t ng s các đơn ánh f : N −→ M là M xu t hi n l n th m! = (m)n = An m(m − 1)(m − 2) · · · (m − n + 1) = m (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 h oá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 tt 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 (N ≡ [m]) thì ta có m! đơn ánh f : N −→ M . Do s phân như m t ph n t 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 n m= 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 c a M v i các toàn ánh f : N −→ K và b ng Cm k !Sn,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 k mn = Cm k !Sn,k = Sn,k (m)k . 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. n! 11 1 · ··· Sn,k = . k! i1 ! i2 ! ik ! P k (i1 ,i2 ,...,ik ): ij =n j =1 ij ≥1 k có b s (i1 , i2 , · · · , ik ) sao cho Ch ng minh. Gi s 1.Ta s ij = n, ij 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ó: i S cách ch n i1 ph n t t n ph n t c a t p X là Cn1 , i V i m i cách ch n i1 ph n t thì có Cn2−i1 cách ch n i2 ph n t ; i V i m i cách ch n i1 ph n t và i2 ph n t thì có Cn3−i1 −i2 cách ch n i3 ph n t; .................................................................... i V i m i cách ch n i1 ph n t ,..., ik−1 ph n t thì có Cnk−i1 −i2 −···−ik−1 cách ch n 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 i i · Cn1 Cn2−i1 · · · Cn−i1 −i2 −···−ik−1 = · · = k ! i1 !i2 ! · · · ik ! k ! i1 ! · · · i k ! k! 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! 11 1 · ··· · ··· = k ! i1 ! i2 ! ik ! k! i1 ! i2 ! ik ! P P k k (i1 ,i2 ,...,ik ): ij =n (i1 ,i2 ,...,ik ): 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 1 j (−1)k−j Ck .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). n k Bn+1 = Cn Bk , (B0 = S0,0 = 1) . k=0 Ch ng minh. Xét hàm s L : R [x] → R ∀ k ∈ N∗ (x)k → L(x)k = 1 n mn Theo m nh đ 1.5 ta có Sn,k (m)k v i m i s nguyên dương m. Đi u = k=1 n xn − này nghĩa là đa th c Sn,k (x)k có vô s nghi m. Theo đ nh lý cơ b n k=1 n n xn xn − c a đ i s ta đư c Sn,k (x)k = 0 hay Sn,k (x)k . = k=1 k=1 n n n Suy ra L(xn ) = L Sn,k = Bn . Sn,k (x)k = Sn,k L(x)k = k=1 k=1 k=0 M t khác, (x)n+1 = x(x − 1)n . Suy ra L(x)n+1 = L(x)n = Lx(x − 1)n
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 n n n Cn xk k Cn Lxk k k Lxn+1 = Bn+1 Trong đó L(x + 1) = L Cn Bk còn = = k=0 k=0 k=0 n k Do đó Bn+1 = Cn 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 kn 1 ( Công th c Dobinski ). Bn = 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: 0 1 2 3 4 5 6 7 8 n 1 1 2 5 15 52 203 877 4140 Bn