Luận văn Các số tổ hợp liên quan đến số các phân hoạch

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 
1Mụ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
21.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
3mở đầ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.
4Chươ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
5Chươ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.
61.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ì
|A1 ×A2 × · · · × An| = |A1| × |A2| × · · · × |An|.
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.
71.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 Akn 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à Akn = 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à 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ổ 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,
8ta 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à Ckn. Để tính
Ckn 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ó 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ó Ckn cách thực hiện giai đoạn H1.
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ó Akk = k! cách thực hiện giai đoạn H2.
Theo quy tắc nhân ta có Akn = C
k
n.k!. Suy ra C
k
n =
Akn
k!
. Vì vậy
Ckn =


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 C0n = 1. Khi đó đẳng thứ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 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 6= 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ả
9cá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ử ... +1∑
k=1
akC
k
n+1
∫ u
0
Pn+1−k(x)dx
+
n∑
j=1
Pj(t)
n+1−j∑
k=1
akC
k
n+1C
j
n+1−k
∫ u
0
Pn+1−k−j(x)dx
= Pn+1(t) + Pn+1(u) +
n∑
j=1
Pj(t)
n+1−j∑
k=1
akC
j
n+1C
k
n+1−j
∫ u
0
Pn+1−k−j(x)dx
= Pn+1(t) + Pn+1(u) +
n∑
j=1
C
j
n+1Pj(t)
n+1−j∑
k=1
akC
k
n+1−j
∫ u
0
Pn+1−k−j(x)dx
= Pn+1(t) + Pn+1(u) +
n∑
j=1
Cjn+1Pj(t)Pn+1−j(u)
=
n+1∑
j=0
C
j
n+1Pj(t)Pn+1−j(u).
Việc kiểm tra tính duy nhất của Pn(t) hay an khi cho trước dãy còn lại
là đơn giản. Như vậy ta thấy rằng có tương ứng một-một giữa dãy nhị thức
với dãy số xác định bởi :
ak = lim
t→0
Pk(t)
t
, k = 1, 2, ....
78
Tiếp theo ta nêu lên biểu diễn tường minh Pn(t) theo dãy ak đã cho qua
định lý sau.
Định lý 4.2.2. (theo [1, 2]) Dãy đa thức Pn(t), n = 0, 1, 2, ... là dãy nhị thức
khi và chỉ khi tồn tại dãy số thực ak, k = 1, 2, ... sao cho :
(α) P0(t) = 1
(β) Pn(t) = n!
n∑
k=1
( ∑
(i1,i2,...,ik):
kP
j=1
ij=n
ij≥1
ai1
i1!
·ai2
i2!
· · · aik
ik!
)
tk
k!
, n = 1, 2, ...
Chứng minh: Giả sử Pn(t) là dãy nhị thức. Ta sẽ chứng minh bằng quy nạp
toán học rằng (β) đúng.
Việc kiểm tra trường hợp n = 1 là đơn giản .
Giả sử với k ≤ n, ta đã có
Pk(t) = k!
k∑
j=1
( ∑
(i1,i2,...,ij):
jP
m=1
im=k
im≥1
ai1
i1!
·ai2
i2!
· · · aij
ij !
)
tj
j!
, n = 1, 2, ...
Khi đó, theo Định lý 4.2.1 ta có :
Pn+1(t) =
n+1∑
k=1
akC
k
n+1
t∫
0
Pn+1−k(x)dx = an+1C
n+1
n+1 t+
n∑
k=1
akC
k
n+1
t∫
0
Pn+1−k(x)dx
=an+1Cn+1n+1 t+
n∑
k=1
akC
k
n+1(n+1−k)!
n+1−k∑
j=1
( ∑
(i1,i2,...,ij):
jP
m=1
im=n+1−k
im≥1
ai1
i1!
·ai2
i2!
· · · aij
ij !
)
tj+1
(j + 1)!
=an+1Cn+1n+1 t+
n∑
j=1
n+1−j∑
k=1
ak
(n+ 1)!
k!
( ∑
(i1,i2,...,ij):
jP
m=1
im=n+1−k
im≥1
ai1
i1!
·ai2
i2!
· · · aij
ij !
)
tj+1
(j + 1)!
=an+1Cn+1n+1 t+(n+1)!
n∑
j=1
n+1−j∑
k=1
(
ak
k!
∑
(i1,i2,...,ij):
jP
m=1
im=n+1−k
im≥1
ai1
i1!
·ai2
i2!
· · · aij
ij !
)
tj+1
(j + 1)!
=an+1Cn+1n+1 t+ (n+ 1)!
n∑
j=1
( ∑
(i1,i2,...,ij,ij+1):
j+1P
m=1
im=n+1
im≥1
ai1
i1!
·ai2
i2!
· · · aij
ij !
aij+1
ij+1!
)
tj+1
(j + 1)!
79
=an+1Cn+1n+1 t+ (n+ 1)!
n+1∑
j=2
( ∑
(i1,i2,...,ij):
j+1P
m=1
im=n+1
im≥1
ai1
i1!
·ai2
i2!
· · · aij
ij !
)
tj
j!
=(n+ 1)!
n+1∑
j=1
( ∑
(i1,i2,...,ij):
jP
m=1
im=n+1
im≥1
ai1
i1!
·ai2
i2!
· · · aij
ij !
)
tj
j!
.
Bây giờ giả sử ngược lại rằng tồn tại dãy ak, k = 1, 2, ... sao cho các điều
kiện (α), (β) thỏa mãn. Ta cần chứng minh rằng Pn(t) là dãy nhị thức, tức là
cần chứng minh rằng (ii) đúng.
Từ chứng minh ở bước trước, ta thấy rằng việc kiểm tra điều kiện (b)
trong Định lý 4.2.1 bằng quy nạp, xuất phát từ điều kiện (β) là tương tự. Sau
đó sử dụng Định lý 4.2.1 ta sẽ hoàn thành chứng minh.
Định nghĩa 4.2.1. (theo[1, 2]) Cho trước dãy số thực ak, k = 1, 2, .... Giả sử
rằng Pn(t) là dãy các đa thức thỏa mãn (α), (β). Ta gọi Pn(t) là dãy nhị thức
sinh bởi dãy ak, k = 1, 2, ... đã cho.
4.3 Dãy nhị thức sinh bởi một hàm số
Cho hàm số f có khai triển thành chuỗi lũy thừa
f(x) =
∞∑
k=1
ak
xk
k!
(f(0) = 0).
Khi đó dãy số ak = f (k)(0), k = 1, 2, ... sẽ xác định một dãy nhị thức Pn(t)
theo Định lý 4.2.2. Ta sẽ gọi dãy nhị thức này là dãy nhị thức sinh bởi hàm
số f . Nhờ vào Định lý 4.2.2 ta có mệnh đề sau :
Mệnh đề 4.3.1. (theo [1, 4]) Giả sử Pn(t) là dãy nhị thức sinh bởi hàm số f .
Khi đó,
etf(x) =
∞∑
n=0
Pn(t)
xn
n!
.
80
Chứng minh: Ta có :
etf(x) = 1 +
∞∑
k=1
[f(x)]k
tk
k!
= 1 +
∞∑
k=1
tk
k!
( ∞∑
j=1
aj
xj
j!
)k
= 1 +
∞∑
k=1
tk
k!
∞∑
n=1
( ∑
(i1,i2,...,ik):
kP
j=1
ij=n
ij≥1
ai1
i1!
·ai2
i2!
· · · aik
ik!
)
xn
= 1 +
∞∑
n=1
[
n!
∞∑
k=1
( ∑
(i1,i2,...,ik):
kP
j=1
ij=n
ij≥1
ai1
i1!
·ai2
i2!
· · · aik
ik!
)
tk
k!
]
xn
n!
= 1 +
∞∑
n=1
[
n!
n∑
k=1
( ∑
(i1,i2,...,ik):
kP
j=1
ij=n
ij≥1
ai1
i1!
·ai2
i2!
· · · aik
ik!
)
tk
k!
]
xn
n!
= P0(t) +
∞∑
n=1
Pn(t)
xn
n!
=
∞∑
n=0
Pn(t)
xn
n!
.
* Chú ý: Trong các tài liệu hiện hành viết về dãy nhị thức, để kiểm tra Pn(t)
là một dãy nhị thức người ta đã sử dụng phương pháp dựa trên các phép tính
toán tử. Đây là một phương pháp chính thống và đã đạt được nhiều kết quả.
Tuy nhiên phương pháp này chỉ áp dụng với giả thiết deg(Pn(t)) = n.
Mệnh đề 4.3.2. Giả sử f(x) =
∞∑
k=1
ak
xk
k!
và Pn(t) là một dãy các đa thức
(P0(t) = 1). Nếu etf(x) =
∞∑
n=0
Pn(t)
xn
n!
thì Pn(t) là một dãy nhị thức.
Chứng minh: Ta có :
etf(x)euf(x) = e(t+u)f(x).
Theo giả thiết ta có : e(t+u)f(x) =
∞∑
n=0
Pn(t+ u)
xn
n!
81
Mặt khác
etf(x)euf(x) =
(
∞∑
n=0
Pn(t)
xn
n!
)(
∞∑
n=0
Pn(u)
xn
n!
)
=
∞∑
n=0
(
n∑
k=0
CknPk(t)Pn−k(u)
)
xn
n!
.
Do đó ta có :
Pn(t+ u) =
n∑
k=0
CknPk(t)Pn−k(u).
Vậy Pn(t) là dãy nhị thức.
4.4 Một số ví dụ về dãy nhị thức
Ta sẽ vận dụng Mệnh đề 4.3.2 để khảo sát các dãy đa thức trong các ví dụ
sau là dãy nhị thức. Trong đó, Ví dụ 4.5 nêu lên hai dãy đa thức hoàn toàn
mới chưa có trong tài liệu tham khảo; Ví dụ 4.6 và Ví dụ 4.7 nêu lên hai dãy
đa thức đã có nhưng ở đây chúng tôi hình thành hai dãy đa thức này theo
con đường khác.
Ví dụ 4.2. Dãy các đa thức sn(t) = (t)n = t(t− 1)(t− 2)...(t− n+ 1). Quy ước
s0(t) = (t)0 = 1, t ∈ R.
Ta có :
∞∑
n=0
(t)n
xn
n!
= 1 +
tx
1!
+
t(t− 1)x2
2!
+ · · ·+ t(t− 1) . . . (t− n+ 1)x
n
n!
+ · · ·
= (1 + x)t = eln(1+x)
t
= etln(1+x).
Do đó sn(t) là dãy nhị thức.
Ví dụ 4.3. Dãy các đa thức Cn(t) = (t)n = t(t+1)(t+2)...(t+ n− 1). Quy ước
C0(t) = (t)
0 = 1, t ∈ R.
82
Ta có :
∞∑
n=0
(t)n
xn
n!
= 1 +
tx
1!
+
t(t+ 1)x2
2!
+ · · ·+ t(t+ 1) . . . (t+ n− 1)x
n
n!
+ · · ·
= (1− x)−t = eln(1−x)−t = et(−ln(1−x)).
Suy ra Cn(t) là dãy nhị thức.
Ví dụ 4.4. Dãy đa thức mũ en(t) =
n∑
k=0
Sn,kt
k (e0(t) = 1, t ∈ R) là dãy nhị
thức.
Thật vậy, theo Mệnh đề 2.2.3 ta có
∞∑
n=0
en(t)
xn
n!
=
∞∑
n=0
(
n∑
k=0
Sn,kt
k
)
xn
n!
= et(e
x
−1).
Do đó en(t) =
n∑
k=0
Sn,kt
k là dãy nhị thức.
Ví dụ 4.5. Dãy đa thức Pn(t) =
n∑
k=0
En,kt
k và Qn(t) =
n∑
k=0
On,kt
k với
P0(t) = Q0(t) = 1, t ∈ R là dãy nhị thức.
Thật vậy, theo Mệnh đề 2.2.6 ta có : et(chx−1) =
∞∑
n=0
Pn(t)
xn
n!
và
et.shx =
∞∑
n=0
Qn(t)
xn
n!
. Do đó Pn(t), Qn(t) là các dãy nhị thức.
Ta thấy rằng dãy đa thức Pn(t) =
n∑
k=0
En,kt
k là dãy nhị thức nhưng
deg(Pn(t)) < n (vì En,n = 0 ∀n ≥ 1).
Ví dụ 4.6. Dãy đa thức Gn(t) =
n∑
k=0
Un,kt
k =
n∑
k=0
Ckn.k
n−ktk với
G0(t) = 1, t ∈ R là dãy nhị thức.
Thật vậy, theo Mệnh đề 2.2.1 ta có
etxe
x
=
∞∑
n=0
Gn(t)
xn
n!
=
∞∑
n=0
n∑
k=0
Ckn.k
n−ktk
xn
n!
.
Do đó Gn(t) là dãy nhị thức.
83
Ví dụ 4.7. Dãy đa thức Ln(t) =
n∑
k=0
Ln,kt
k =
n∑
k=0
n!
k!
Ck−1n−1t
k với L0(t) = 1, t ∈ R
là dãy nhị thức.
Thật vậy, theo Mệnh đề 2.2.8 ta có
e
tx
1− x =
∞∑
n=0
(
n∑
k=0
n!
k!
Ck−1n−1t
k
)
xn
n!
.
Do đó Ln(t) là dãy nhị thức.
Từ những ví dụ trên ta thấy rằng có mối liên hệ giữa:
Dãy số {an,k}∞n=0 với dãy nhị thức Pn(t) =
n∑
k=0
an,kt
k và hàm sinh tương ứng
với dãy nhị thức:
∞∑
n=0
Pn(t)
xn
n!
.
Có nghĩa là với mỗi dãy số an,k ta có dãy nhị thức tương ứng và hàm sinh
tương ứng với dãy nhị thức. Ta có một số mối liên hệ sau:
1. Dãy sn,k =⇒ (t)n =
n∑
k=0
sn,kt
k =⇒ etln(1+x).
2. Dãy Cn,k =⇒ (t)n =
n∑
k=0
Cn,kt
k =⇒ et(−ln(1−x)).
3. Dãy Sn,k =⇒ en(t) =
n∑
k=0
Sn,kt
k =⇒ et(ex−1).
4. Dãy En,k =⇒ Pn(t) =
n∑
k=0
En,kt
k =⇒ et(chx−1).
5. Dãy On,k =⇒ Qn(t) =
n∑
k=0
On,kt
k =⇒ et.shx.
6. Dãy Un,k = Cknk
n−k =⇒ Gn(t) =
n∑
k=0
Un,kt
k =⇒ etxex.
7. Dãy Ln,k =
n!
k!
Ck−1n−1 =⇒ Ln(t) =
n∑
k=0
n!
k!
Ck−1n−1t
k =⇒ e
tx
1− x .
84
kết luận
Luận văn đã đạt được những kết quả chính sau đây:
1. Thông qua bài toán phân hoạch tập hợp, luận văn đưa ra một số loại
số tổ hợp mới (En,k, On,k, Un,k, Ln,k, Pn, Qn, Gn, ...), thiết lập được công thức
truy hồi và 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 đó. Các Định lý 1.4.1, 1.4.2; Mệnh đề 1.4.1, 1.4.2, 1.4.3, 1.4.4, 1.4.5, 1.4.6,
1.4.7, 1.5.3; Hệ quả 1.4.1, 1.4.2 chưa được đề cập tới trong các tài liệu tham
khảo.
2. Luận văn giải quyết được một số bài toán đếm bằng phương pháp
hàm sinh. Chúng tôi đã có được một số kết quả mới sau: tìm được hàm sinh
mũ cho các số tổ hợp được trình bày trong Chương 1 (Hệ quả 2.2.1, 2.2.6,
2.2.8), đưa ra công thức biểu diễn cho số ee (Hệ quả 2.2.2), mối liên hệ giữa số
e với số Bell (Hệ quả 2.2.5), chứng minh được công thức Dobinski (Mệnh đề
2.2.5), mối liên hệ giữa số Bell Bn với các số phân hoạch chẵn (Pn), lẻ (Qn),
công thức biểu diễn cho các số tổ hợp Pn, Qn (Hệ quả 2.2.7).
3. Giới thiệu 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 trình bày 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.
4. Kiểm tra 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. Trong đó, Ví dụ 4.5 trình bày hai dãy nhị thức mới, chưa có
trong tài liệu tham khảo. Hơn nữa, chúng tôi đưa ra được một số liên hệ giữa
dãy số {an,k}∞n=0 với dãy nhị thức Pn(t) =
n∑
k=0
an,kt
k và hàm sinh tương ứng với
dãy nhị thức:
∞∑
n=0
Pn(t)
xn
n!
.
85
tài liệu tham khảo
Tiếng Việt
[1] Phạm Xuân Bình (2002), " Quá trình đếm ", Báo cáo đề tài nghiên cứu
khoa học, Trường ĐH Quy Nhơn.
[2] Vũ Đình Hòa (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] Nguyễn Đức Nghĩa, Nguyễn Tô Thành (2003), Toán rời rạc, NXB Đại học
Quốc Gia 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.
Tiếng Anh
[5] Martin Aigner (1997), Combinatorial Theory, Spring Verlag, Berlin Hei-
delberg.
[6] Proudnikov et al (1981), Intergrals and Series of Elementary Functions,
Nauka, Moscou, (In Russian).
[7] Richard P.Stanley (2001), Enumerative Combinatorics, Cambridge Uni-
versity Press.
[8] Karl H.Wehrhahn (1992), Combinatorics An Introductin, Carslaw Publi-
cations, Australia.
86
lời cảm ơn.
Luận văn được hoàn thành dưới sự hướng dẫn khoa học của PGS.TS.
Nguyễn Đức Minh. Tác giả xin bày tỏ lòng biết ơn sâu sắc đến Thầy. Thầy
đã tận tình hướng dẫn và động viên tác giả trong suốt quá trình thực hiện
luận văn.
Tác giả xin bày tỏ lòng biết ơn chân thành đến thầy Phạm Xuân Bình -
Khoa Toán - ĐH Quy Nhơn. Một số vấn đề mới trong luận văn này đã được
Thầy đặt ra cho chúng tôi giải quyết. Thầy đã giúp cho tác giả có niềm say
mê nghiên cứu khoa học, gợi mở cho chúng tôi nhiều ý tưởng hay và truyền
đạt nhiều kiến thức quý báu trong quá trình thực hiện luận văn này.
Tác giả xin chân thành cảm ơ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 K8, Trường THPT Nguyễn Chí Thanh- Khánh Hòa và
các bạn đồng nghiệp đã tạo điều kiện thuận lợi và giúp đỡ tác giả trong quá
trình học tập và hoàn chỉnh luận văn.
Đoàn Nhật Thịnh