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ục lụ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ổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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ột tập hữu hạ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 tr ong 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, t hố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ó l iê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 t hức tính cho các số tổ hợp quan trọng (số xáo trộn
tổng quát D
n
, số Fibonaci F

n
, số Bell B
n
, ). 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 D
n
, S
n,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ị t hứ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
A
1
và A
2
thì A
1
và A
2
có cùng số phần tử.
1.1.2 Quy tắc cộng
Nếu A
1
, A
2
, , A
n
là các tập hữu hạn đôi một rời nhau thì
|A
1
∪A
2
∪ ∪ A
n
| = |A
1
| + |A

2
|+ ··· + |A
n
|
ở đây |A
i
| là số phần tử của tập A
i
.
6
1.1.3 Quy tắc nhân
Nếu A
1
, A
2
, , A
n
là các tập hữu hạn bất kỳ và A
1
×A
2
×···×A
n
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 H
1
,H
2
, ,H
n
, 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
H
i
có a
i
cách thực hiện. Khi đó hành động H: hoặc H
1
xảy ra, hoặc H
2
xảy
ra, , hoặc H
n
xảy ra, có cả thảy a

1
+ a
2
+ ··· + a
n
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 H
i
. Ta cũng giả sử rằng
hành động H
i
có a
i
cách thực hiện. Khi đó hành động H có cả thảy a
1
a
2
a
n
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 A
k
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) = n
k
.
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 A
k
n
hay (n)
k
để chỉ số chỉnh hợp không lặp chập
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 à A
k
n
= n(n −1) (n −k + 1) =
n!
(n − k)!
· Để tồn tại chỉnh hợp, cần phải thỏa mãn k ≤ n. Ta quy ước A
k
n
= 0
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à P
n
= 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ổ hợp
Đị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à C
k
n
. Để tính
C
k
n
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
A có t hể 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 H
1
và H
2
sau đây:
Giai đoạn H

1
: 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ó C
k
n
cách thực hiện giai đoạn H
1
.
Giai đoạn H
2
: 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 H
1
. Ta có A
k
k
= k! cách thực hiện giai đoạn H
2
.
Theo quy tắc nhân t a có A
k
n
= C
k
n
.k!. Suy ra C
k
n
=
A

k
n
k!
. Vì vậy
C
k
n
=







n!
(n − k)!
: k! =
n!
k!(n − k)!
nếu 1 ≤ k ≤ n
0 nếu k > n.
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
rằng C
0
n
= 1. Khi đó đẳng t hức C
k

n
=
n!
k!(n − k)!
cũng đúng cho cả k = 0.
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 A
1
, A
2
, , A
k
của A thỏa mãn hai tính chất sau:
a) A
1
∪A
2
∪ ∪ A
k
= A,
b) A
i
∩A
j
= ∅ ∀i = j i, j ∈ {1, 2, , k}.
Mỗi tập con A
i
đượ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à S
n,k
.
Dễ thấy rằng S
n,k
= 0 nếu k > n và với mọi n ≥ 1 ta có: S
n,0
= 0,
S
n,1
= 1, S
n,n
= 1. Ta cũng thừa nhận rằng S
0,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ố B
n
= S
n,0
+ S
n,1
+ ··· + S
n,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ó S
4,3
= 6.
Ta có thể tính được các số S
n,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ó S
n+1,k
= k.S
n,k
+ S
n,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 = {x
1
, x
2
, , x
n+1
}.
Theo định nghĩa có S
n+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 B
1
và B
2
rời

nhau như sau: B
1
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à {x
n+1
}, còn B
2
bao gồm tất cả các phân hoạch tập A thành k
khối tr ong đó không có khối nào là {x
n+1
}. Khi đó mỗi phân hoạch thuộc B
1
sẽ chia tập {x
1
, x
2
, , x
n
} thành (k − 1) khối và có S
n,k−1
cách chia như thế.
Do đó |B
1
| = S
n,k−1
. Nếu {x
n+1
} không là một khối thì x
n+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ó S
n,k
cách phân hoạch tập
{x
1
, x
2
, , x
n
} thành k khối và x
n+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.S
n,k
cách phân hoạch tập A thành k khối sao cho
{x
n+1
} không là một khối của phân hoạch. Do đó |B
2
| = kS
n,k
. Vì B = B
1
∪B
2
10
và B
1
∩B
2

= ∅ nên theo quy tắc cộng t a có
S
n+1,k
= |B| = |B
1
| + |B
2
| = S
n,k−1
+ kS
n,k
.
Dựa vào hệ thức tr uy hồi trên, ta tính được các số S
n,k
và B
n
. 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:
S
n,k
k=0 k=1 k= 2 k=3 k=4 k=5 k=6 k=7 k=8 B
n
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
x
1
+ x
2
+ ··· + x
k
= 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
 
x
1
0 x ···x
 
x
2
0 ···0 x . . . x

x
k
(∗)

Trong đó, số kí tự x ở đoạn thứ i (được ngăn cách bởi các số 0) tương ứng là
x
i
, x
1
+ x
2
+ ··· + x
k
= n, x
i
≥ 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
(x
1
, x
2
, . . . , x
k
) 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ị t rí của dãy dạng (*). Do đó, số các dãy dạng (*)
là C
k−1
n−1
. Vậy số nghiệm nguyên dương của phương trình x
1
+ x

2
+ ···+ x
k
= n
là C
k−1
n−1
.
Nhận xét : Nếu x
1
+ x
2
+ ··· + x
k
= n với x
1
, x
2
, , x
k
≥ 0. Khi đó :
(x
1
+ 1) + (x
2
+ 1) + ···+ (x
k
+ 1) = n + k và (x
i
+ 1) > 0 ∀ i = 1, k.

Đảo lại, nếu y
1
+ y
2
+ ··· + y
k
= n + k với y
j
> 0 ∀j = 1, k thì
(y
1
− 1) + (y
2
− 1) + ··· + (y
k
− 1) = n với y
j
≥ 0 ∀j = 1, k. Vì vậy số nghiệm
nguyên không âm của phương trình x
1
+ x
2
+ ···+ x
k
= n là C
k−1
n+k−1
= C
n
n+k−1

.
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 = {a
1
, a
2
, , a
n
}. 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(a
1
), f(a
2
), , f(a
n
)) với
f(a
1
), f(a
2
), , f(a
n
) ∈ 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) = m
n
. Vậy ta có

Số tất cả các hàm từ N đến M bằng U(m, n) = m
n
.
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 = {a
1
, a
2
, , a
n
}. 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(a
1
), f(a
2
), , f(a
n
))
với f(a
1
), f(a
2
), , f(a
n
) ∈ M và f(a
i
) = f(a

j
) 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
A
n
m
. Vậy ta có
Số tất cả các hàm đơn ánh từ N đến M bằng A
n
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 A
m
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 = {b
1
, b
2

, , b
m
} và f : N → M là một hàm toàn ánh. Ta
định nghĩa quan hệ
f
∼ trên N như sau: a
1
f
∼ a
2
khi và chỉ khi f(a
1
) = f(a
2
).
Dễ thấy rằng quan hệ
f
∼ là một quan hệ t ương đương trên N. Vì thế mà các
lớp tương đương của
f
∼ 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
= {N
1
, N
2
, , N
m

} với các N
i
(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 : N
i
→ f(N
i
) = f(a
i
) với
a
i
∈ N
i
. 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 : a
i
→ f(a
i
) = g([a
i
]) với [a
i
] là khối của
phân hoạch N chứa a

i
.
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 H
1
và H
2
như
sau:
Giai đoạn H
1
: 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ố Stirli ng loại hai, ta có S
n,m
cách thực hiện giai đoạn H
1
.
Giai đoạn H
2
: Với mỗi phân hoạch N tạo ra từ giai đoạn H
1
, 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 H
2
.
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!S
n,m
.

14
Bây giờ ta có thể chứng minh một kết quả tổ hợp quan trọng sau đây.
Định lý 1.3.1. (theo [3, 1.4]) m
n
=
n

k=0
S
n,k
(m)
k
.
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 F
k
= {f ∈ F : |f(N)| = k}, k =
1, 2, , m. Khi đó F
i
∩F
j
= ∅ nếu i = j và F = F
1
∪ F
2
∪ ··· ∪F
m
.
Theo quy tắc cộng, ta có:
|F | = |F

1
| + |F
2
| + ···+ |F
m
|.
Mỗi f ∈ F
k
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 F
k
" bao gồm hai giai đoạn H
1
và H
2
như sau:
Giai đoạn H
1
: Tạo ra tập con K ⊆ M lực lượng k. Theo định nghĩa của
tổ hợp, ta có C
k
m
cách thực hiện H
1
.
Giai đoạn H
2
: Tạo ra một hàm toàn ánh từ N đến K. Theo Bài toán
1.4, có k!.S
n,k

cách thực hiện giai đoạn H
2
.
Theo quy tắc nhân ta có |F
k
| = C
k
m
.k!.S
n,k
= S
n,k
(m)
k
. Do đó |F | =
m

k=1
S
n,k
(m)
k
.
Theo Bài toán 1.2, ta có |F | = m
n
. Vì S
n,0
= 0 nếu n > 1, S
n,k
= 0 nếu k > n,

(m)
k
= 0 nếu k > m, nên ta nhận được
m
n
= |F | = S
n,0
(m)
0
+
n

k=1
S
n,k
(m)
k
=
n

k=0
S
n,k
(m)
k
.
Theo Định lý 1.3.1, m
n
=
n


k=0
S
n,k
(m)
k
với mọi số nguyên dương m, tức
là đa thức x
n
−
n

k=0
S
n,k
(x)
k
có vô số nghiệm. Theo Định lý cơ bản của đại số,
ta có
x
n
−
n

k=0
S
n,k
(x)
k
= 0,

Suy ra
x
n
=
n

k=0
S
n,k
(x)
k
.
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ó
B
n+1
=
n

k=0
C
k
n
B
k
, (B
0
= 1).

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,
Ta có x
n
=
n

k=0
S
n,k
(x)
k
. Do đó
L(x
n
) =
n

k=0
S
n,k
L((x)
k
) =
n


k=0
S
n,k
= B
n
.
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(x
n+1
)
⇔
n

k=0

C
k
n
L(x
k
) = B
n+1
⇔
n

k=0
C
k
n
B
k
= B
n+1
.
Vậy ta có
B
n+1
=
n

k=0
C
k
n
B

k
.
Mệnh đề 1.3.1. Ta có
S
n,k
=
n!
k!

(i
1
,i
2
, ,i
k
):
k
P
j=1
i
j
=n
i
j
≥1

1
i
1
!

·
1
i
2
!
···
1
i
k
!

.
Chứng minh: Ta xét số các hàm toàn ánh từ N đến K với |N| = n và
K = {b
1
, b
2
, , b
k
}. Theo Bài toán 1.4, số các hàm toàn ánh như trên là k!S
n,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 A
j
= f
−1
(b
j

),
j = 1, 2, , k. Giả sử | A
j
| = i
j
, j = 1, 2, , k. Vì f là toàn ánh nên t a có
A
i
∩A
j
= ∅ ∀i = j, N = A
1
∪A
2
∪···∪A
k
, i
j
≥ 1 ∀j = 1, k và n = i
1
+i
2
+···+i
k
.
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 i
1
phần tử từ tập N gồm n phần tử là tạo ảnh của b
1

, có C
i
1
n
cách.
+ Bước 2: Chọn i
2
phần tử từ tập gồm n − i
1
phần tử còn lại của N là tạo
ảnh của b
2
, có C
i
2
n−i
1
cách.

+ Bước k: Chọn i
k
phần tử từ tập gồm n −i
1
−i
2
−···−i
k−1
phần tử còn lại
của N là tạo ảnh của b
k

, có C
i
k
n−i
1
−i
2
−···−i
k−1
cách.
Theo quy tắc nhân, số các hàm toàn ánh f : N → K mà f(A
j
) = b
j
là
C
i
1
n
C
i
2
n−i
1
C
i
k
n−i
1
−i

2
−···−i
k−1
=
n!
i
1
!i
2
! i
k
!
.
Vì các số i
j
thay đổi thỏa mãn n = i
1
+ i
2
+ ···+ i
k
, i
j
≥ 1 ∀j = 1, k nên số tất
cả các hàm toàn ánh t ừ N đến K là :

(i
1
,i
2

, ,i
k
):
k
P
j=1
i
j
≥1
i
j
=n
n!
i
1
!i
2
! . . . i
k
!
Vậy ta nhận được
k!S
n,k
=

(i
1
,i
2
, ,i

k
):
k
P
j=1
i
j
≥1
i
j
=n
n!
i
1
!i
2
! . . . i
k
!
.
Từ đây ta suy ra
S
n,k
=
n!
k!

(i
1
,i

2
, ,i
k
):
k
P
j=1
i
j
=n
i
j
≥1

1
i
1
!
·
1
i
2
!
···
1
i
k
!

.

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:
* U
n,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 U
0,0
= 1 và
U
n,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ó U
3,2
= 6.
* G
n
=
n

k=0

U
n,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
con không rỗng và trong mỗi tập con ta chọn ra một phần tử đại diện.
* E
n,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 E
0,0
= 1.
* O
n,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 O
0,0
= 1.
*P
n
=
n

k=0
E
n,k
; Q
n
=
n

k=0

O
n,k
.
Như vậy, P
n
(Q
n
) 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 E
2n+1,k
= 0 ∀n, k ∈ N.
Do đó, P
2n+1
= 0, n = 0, 1, 2, Ta gọi P
n
(Q
n
) 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 t hứ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ó
B
n

=
n

k=0
C
k
n
P
k
Q
n−k
.
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,
B
n
=
n

k=0
C
k
n
P
k
Q
n−k
.
Nhận xét. 1) Nếu để ý rằng P
k

=0 với k lẻ thì có thể viết lại
B
n
=
»
n
2
–

k=0
C
2k
n
P
2k
Q
n−2k
.
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 B
n
được biểu diễn qua các số phân hoạch chẵn
P
n
và các số phân hoạch lẻ Q
n
.
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ố E

n,k
và O
n,k
.
19
Mệnh đề 1.4.1. Ta có
E
2n+2,k+1
= E
2n,k
+ (k + 1)E
2n,k+1
+
n

j=1
C
2j
2n
(E
2j+2,2
− 1 −2E
2j,2
)E
2n−2j,k−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 E
2n,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ó E
2n,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)E
2n,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 đó |σ| = E
2j+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
20
phân hoạch τ} ⇒ |σ
2
| = 2E
2j,2
.
+ σ
3
= {τ ∈ σ : a và b nằm trong hai tập k hác nhau của phép phân hoạch τ }.
Rõ ràng σ = σ
1
∪σ
2
∪σ
3
và σ
i
∩σ
j
= ∅ ∀i = j; i, j ∈ {1, 2, 3}.
Do đó |σ| = |σ
1
|+ |σ
2
| + |σ
3
| ⇒ |σ

3
| = |σ| − |σ
1
| − |σ
2
| = E
2j+2,2
−1 − 2E
2j,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 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
là E
2j+2,2
− 1 −2E
2j,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ó một số chẵn phần tử và số cách phân hoạch
là E
2n−2j,k−1
.
Hơn nữa, Với mỗi j = 1, 2, 3, , n ta có C
2j
2n
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

C
2j
2n
(E
2j+2,2
− 1 −2E
2j,2
)E
2n−2j,k−1
.
Từ ba trường hợp trên, ta có điều cần chứng minh.
Mệnh đề 1.4.2. Ta có
(i)E
2m,2
= 2
2(m−1)
− 1
(ii)E
2m,m
= (2m − 1)!!
Chứng minh: (i) Mỗi cách phân hoạch tập 2m phần tử thành hai tập con
không rỗng gồm hai bước :
+ Bước 1: Chọn 2j phần tử từ 2m phần tử cho tập thứ nhất, có C
2j
2m
cách.
+ Bước 2: Chọn 2m − 2j phần tử còn lại cho tập thứ hai, có 1 cách.
Do j có thể nhận các giá trị 1, 2, , m −1 và số cách chọn ứng với mỗi j được
tính 2 lần nên ta có
E

2m,2
=
1
2
m−1

j=1
C
2j
2m
21
Khai triển nhị thức (1 + x)
2m
sau đó lần lượt cho x = 1, x = −1 ta nhận được
E
2m,2
=
1
2
m−1

j=1
C
2j
2m
= 2
2(m−1)
− 1.
(ii ) Ta có
E

2m,m
=
1
m!
C
2
2m
C
2
2m−2
···C
2
4
C
2
2
=
1
m!
·
(2m)!
2!(2m − 2)!
·
(2m −2)!
2!(2m − 4)!
···
4!
2!2!
2!
2!

=
1
m!
·
(2m)!
2
m
= (2m − 1)!!.
Ví d ụ: Tại vòng chung kết World Cup 2006 diễn ra ở nước Đức, Ban tổ chức
chọn ra được 16 đội bóng lọt vào vòng đấu loại trực tiếp. Các đội bóng sẽ bóc
thăm để chia thành 8 cặp đấu, hai đội cùng thuộc một cặp s ẽ thi đấu với nhau
để chọn ra đội thắng vào vòng tứ kết. Khi đó, số tất cả các khả năng chia
cặp đấu là số cách phân hoạch tập gồm 16 phần tử thành 8 tập con không
rỗng mà mỗi tập có một số chẵn (2) phần tử. Số cách đó là E
16,8
. Theo Mệnh
đề 1.4.2 ta có E
16,8
= 15!! = 2.027.025 khả năng. Tương tự, số cách chia 8 đội
thắng thành 4 cặp đấu cho vòng tứ kết là E
8,4
= 7!! = 105 cách và số cách chia
4 đội thắng cho vòng bán kết là E
4,2
= 3!! = 3 cách.
Mệnh đề 1.4.3. Ta có
O
n+2,k+1
= (k + 1)O
n,k+1

+
[
n
2
]

j=0
C
2j
n
(O
2j+2,2
−2O
2j,2
)O
n−2j,k−1
.
Chứng minh: Ta thấy rằng:
O
2n,1
= 0, O
2n+1,1
= 1, O
2n+1,2
= 0
Để chứng minh đẳng thức trên, 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
22
hợp sau :

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ó O
n,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)O
n,k+1
cách phân hoạ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ó một số lẻ phần tử.
+ Gọi σ 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ó một số lẻ phần tử. Khi đó |σ| = O
2j+2,2
.
+ Gọi σ
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 τ}. Khi đó |σ
1
| = 2O
2j,2
.
+ Gọi σ
2
= {τ ∈ σ : a và b nằm trong hai tập khác nhau của phép phân
hoạch τ }.
Rõ ràng σ = σ
1
∪σ

2
và σ
1
∩ σ
2
= ∅. Suy ra |σ
2
| = |σ|−|σ
1
| = O
2j+2,2
− 2O
2j,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ó một số l ẻ phần tử mà a và b nằm trong hai tập khác nhau là
O
2j+2,2
−2O
2j,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ó một số lẻ phần tử, có O
n−2j,k−1
cách.
Hơn nữa, có C
2j
n
cách chọn 2j phần tử từ n phần tử. Do mỗi tập có một 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á t rị là

0, 1, ,

n
2

. Do đó số cách phân hoạch tr ong trường hợp 2 là
[
n
2
]

j=0
C
2j
n
(O
2j+2,2
− 2O
2j,2
)O
n−2j,k−1
.
23
Từ hai trường hợp a) và b) ta có
O
n+2,k+1
= (k + 1)O
n,k+1
+
»

n
2
–

j=0
C
2j
n
(O
2j+2,2
− 2O
2j,2
)O
n−2j,k−1
.
Mệnh đề 1.4.4. Ta có
(i) O
2n,2
= 2
2(n−1)
,
(ii) O
n,n−2
= C
3
n
=
n(n −1)(n −2)
6
, n ≥ 4 .

Chứng minh: (i)Lập luận tương tự như cách tính E
2n,2
ta cũng có được
công thức
O
2n,2
=
1
2
n

j=1
C
2j−1
2n
= 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ó một 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ó một phần tử.
+ Có C
3
n
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ó O
n,n−2
= C

3
n
=
n(n − 1)(n −2)
6
, n ≥ 4.
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 cho cụ thể với một số giá trị n đầu tiên.
24
* Bảng các phân hoạch chẵn:
E
n,k
k=0 k=1 k= 2 k=3 k=4 k=5 k=6 k=7 k=8 P
n
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ẻ:
O
n,k
k=0 k=1 k= 2 k=3 k=4 k=5 k=6 k=7 k=8 Q
n
n=0 1 1
n=1 0 1 1

n=2 0 0 1 1
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
Chú ý: Bằng phương pháp hàm sinh, chúng tôi cũng nhận được một số kết