Xem mẫu
- 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
nguon tai.lieu . vn
