Luận văn 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ẻ 
1Mục lụ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ột tập hữu hạn . . . . . . . . . . . . . . . . . . . . . . . 15
1.2.4 Bài toán đếm tất cả các hàm đơn ánh từ một tập hữu
hạn vào một tập hữu hạn. . . . . . . . . . . . . . . . . . . 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
Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
2tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3mở đầ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
4và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
5Chương 1
Kiến thức chuẩn bị
Trong chương này chúng tôi sẽ trình bày một số quy tắc đếm, bài toán
đếm và một số kết quả liên quan đến số tất cả các phân hoạch một tập hợp
hữu hạn thành các tập con không rỗng - số Stirling loại 2. (Xem [1], [3], [4],
[6], [9]).
1.1 Các quy tắc đếm cơ bản
Quy tắc tương ứng một -một ([1], tr 46).
Cho hai tập hợp hữu hạn X và Y : X = {1, 2, . . . , n}, |X| = n
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
ϕ =
 1 2 · · · n
ai1 ai2 · · · ain

cho ứng mỗi phần tử j ∈ X với duy nhất một phần tử aij ∈ Y, j = 1, n.
- Ánh xạ ϕ được gọi là một toàn ánh nếu mỗi a ∈ Y , tồn tại ít nhất một i ∈ X
sao cho a = ϕ(i).
Nếu tồn tại một toàn ánh từ X đến Y thì |X| ≥ |Y |.
- Ánh xạ ϕ được gọi là một đơn ánh nếu với mọi i, j ∈ X nếu i 6= j thì
ϕ(i) 6= ϕ(j).
6Nế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
tính hai lần, do vậy có
n(n− 1)
2
đoạn thẳng. Gọi B là tập hợp tất cả các đoạn
thẳng này, |B| = n(n− 1)
2
. Rõ ràng tồn tại một song ánh (một tương ứng 1-1)
giữa hai tập hợp A và B. Do đó ta có
|A| = |B| = n(n− 1)
2
.
Quy tắc cộng ([3], tr 27).
Nếu có m1 cách chọn đối tượng x1, m2 cách chọn đối tượng x2, . . . ,mn
cách chọn đối tượng xn và nếu cách chọn đối tượng xi không trùng với bất
kỳ cách chọn đối tượng xj nào (i 6= j, i, j = 1, n) thì có m1+m2+ · · ·+mn cách
chọn một trong các đối tượng đã cho.
Ta chứng minh quy tắc cộng trên cơ sở của lý thuyết tập hợp như sau.
Định lý 1.1. Cho n tập hợp hữu hạn Xi(i = 1, n) với |Xi| = mi, Xi∩Xj = ∅, i 6= j.
Khi đó số cách chọn một phần tử thuộc tập
n⋃
i=1
Xi là
∣∣∣ n⋃
i=1
Xi
∣∣∣ và
∣∣∣ n⋃
i=1
Xi
∣∣∣= n∑
i=1
|Xi|. (1.1)
7Chứ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⋃
i=1
Xi
∣∣∣= k+1∑
i=1
|Xi|. (1.2)
Thật vậy ta có
X1 ∪X2 ∪ · · · ∪Xk ∪Xk+1 = (X1 ∪X2 ∪ · · · ∪Xk) ∪Xk+1.
Vì Xi ∩Xj = ∅, i 6= j; i, j = 1, 2, . . . , k, k + 1 nên
(X1 ∪X2 ∪ · · · ∪Xk) ∩Xk+1 = (X1 ∩Xk+1) ∪ (X2 ∩Xk+1) ∪ · · · ∪ (Xk ∩Xk+1) = ∅.
Vậy |X1 ∪X2 ∪ · · · ∪Xk ∪Xk+1| = |(X1 ∪X2 ∪ · · · ∪Xk) ∪Xk+1|
= |X1 ∪X2 ∪ · · · ∪Xk| ∪ |Xk+1|
=
k∑
i=1
|Xi|+ |Xk+1|.
=
k+1∑
i=1
|Xi|.
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
8trườ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ó m1m2 . . .mn cách chọn dãy các đối tượng "x1 rồi x2 rồi
x3...rồi xn".
Ta chứng minh quy tắc nhân trên cơ sở của lý thuyết tập hợp như sau.
Định lý 1.2. Giả sử có n tập hữu hạn Xi, i = 1, n, |Xi| = mi. Chọn một bộ
gồm n phần tử (a1, a2, . . . , an) với ai ∈ Xi. Khi đó số cách chọn khác nhau là
|X1 ×X2 × · · · ×Xn| và
|X1 ×X2 × · · · ×Xn| =
n∏
i=1
mi. (1.3)
Chứng minh. Ta chứng minh (1.3) bằng phương pháp quy nạp theo n, n ≥ 2
như sau.
Với n = 2, ta có |X1| = m1, |X2| = m2. Giả sử X1 = {a1, a2, . . . , am1} và
X2 = {b1, b2, . . . , bm2} thì
X1 ×X2 = {(ai, bj) : 1 ≤ i ≤ m1, 1 ≤ j ≤ m2, ai ∈ X1, bj ∈ X2}.
Ta viết X1 ×X2 dưới dạng bảng sau
(a1, b1) (a1, b2) · · · · · · (a1, bm2)
(a2, b1) (a2, b2) · · · · · · (a2, bm2)
9...
...
...
...
(am1 , b1) (am1 , b2) · · · · · · (am1 , bm2)
Đặt Ei = {(ai, b1), (ai, b2), . . . , (ai, bm2) : 1 ≤ i ≤ m1} =⇒ |Ei| = m2.
Ta có X1 ×X2 = E1 ∪E2 ∪ · · · ∪Em1 với Ei ∩Ej = ∅, i 6= j. Theo quy tắc cộng ta
được
|X1 ×X2| = |E1 ∪ E2 ∪ · · · ∪ Em1| =
m1∑
i=1
|Ei| = m1m2.
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 ... inh. (i) Lập luận tương tự như cách tính E2n,2 ta cũng có được
công thức
O2n,2 =
1
2
n∑
j=1
C2j−12n = 2
2(n−1)
(ii) Khi phân hoạch tập n phần tử thành n− 2 tập con không rỗng mà mỗi tập
có số lẻ phần tử thì sẽ có một tập có 3 phần tử và n− 3 tập còn lại mỗi tập có
54
một phần tử.
+ Có C3n cách chọn 3 phần tử để tạo thành một tập có 3 phần tử.
+ Có duy nhất một cách phân hoạch n−3 phần tử thành n−3 tập không rỗng,
mỗi tập có 1 phần tử.
Do đó theo quy tắc nhân ta có On,n−2 = C3n =
n(n− 1)(n− 2)
6
, n ≥ 4.
Tiếp theo ta chứng minh công thức truy hồi cho các số Pn,k và Qn,k.
Mệnh đề 3.7. Ta có
E2n+2,k+1 = E2n,k + (k + 1)E2n,k+1 +
n∑
j=1
C2j2n(E2j+2,2 − 1− 2E2j,2)E2n−2j,k−1,
∀n ∈ N,∀k ∈ N. (3.11)
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ó số chẵn phần tử.
Ta xem tập gồm 2n+2 phần tử như là tập 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ó 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 có chẵn phần tử, sao cho a và b nằm trong hai tập khác nhau.
+ Gọi A 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
55
có chẵn phần tử. Khi đó |A| = E2j+2,2.
+ A1 = {f ∈ A : {a, b} là một tập của phép phân hoạch f} =⇒ |A1| = 1.
+ A2 = {f ∈ A : 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
phân hoạch f} =⇒ |A2| = 2E2j,2.
+ A3 = {f ∈ A : a và b nằm trong hai tập khác nhau của phép phân hoạch f}.
Rõ ràng A = A1 ∪ A2 ∪ A3 và Ai ∩ Aj = ∅ ∀i 6= j; i, j ∈ {1, 2, 3}.
Do đó |A| = |A1|+ |A2|+ |A3| =⇒ |A3| = |A| − |A1| − |A2| = E2j+2,2 − 1− 2E2j,2.
Như vậy, số phép phân hoạch tập có 2j + 2 phần tử này thành 2 tập con có
chẵn phần tử, sao cho a và b nằm trong hai tập khác nhau là E2j+2,2−1−2E2j,2.
Khi đó, 2n− 2j phần tử còn lại phải được phân hoạch thành k− 1 tập con, mỗi
tập có chẵn phần tử và số cách phân hoạch là E2n−2j,k−1.
Hơn nữa, Với mỗi j = 1, 2, 3, ..., n ta có C2j2n cách chọn 2j phần tử từ 2n phần
tử.
Do đó, số cách phân hoạch trong trường hợp 3 là
n∑
j=1
C2j2n(E2j+2,2 − 1− 2E2j,2)E2n−2j,k−1
Từ ba trường hợp trên, ta có điều cần chứng minh.
Mệnh đề 3.8. Ta có
On+2,k+1 = (k + 1)On,k+1 +
n
2

∑
j=0
C2jn (O2j+2,2 − 2O2j,2)On−2j,k−1, (3.12)
trong đó ký hiệu [x] dùng để chỉ phần nguyên của x.
Chứng minh. Ta thấy rằng
O2n,1 = 0, O2n+1,1 = 1, O2n+1,2 = 0.
Để thiết lập công thức (3.12), ta xem tập n + 2 phần tử như là tập ban đầu
có n phần tử và thêm vào hai phần tử mới, giả sử đó là a và b. Tùy theo sự
phân bố của a và b trong các tập con của phép phân hoạch, ta có các trường
hợp sau.
56
a) Trường hợp 1: 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 phân hoạch. Có On,k+1 cách phân hoạch tập có n phần tử thành k+1 tập.
Do a và b có thể nằm trong một tập bất kì trong số k + 1 tập đó nên có tất cả
là (k + 1)On,k+1 cách.
b) Trường hợp 2: a và b nằm trong hai tập khác nhau. Gọi 2j + 2 là số phần
tử của cả hai tập này ( bao gồm cả a và b). Ta 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ó số lẻ phần tử.
+ Gọi B là tập tất cả các phân hoạch tập 2j + 2 phần tử thành 2 tập con mà
mỗi tập có số lẻ phần tử. Khi đó |B| = O2j+2,2.
+ Gọi B1 = {f ∈ B :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 phân hoạch f}. Khi đó |B1| = 2O2j,2.
+ Gọi B2 = {f ∈ B : a và b nằm trong hai tập khác nhau của phép phân hoạch f}.
Rõ ràng B = B1 ∪B2 và B1 ∩B2 = ∅. Suy ra |B2| = |B| − |B1| = O2j+2,2 − 2O2j,2.
Do đó số cách phân hoạch tập gồm 2j+2 phần tử thành 2 tập con sao cho mỗi
tập có số lẻ phần tử mà a và b nằm trong hai tập khác nhau là O2j+2,2− 2O2j,2.
Khi đó, n − 2j phần tử còn lại được phân hoạch thành k − 1 tập con sao cho
mỗi tập có số lẻ phần tử, có On−2j,k−1 cách.
Hơn nữa, có C2jn cách chọn 2j phần tử từ n phần tử. Do mỗi tập có số lẻ phần
tử nên {a}, {b} cũng có thể là các tập, vì vậy j nhận các giá trị là 0, 1, ...,
[n
2
]
.
Do đó số cách phân hoạch trong trường hợp 2 là
n
2

∑
j=0
C2jn (O2j+2,2 − 2O2j,2)On−2j,k−1
Từ hai trường hợp a) và b) ta có
On+2,k+1 = (k + 1)On,k+1 +
n
2

∑
j=0
C2jn (O2j+2,2 − 2O2j,2)On−2j,k−1.
Từ các kết quả trên ta có thể tính truy hồi cho các số phân hoạch chẵn
và lẻ. Dưới đây là bảng số phân hoạch chẵn (lẻ) cho các giá trị n, k đầu tiên.
57
58
* Bảng các phân hoạch chẵn :
En,k k=0 k=1 k= 2 k=3 k=4 k=5 k=6 k=7 k=8 Pn
n=0 1 1
n=1 0 0 0
n=2 0 1 0 1
n=3 0 0 0 0 0
n=4 0 1 3 0 0 4
n=5 0 0 0 0 0 0 0
n=6 0 1 15 15 0 0 0 31
n=7 0 0 0 0 0 0 0 0 0
n=8 0 1 63 210 105 0 0 0 0 379
* Bảng các phân hoạch lẻ :
On,k k=0 k=1 k= 2 k=3 k=4 k=5 k=6 k=7 k=8 Qn
n=0 1 1
n=1 0 1 1
n=2 0 0 1 3
n=3 0 1 0 1 2
n=4 0 0 4 0 1 5
n=5 0 1 0 10 0 1 12
n=6 0 0 16 0 20 0 1 37
n=7 0 1 0 91 0 35 0 1 128
n=8 0 0 64 0 366 0 56 0 1 457
Mệnh đề sau đây cho ta mối liên hệ giữa các số Sn,k, En,k và On,k.
59
Mệnh đề 3.9.
Sn,k =
k∑
j=0
n∑
i=0
CinEi,jOn−i,k−j .
Chứng minh. Trong số n phần tử phân hoạch thành k tập con không rỗng,
gồm có i phần tử được phần hoạch chẵn thành j tập con không rỗng và n− i
phần tử được phần hoạch lẻ thành k−j tập con không rỗng, ở đây i = 0, 1, · · · , n
và j = 0, 1, · · · , k. Do đó ta có
Sn,k =
k∑
j=0
n∑
i=0
CinEi,jOn−i,k−j .
Từ kết quả mệnh đề 4.9 ta suy ra hệ quả sau.
Hệ quả 3.10.
Bn =
n∑
k=0
Sn,k =
n∑
k=0
k∑
j=0
n∑
i=0
CinEi,jOn−i,k−j .
Sau đây chúng tôi đưa ra một vài ví dụ thực tế, mang tính chất áp
dụng, liên quan đến vấn đề tính số phân hoạch chẵn và số phân hoạch lẻ một
tập hữu hạn.
Ví dụ 3.1. Phân phối n quả cầu phân biệt vào m hộp giống nhau.
Có bao nhiêu cách phân phối sao cho mỗi hộp có chứa một số chẵn quả cầu và
bao nhiêu cách phân phối sao cho mỗi hộp có chứa một số lẻ quả cầu?
Chứng minh. Vì các quả cầu là phân biệt nhau và các hộp là giống nhau nên
số cách phân phối để mỗi hộp có một số chẵn (lẻ) phần tử bằng số cách phân
hoạch tập n phần tử thành m tập con sao cho mỗi tập có một số chẵn (lẻ) phần
tử.
Do đó số cách phân phối sao cho mỗi hộp có chứa một số chẵn quả cầu
sẽ bằng En,m cách và số cách phân phối sao cho mỗi hộp có chứa một số lẻ quả
cầu sẽ bằng On,m cách.
60
Ví dụ 3.2. Phân phối n quả cầu phân biệt vào k hộp phân biệt.
Có bao nhiêu cách phân phối sao cho mỗi hộp có chữa một số chẵn quả cầu và
có bao nhiêu cách phân phối sao cho mỗi hộp có chứa một số lẻ quả cầu?.
Chứng minh. Giả sử các hộp là giống nhau. Theo bài trên, số cách phân phối
sao cho mỗi hộp có chứa một số chẵn quả cầu bằng En,k và số cách phân phối
sao cho mỗi hộp có chứa một số lẻ quả cầu sẽ bằng On,k.
Với mỗi cách phân phối này, bằng cách hoán vị, mỗi lần hoán vị ta sẽ
được một phân phối vào k hộp khác nhau. Do đó, số cách phân phối n quả cầu
phân biệt vào k hộp phân biệt sao cho mỗi hộp có chứa một số chẵn quả cầu
bằng k!En,k và số cách phân phối n quả cầu phân biệt vào k hộp phân biệt sao
cho mỗi hộp có chứa một số lẻ quả cầu sẽ bằng k!On,k.
Ví dụ 3.3. Có bao nhiêu cách phân phối 5 đồ vật khác nhau vào 3 hộp giống
nhau sao cho mỗi hộp chứa một số chẵn đồ vật?.
Có bao nhiêu cách phân phối 5 đồ vật khác nhau vào 3 hộp giống nhau sao cho
mỗi hộp chứa một số lẻ đồ vật?.
Chứng minh. Vì các đồ vật là khác nhau và các hộp là giống nhau nên số
cách phân phối 5 đồ vật khác nhau sao cho mỗi tập có một số chẵn phần tử vào
3 hộp khác nhau bằng số cách phân hoạch tập có 5 phần tử phân biệt thành 3
tập con sao cho mỗi tập con có một số chẵn phần tử và bằng E5,3 = 0.
Tương tự, số cách phân phối 5 đồ vật khác nhau vào 3 hộp giống nhau
sao cho mỗi hộp có một số lẻ phần tử bằng O5,3 = 10.
Ví dụ 3.4. Trong một giải bóng đá, tại vòng 1/8 ban tổ chức cần chia các
16 đội thành 8 cặp thi đấu và các đội tiến hành bốc thăm. Hỏi có bao nhiêu
trường hợp như thế?.
Chứng minh. Số trường hợp các đội bắt thăm chính là số phân hoạch tập
gồm có 8 phần tử phân biệt thành 4 tập con không rỗng sao cho mỗi tập con
có chẵn phần tử.
Do đó số trường hợp các đội bốc thăm được sẽ là E16,8 = 15!! = 2027025.
61
Ví dụ 3.5. Có 20 vận động viên trong một cuộc thi đấu cầu lông. Ban tổ chức
cần chia các vận động viên thành 10 cặp thi đấu. Hỏi ban tổ chức có bao nhiêu
cách chia ?.
Chứng minh. Số cách chia 20 vận động viên thành 10 cặp thi đầu chính là
số phân hoạch tập 20 phần tử thành 10 tập con sao cho mỗi tập con có một số
chẵn phần tử.
Do đó số cách chia sẽ bằng E20,10 = 19!! = 654729075.
62
kết luận
Trong luận văn, chúng tôi đã trình bày một số vấn đề sau đây
1. Các quy tắc đếm, một số bài toán đếm cơ bản và một số kết quả liên
quan đến vấn đề số phân hoạch của 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, số Bell).
2. Khái niệm về hàm sinh, hàm sinh mũ và các ví dụ điển hình mà trong
đó áp dụng kỹ thuật hàm sinh, hàm sinh mũ để giải quyết chúng.
3. Công thức ngược và áp dụng công thức ngược để thiết lập công thức
sàng.
4. Chứng minh được công thức tính tổng số phần tử của một tập hữu
hạn X mà chứa trong một số chẵn (hay một số lẻ) các tập con cho trước của
X.
5. Thiết lập công thức tính trực tiếp cho số phân hoạch chẵn Pn và số
phân hoạch lẻ Qn.
6. Chỉ ra được hệ thức liên hệ giữa số phân hoạch chẵn Pn, số phân
hoạch lẻ Qn và Số Bell Bn.
7. Bằng lập luận sơ cấp chứng minh được công thức tính truy hồi cho số
En,k, On,k và chỉ ra được mối liên với số Stirling loại 2 - Sn,k. Sau cùng là một
số bài tập áp dụng.
63
Tài liệu tham khảo
[1] Lê Hạnh (1995), 120 Bài tập giải tích tổ hợp, NXB Giáo Dục, TPHCM.
[2] Vũ Đình Hoà (2002), Lý thuyết tổ hợp và các bài toán ứng dụng, NXB
Giáo Dục, Hà Nội.
[3] Ngô Thúc Lanh (1998), Tìm hiểu đại số tổ hợp phổ thông, NXB Giáo Dục,
Hà Nội.
[4] Ngô Đắc Tân (2003), Lý thuyết tổ hợp và đồ thị, NXB Đại Học Quốc Gia
Hà Nội, Hà Nội.
[5] Hoàng Chí thành, (2001), Giáo trình tổ hợp, NXB Đại Học Quốc Gia Hà
Nội.
[6] Martin Aigner (1997), Combinatorial Theory, Spring Verlag, Berlin Hei-
delberg.
[7] Proudnikov et al (1981), Intergrals and Series of Elementary Functions,
Nauka, Moscou, (In Russian).
[8] Richard P.Stanley (2001), Enumerative Combinatorics, Cambridge Univer-
sity Press, 2001.
[9] Karl H.Wehrhahn (1992), Combinatorics An Introductin, Carslaw Publi-
cations, Australia.