- Trang Chủ
- Khoa học tự nhiên
- 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ẻ
Xem mẫu
- 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
nguon tai.lieu . vn
