Định lý (Công thức tích cho hàm sinh thông thường)
Gọi an là số cách để xây dựng một cấu trúc nào đó trên tập n phần tử, và
bn là số cách để xây dựng một cấu trúc khác trên tập n phần tử. Gọi cn
là số cách để chia [n] thành các đoạn S = {1, 2, · · · , i} và
T = {i + 1, i + 2, · · · , n}, (S và T có thể bằng rỗng), và xây dựng cấu trúc
loại thứ nhất lên S, và cấu trúc loại thứ hai lên T. Gọi A(x), B(x), và C(x)
là các hàm sinh tương ứng của các dãy {an}, {bn}, và {cn}. Thì
A(x)B(x) = C(x)
103 trang |
Chia sẻ: HoaNT3298 | Lượt xem: 827 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Bài giảng Nhập môn Lý thuyết Tổ hợp - Chương 2: Tổ hợp tính toán - Nguyễn Anh Thi, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
nguyên
Định nghĩa
Một hình mẫu Ferrers của một phân hoạch các số nguyên
p = (x1, x2, . . . , xk) là tập hợp tất cả n hình vuông với chiều ngang và
chiều dọc sao cho ở dòng thứ i, ta có xi ô vuông, và tất cả các dòng đều
bắt đầu từ cùng một cột.
Ví dụ
Hình mẫu Ferrers của phân hoạch p = (4, 2, 1).
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 27 / 99
Phân hoạch Phân hoạch số nguyên
Định nghĩa
Khi ta lấy đối xứng hình mẫu Ferrers của một phân hoạch p qua đường
chéo chính, ta được một hình mẫu khác. Hình mẫu đó được gọi là phân
hoạch liên hợp của p.
Ví dụ
Tìm phân hoạch liên hợp của phân hoạch p trong ví dụ trên.
Định nghĩa
Một phân hoạch được gọi là tự liên hợp nếu nó bằng với chính liên hợp
của nó.
Ví dụ
Các phân hoạch (4, 3, 2, 1), (5, 1, 1, 1, 1), và (4, 2, 1, 1) là tự liên hợp.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 28 / 99
Phân hoạch Phân hoạch số nguyên
Định lý
Số các phân hoạch của n thành nhiều nhất k phần bằng với số các phân
hoạch của n thành các phần mà không lớn hơn k.
Chứng minh. Ta thấy Số các phân hoạch của n thành k phần bằng số các
hình mẫu Ferrer với nhiều nhất k dòng. Hơn nữa, số các phân hoạch của
n thành các phần mà không lớn hơn k thì bằng với số hình mẫu Ferrer với
nhiều nhất là k cột. Ta chỉ cần lấy liên hợp hai loại hình mẫu Ferrer trên
là được kết quả.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 29 / 99
Phân hoạch Phân hoạch số nguyên
Định lý
Số các phân hoạch của n thành những phần lẻ rời nhau thì bằng với số
các phân hoạch tự liên hợp của n.
Chứng minh. Ta định nghĩa một song ánh f từ tập các phân hoạch tự liên
hợp của n vào tập các phân hoạch của n thành các phần lẻ rời nhau.
Chọn pi = (pi1, pi2, . . . , pit) là một phân hoạch tự liên hợp của n. Từ đó ta
có được hình mẫu Ferrers của nó. Ta bỏ hết các ô vuông ở hình dòng đầu
tiên và cột đầu tiên của hình mẫu. Bởi vì pi là phân hoạch tự liên hợp nên
số ô vuông bị bỏ đi là 2pi1 − 1. Đặt f(pi)1 = 2pi1 − 1, nghĩa là phần đầu tiên
của ảnh của f(pi) là 2pi1 − 1..., tương tự, f(pi)2 = 2pi2 − 3...Tiếp tục làm như
vậy ta được
f(pi) = (2pi1 − 1, 2pi2 − 3, . . . , 2pii − (2i− 1), . . . )
là một phân hoạch có các phần lẻ rời nhau, (do pi1 ≥ pi2 ≥ · · · ≥ pit)
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 30 / 99
Phân hoạch Phân hoạch số nguyên
Ngược lại, gọi α là một phân hoạch của n thành các phần lẻ rời nhau,
α = (2a1 − 1, 2a2 − 3, . . . , 2au − (2u− 1)). Gọi pi là một phân hoạch sao
cho pi = (a1, a2, . . . , au). Khi đó, f(pi) = α.
Ví dụ
Nếu pi = (6, 6, 4, 3, 2, 2), thì f(pi) = (11, 9, 3)
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 31 / 99
Phân hoạch Phân hoạch số nguyên
Mối liên hệ giữa số các phân hoạch số nguyên của n và
số các phân hoạch của tập [n]
Gọi pi = (pi1, pi2, . . . , pik) là một phân hoạch của tập [n], với pii là các
'block' của pi. Ta sắp xếp các block trên theo kích cỡ (|pi1|, |pi2|, . . . , |pik|)
không tăng để nhận được một dãy a1 ≥ a2 ≥ · · · ≥ ak. Khi đó
a = (a1, a2, . . . , ak) là một phân hoạch các số nguyên của n. Ta nói a là
loại của phân hoạch pi.
Ví dụ
Tìm loại của phân hoạch {1, 5, 6}, {2, 7}, {3, 9}, {4, 8}, {10}?
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 32 / 99
Phân hoạch Phân hoạch số nguyên
Mối liên hệ giữa số các phân hoạch số nguyên của n và
số các phân hoạch của tập [n]
Định lý
Gọi a = (a1, a2, . . . , ak) là một phân hoạch của số nguyên n, gọi mi là số
bội của i trong phân hoạch a. Khi đó, số các phân hoạch tập hợp của [n]
có 'loại' a là
Pa =
(
n
a1, a2, . . . , ak
)
∏
i≥1 mi!
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 33 / 99
Phân hoạch Phân hoạch số nguyên
Bảng tổng kết
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 34 / 99
Phân hoạch Phân hoạch số nguyên
Bảng tổng kết
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 35 / 99
Chu trình trong hoán vị
Chu trình trong hoán vị
Bổ đề
Gọi p : [n] → [n] là một hoán vị, và x ∈ [n]. Khi đó tồn tại một số nguyên
dương 1 ≤ i ≤ n sao cho pi(x) = x.
Định nghĩa
Gọi p : [n] → [n] là một hoán vị, x ∈ [n], và i là một số nguyên dương nhỏ
nhất sao cho pi(x) = x. Khi đó ta nói x, p(x), p2(x), · · · , pi−1(x) tạo thành
một i− chu trình trong p.
Hệ quả
Mọi hoán vị đều được phân tích thành hội các chu trình rời nhau.
Ví dụ
321564 = (31)(2)(564)
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 36 / 99
Chu trình trong hoán vị
Định lý
Gọi a1, a2, . . . , an là các số nguyên không âm sao cho ta có tổng∑n
i=1 i.ai = n. Khi đó số các hoán vị độ dài n với ai chu trình có chiều dài
i với i ∈ [n] là
n!
a1!a2! . . . an!.1a12a2 . . .nan
.
Chú ý
Nếu một hoán vị p có ai chu trình có độ dài i, với i = 1, 2, . . . ,n, thì ta nói
(a1, a2, . . . , an) là loại của p.
Ví dụ
Số các hoán vị độ dài n có duy nhất một chu trình, hay nói cách khác, số
các hoán vị loại (0, 0, . . . , 1) bằng (n− 1)!.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 37 / 99
Chu trình trong hoán vị
Chu trình trong hoán vị
Định nghĩa
Gọi c(n, k) là số các hoán vị độ dài n với k chu trình, và
s(n, k) = (−1)n−kc(n, k). Khi đó ta gọi s(n, k) là số Stirling dạng thứ nhất,
và c(n, k) là số Stirling không dấu dạng thứ nhất.
Định lý
Gọi n và k là các số nguyên dương thỏa mãn n ≥ k, ta có
c(n, k) = c(n− 1, k− 1) + (n− 1)c(n− 1, k).
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 38 / 99
Chu trình trong hoán vị
Hướng dẫn. Ta xét hai trường hợp.
n tạo thành chu trình bởi chính nó, và n− 1 phần tử còn lại tạo
thành k− 1 chu trình. Khi đó số các hoán vị là c(n− 1, k− 1).
Nếu n không tạo thành chu trình bởi chính nó, thì n− 1 phần tử còn
lại sẽ tạo thành k chu trình, và phần tử n sẽ được thêm vào một chu
trình nào đó. Số cách tạo ra k chu trình là c(n− 1, k). Sau đó ta
thêm n vào sau mỗi phần tử. Số cách thêm là n− 1. Vậy ta có tất cả
(n− 1)c(n− 1, k) cách.
Kết hợp hai trường hợp trên ta được số các hoán vị độ dài n có k chu trình
là
c(n, k) = c(n− 1, k− 1) + (n− 1)c(n− 1, k).
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 39 / 99
Chu trình trong hoán vị
Bổ đề
Cho n là số nguyên dương, ta có
n∑
k=0
c(n, k)xk = x(x + 1) . . . (x + n− 1).
Hướng dẫn. Ta chứng minh rằng hệ số của xk ở vế phải chính là số
Stirling không dấu dạng thứ nhất.
Gọi Gn(x) = x(x + 1) . . . (x + n− 1) =
∑n
k=0 an,kxk. Ta thấy
Gn(x) = (x + n− 1)Gn−1(x) = (n + n− 1)
∑n−1
k=0 an−1,kxk =∑n
k=1 an−1,k−1xk + (n− 1)
∑n−1
k=0 an−1,k. Ta vừa chứng minh được
n∑
k=0
an,kxk =
n∑
k=1
an−1,k−1xk + (n− 1)
n−1∑
k=0
an−1,kxk.
Từ đây suy ra
an,k = an−1,k−1 + (n− 1)an−1,k.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 40 / 99
Chu trình trong hoán vị
Ta thấy c(n, k) và an,k có cùng hệ thức đệ quy, và cùng điều kiện đầu
c(0, 0) = a0,0 = 1, và c(n, 0) = an,0 nếu n > 0, nên ta có được
c(n, k) = an,k.
Chú ý
Ta thay x bằng −x trong hệ thức trên, và nhân cả hai vế cho (−1)n, ta
được công thức
n∑
k=0
s(n, k)xk = (x)n. (1)
So sánh với công thức Stirling dạng thứ hai
xn =
n∑
k=0
S(n, k)(x)k. (2).
Ta thấy số Stirling dạng thứ nhất gần như là 'ảnh ngược' của số Stirling
dạng thứ hai .
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 41 / 99
Chu trình trong hoán vị
Để thấy được tính chất này, ta xem suy luận sau.
Gọi V là không gian vectơ gồm các đa thức có hệ số thực. Khi đó ta
biết rằng B = {1, x, x2, . . . } là một cơ sở của không gian V. Ngoài ra,
ta cũng chứng minh được B′ = {1, (x)1, (x)2, (x)3, . . . } cũng là một
cơ sở của V.
Gọi S là ma trận mà có hệ số ở vị trí (n, k) bằng S(n, k), và s là ma
trận mà có hệ số ở vị trí (n, k) bằng s(n, k). Khi đó s chính là ma
trận đổi cơ sở từ B sang B′, và S là ma trận đổi cơ sở từ B′ sang B.
Rõ ràng ta thấy S = s−1.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 42 / 99
Nguyên lý bù trừ
Nguyên lý bù trừ
Định lý (Nguyên lý bù trừ)
Gọi A1,A2, . . . ,An là các tập con của tập A, ta có
|A1 ∪ A2 ∪ · · · ∪ An| =
n∑
j=1
(−1)j−1
∑
i1,i2,...,ij
|Ai1 ∩ Ai2 ∩ · · · ∩ Aij |
trong đó (i1, i2, . . . , ij) là các tập con j phần tử của [n].
Ví dụ
Tìm số nghiệm nguyên không âm của phương trình
x1 + x2 + x3 + x4 = 18 (∗)
thỏa điều kiện xi ≤ 7,∀i = 1, . . . , 4.
Đáp án. 246
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 43 / 99
Nguyên lý bù trừ
Ví dụ
Có bao nhiêu cách lấy 6 lá bài từ 52 lá sao cho
a. có đầy đủ bốn chất (cơ, rô, chuồn, bích)?8682544.
b. ít nhất một chất không có. 11675976.
Ví dụ
Tìm số nghiệm nguyên không âm của phương trình
x1 + x2 + x3 + x4 = 25 (∗)
thỏa điều kiện x1 ≤ 5, x2 ≤ 6, x3 ≤ 7.
Ví dụ
Tìm số nghiệm nguyên không âm của phương trình
x1 + x2 + x3 + x4 + x5 + x6 = 20 (∗) thỏa điều kiện xi ≤ 8, (i = 1, 2, . . . , 6).
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 44 / 99
Nguyên lý bù trừ
Định lý
Cho tập vũ trụ U có N phần tử và A1,A2, . . . ,An là n tập con của tập hợp
U . Khi đó số phần tử thuộc vào đúng m tập hợp, ký hiệu Nm, là
Nm =
∑n−m
i=0 (−1)i
(
m + i
i
)
Sm+i =
Sm−
(
m + 1
m
)
Sm+1 + · · ·+(−1)n−m
(
n
m
)
Sn. Với Sk là tổng số phần
tử của tất cả tập giao của đúng k tập hợp từ các tập {Ai}i=1,2,...,n, cụ thể
S1 =
∑
i
|Ai|, S2 =
∑
i6=j
|Ai ∩ Aj|, . . . . . . ,Sn = |A1 ∩ A2 ∩ · · · ∩ An|.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 45 / 99
Nguyên lý bù trừ
Hệ quả
Nếu ta gọi N∗m là số phần tử thuộc ít nhất m tập hợp thì
N∗m =
∑n−m
i=0 (−1)i
(
m + i
m− 1
)
Nm+i =
Sm −
(
m
m− 1
)
Sm+1 + · · ·+ (−1)n−m
(
n− 1
m− 1
)
Sn.
Ví dụ
Có bao nhiêu chuỗi tam phân (chỉ gồm 0, 1, 2) độ dài 4 thỏa mãn
a.chứa đúng 2 chữ số 1, b. chứa nhiều hơn 2 chữ số 1.
Hướng dẫn. Gọi U là tập hợp tất cả các chuỗi tam phân có độ dài 4. Gọi
Ai là tập hợp tất cả các chuỗi tam phân có chữ số tại vị trí i là 1. Ta tính
được N = 34, S1 =
(
4
1
)
33, S2 =
(
4
2
)
32, S3 =
(
4
3
)
31, và
S4 =
(
4
4
)
30. Áp dụng định lý trên ta được kết quả N2 = 24, N∗2 = 33.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 46 / 99
Nguyên lý bù trừ
Định lý
Với mọi số nguyên dương n và k, ta có đẳng thức
S(n, k) = 1k!
k∑
i=0
(−1)i
(
k
i
)
(k− i)n =
k∑
i=0
(−1)i 1i!(k− i)! (k− i)
n
Chứng minh. Trước tiên, ta tìm số toàn ánh từ tập [n] vào tập [k]. Dễ
dàng thấy rằng số các ánh xạ từ [n] vào trong [k] là kn. Với mọi i ∈ [k], gọi
Ai là tập tất cả các ánh xạ từ [n] vào [k] mà tập ảnh của nó không chứa i.
Ta thấy số phần tử |Ai| = (k− 1)n.Tương tự ta có
|Ai1 ∩ Ai2 ∩ · · · ∩ Aij | = (k− j)n với mọi j ≤ k. Áp dụng công thức nguyên lý
bù trừ ta được,
|A1 ∪ A2 ∪ · · · ∪ An| =
∑n
j=1(−1)j−1
∑
i1,i2,...,ij |Ai1 ∩ Ai2 ∩ · · · ∩ Aij | =∑k
i=1(−1)i−1
(
k
i
)
(k− i)n. Suy ra số toàn ánh là
kn −∑ki=1(−1)i−1( ki
)
(k− i)n =∑ki=0(−1)i( ki
)
(k− i)n.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 47 / 99
Nguyên lý bù trừ
Hơn nữa, từ chương trước ta có số toàn ánh bằng k!S(n, k). Do đó ta được
S(n, k) = 1k!
k∑
i=0
(−1)i
(
k
i
)
(k− i)n.
Định lý
Gọi f và g là các hàm được định nghĩa trên tập hợp [n], và f, g thỏa điều
kiện
g(S) =
∑
T⊆S
f(T).
Khi đó
f(S) =
∑
T⊆S
g(T)(−1)|S−T|
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 48 / 99
Hàm sinh Định nghĩa hàm sinh
Định nghĩa hàm sinh
Định nghĩa
Cho {an}n≥0 là một dãy các số thực, thì chuỗi lũy thừa hình thức
A(x) =
∑
n≥0 anxn được gọi là hàm sinh thông thường (hay hàm sinh) của
dãy {an}n≥0.
Ví dụ
Xét tập hợp X với m phần tử, gọi an là số tập con có n phần tử của X,
an =
(
m
n
)
.
Ta được hàm sinh của dãy số thực {an}n≥0 là
A(x) = 1 +
(
m
1
)
x +
(
m
2
)
x2 + · · ·+ · · ·+
(
m
m
)
xm = (1 + x)m
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 49 / 99
Hàm sinh Định nghĩa hàm sinh
Định nghĩa hàm sinh
Ví dụ
Tìm hàm sinh của ar, với ar là số cách để chọn r viên bi từ 3 viên bi màu
xanh, 3 viên bi màu trắng, 3 viên bi màu đỏ, và 3 viên bi màu vàng.
Bài toán trên có thể đưa về bài toán tìm nghiệm nguyên của phương trình
e1 + e2 + e3 + e4 = r
với 0 ≤ ei ≤ 3. Ở đây e1 là số quả cầu màu xanh được chọn, e2 là số quả
cầu màu trắng, e3 là số quả cầu màu đỏ, và e4 là số quả cầu màu vàng.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 50 / 99
Hàm sinh Định nghĩa hàm sinh
Định nghĩa hàm sinh
Ta xây dựng một tích của các nhân tử đa thức sao cho sau khi nhân các đa
thức đó lại với nhau, ta được tất cả các hạng tử có dạng xe1xe2xe3xe4 , trong
đó 0 ≤ ei ≤ 3. Như vậy ta cần 4 nhân tử, và mỗi nhân tử bằng
1 + x + x2 + x3, bao gồm tất cả các lũy thừa nhỏ hơn hay bằng 3 của x. Ta
được hàm sinh cần tìm là
(1 + x + x2 + x3)4 =1 + 4x + 10x2 + 20x3 + 31x4 + 40x5 + 44x6+
+ 31x8 + 40x7 + 20x9 + 10x10 + 4x11 + x12.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 51 / 99
Hàm sinh Định nghĩa hàm sinh
Định nghĩa hàm sinh
Ví dụ
Tìm hàm sinh của {ar}r≥0, với ar là số cách để chọn r quả từ 6 quả lê, 5
quả cam, 3 quả chanh, 3 quả mận.
Giải. Tương tự như ví dụ trên ar là nghiệm nguyên của phương trình
e1 + e2 + e3 + e4 = r
với 0 ≤ e1 ≤ 6, 0 ≤ e2 ≤ 5, 0 ≤ e3 ≤ 3, và 0 ≤ e4 ≤ 3. Để tìm hàm sinh
ta xây dựng một tích của các nhân tử đa thức sao cho sau khi nhân các đa
thức đó lại với nhau, ta được tất cả các hạng tử có dạng xe1xe2xe3xe4 . Các
nhân tử đa thức tương ứng là: 1 + x + x2 + x3 + x4 + x5 + x6,
1+x+x2+x3+x4+x5, 1+x+x2+x3, và 1+x+x2+x3. Vậy hàm sinh cần tìm là
(1 + x + x2 + x3 + x4 + x5 + x6)(1 + x + x2 + x3 + x4 + x5)(1 + x + x2 + x3)2.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 52 / 99
Hàm sinh Định nghĩa hàm sinh
Định nghĩa hàm sinh
Ví dụ
Tìm hàm sinh của {ar}r≥0, với ar là số cách chia r đồng xu vào 5 hộp với
điều kiện: Số đồng xu ở hộp 1 và hộp 2 là số chẵn và không quá 10, và
các hộp còn lại chứa 3 đến 5 đồng xu.
Giải. ar là số nghiệm nguyên của phương trình
e1 + e2 + e3 + e4 + e5 = r
với e1, e2 chẵn, 0 ≤ e1, e2 ≤ 10, và 3 ≤ e3, e4, e5 ≤ 5.
Để tìm hàm sinh ta xây dựng một tích của các nhân tử đa thức sao cho
sau khi nhân các đa thức đó lại với nhau, ta được tất cả các hạng tử có
dạng xe1xe2xe3xe4xe5 . Ta được nhân tử đa thức tương ứng với e1 và e2 là
(1 + x2 + x4 + x6 + x8 + x10), và tương ứng với e3, e4, và e5 là
(x3 + x4 + x5). Hàm sinh cần tìm là
(1 + x2 + x4 + x6 + x8 + x10)2(x3 + x4 + x5)3
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 53 / 99
Hàm sinh Định nghĩa hàm sinh
Định nghĩa hàm sinh
Ví dụ
Tìm hàm sinh của {ar}r≥0, với ar là số cách chia r đồng xu vào 5 hộp với
điều kiện: Số đồng xu ở hộp 1 và hộp 2 là số chẵn và không quá 10, và
các hộp còn lại chứa 3 đến 5 đồng xu.
Giải. ar là số nghiệm nguyên của phương trình
e1 + e2 + e3 + e4 + e5 = r
với e1, e2 chẵn, 0 ≤ e1, e2 ≤ 10, và 3 ≤ e3, e4, e5 ≤ 5.
Để tìm hàm sinh ta xây dựng một tích của các nhân tử đa thức sao cho
sau khi nhân các đa thức đó lại với nhau, ta được tất cả các hạng tử có
dạng xe1xe2xe3xe4xe5 . Ta được nhân tử đa thức tương ứng với e1 và e2 là
(1 + x2 + x4 + x6 + x8 + x10), và tương ứng với e3, e4, và e5 là
(x3 + x4 + x5). Hàm sinh cần tìm là
(1 + x2 + x4 + x6 + x8 + x10)2(x3 + x4 + x5)3
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 53 / 99
Hàm sinh Hệ số hàm sinh
Hệ số hàm sinh
Trong phần này, chúng ta sẽ sử dụng một số kỷ thuật để tính toán các hệ
số trong hàm sinh. Phương pháp chủ yếu là đưa một hàm sinh phức tạp
về hàm sinh kiểu nhị thức hoặc tích của các hàm sinh kiểu nhị thức. Ta
cần sử dụng một số khai triển sau:
Một số khai triển đa thức
(1) 1− x
m+1
1− x = 1 + x + x
2 + x3 + · · ·+ xm
(2) 11− x = 1 + x + x
2 + · · ·
(3) (1 + x)n = 1+
(
n
1
)
x+
(
n
2
)
x2 + · · ·+
(
n
r
)
xr + · · ·+
(
n
n
)
xn
(4) (1− xm)n = 1−
(
n
1
)
xm +
(
n
2
)
x2m + · · ·+ (−1)k
(
n
k
)
xkm +
· · ·+ (−1)n
(
n
n
)
xnm
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 54 / 99
Hàm sinh Hệ số hàm sinh
Hệ số hàm sinh
Một số khai triển đa thức
(5) 1
(1− x)n =
1 +
(
1 + n− 1
1
)
x +
(
2 + n− 1
2
)
x2 + · · ·+
(
r + n− 1
r
)
xr + · · ·
(6) Nếu h(x) = f(x)g(x), với f(x) = a0 + a1x + a2x2 + · · · và
g(x) = b0 + b1x + b2x2 + · · · , thì h(x) = a0b0 + (a1b0 + a0b1)x + (a2b0 +
a1b1 + a0b2)x2 + · · ·+ (arb0 + ar−1b1 + ar−2b2 + · · ·+ a0br)xr + · · ·
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 55 / 99
Hàm sinh Hệ số hàm sinh
Hệ số hàm sinh
Ví dụ
Tìm hệ số của x16 trong (x2 + x3 + x4 + · · · )5?
Giải. Ta có
(x2 + x3 + x4 + · · · )5 = [x2(1 + x + x2 + · · · )]5
= x10(1 + x + x2 + · · · )5
= x10 1
(1− x)5
Để tìm hệ số của x16 trong (x2 + x3 + x4 + · · · )5, ta tìm hệ số của x6 trong
1
(1−x)5 . Theo khai triển trên ta được hệ số của x
6 trong 1
(1−x)5 là(
6 + 5− 1
6
)
.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 56 / 99
Hàm sinh Hệ số hàm sinh
Hệ số hàm sinh
Ví dụ
Tìm số cách để lấy 15 đồng xu từ 20 người sao cho, trong 19 người đầu
tiên ta có thể lấy ở mỗi người 0 đồng hoặc 1 đồng, và người thứ 20 ta có
thể lấy 0 đồng, hoặc 1 đồng, hoặc 5 đồng?
Giải. Bài toán trên tương đương với bài toán tìm nghiệm nguyên của
phương trình
x1 + x2 + · · ·+ x20 = 15
thỏa điều kiện xi = 0 hoặc 1 với i = 1, 2, . . . , 19 và x20 = 0 hoặc 1, hoặc 5.
Ta có được hàm sinh cho bài toán trên là
(1 + x)19(1 + x + x5)
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 57 / 99
Hàm sinh Hệ số hàm sinh
Hệ số hàm sinh
Ví dụ
Tìm số cách để lấy 15 đồng xu từ 20 người sao cho, trong 19 người đầu
tiên ta có thể lấy ở mỗi người 0 đồng hoặc 1 đồng, và người thứ 20 ta có
thể lấy 0 đồng, hoặc 1 đồng, hoặc 5 đồng?
Giải. Bài toán trên tương đương với bài toán tìm nghiệm nguyên của
phương trình
x1 + x2 + · · ·+ x20 = 15
thỏa điều kiện xi = 0 hoặc 1 với i = 1, 2, . . . , 19 và x20 = 0 hoặc 1, hoặc 5.
Ta có được hàm sinh cho bài toán trên là
(1 + x)19(1 + x + x5)
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 57 / 99
Hàm sinh Hệ số hàm sinh
Hệ số hàm sinh
Theo công thức khai triển ta có
(1 + x)19 = 1 +
(
19
1
)
x +
(
19
2
)
x2 + · · ·+ · · ·+
(
19
19
)
x19
Đặt f(x) = (1 + x)19 và g(x) = 1 + x + x5. Gọi ar là hệ số của xr trong f(x),
và br là hệ số của xr trong g(x). Ta thấy ar =
(
19
r
)
, và
b0 = b1 = b5 = 1, các bi khác bằng 0. Hệ số của x15 trong h(x) = f(x)g(x)
được tính bởi (6) là,
a15b0 + a14b1 + a13b2 + · · ·+ a0b15
Thu gọn ta được
a15b0+a14b1+a10b5 =
(
19
15
)
×1+
(
19
14
)
×1+
(
19
10
)
×1 = 107882.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 58 / 99
Hàm sinh Hệ số hàm sinh
Hệ số hàm sinh
Ví dụ
Có bao nhiêu cách chia 25 viên bi vào 7 hộp với điều kiện hộp thứ nhất có
không quá 10 viên, các hộp còn lại tùy ý.
Giải. Hàm sinh của dãy {ar}r≥0 với ar là số cách chia r viên bi vào 7 hộp
với điều kiện như đề bài là:
(1 + x + . . .+ x10)(1 + x + x2 + . . .+)6
=
(
1− x11
1− x
)(
1
1− x
)6
= (1− x11)
(
1
1− x
)7
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 59 / 99
Hàm sinh Hệ số hàm sinh
Hệ số hàm sinh
Ví dụ
Có bao nhiêu cách chia 25 viên bi vào 7 hộp với điều kiện hộp thứ nhất có
không quá 10 viên, các hộp còn lại tùy ý.
Giải. Hàm sinh của dãy {ar}r≥0 với ar là số cách chia r viên bi vào 7 hộp
với điều kiện như đề bài là:
(1 + x + . . .+ x10)(1 + x + x2 + . . .+)6
=
(
1− x11
1− x
)(
1
1− x
)6
= (1− x11)
(
1
1− x
)7
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 59 / 99
Hàm sinh Hệ số hàm sinh
Hệ số hàm sinh
Theo công thức (5) ta có(
1
1− x
)7
= 1 +
(
1 + 7− 1
1
)
x + · · ·+
(
r + 7− 1
r
)
xr + · · ·
Đặt f(x) = 1− x11 và g(x) =
(
1
1− x
)7
. Gọi ar là hệ số của xr trong f(x),
và br là hệ số của xr trong g(x). Ta thấy a0 = 1, a11 = −1, ai = 0 với
i 6= 0, 11 và br =
(
r + 7− 1
r
)
.
Hệ số của x25 trong h(x) = f(x)g(x) được tính bởi (6) là,
a0b25 + a1b24 + · · ·+ a25b0
Thu gọn ta được
a0b25 + a11b14 = 1×
(
25 + 7− 1
25
)
+ (−1)×
(
14 + 7− 1
14
)
= 697521
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 60 / 99
Hàm sinh Hệ số hàm sinh
Hệ số hàm sinh
Ví dụ
Có bao nhiêu cách chọn 25 nón từ 6 loại nón, với điều kiện mỗi loại nón
phải được chọn từ 1 đến 5 cái.
Ví dụ
Cho n là số nguyên dương. Chứng minh rằng:(
n
0
)2
+
(
n
1
)2
+ · · ·+
(
n
n
)2
=
(
2n
n
)
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 61 / 99
Hàm sinh Hệ số hàm sinh
Hệ số hàm sinh
Giải. Ta có
(
2n
n
)
là hệ số của xn trong (1 + x)2n = (1 + x)n(1 + x)n.
Đặt f(x) = (1 + x)n, g(x) = (1 + x)n và ar, br lần lượt là hệ số của xr trong
f(x) và g(x). Ta có ar = br =
(
n
r
)
. Áp dụng công thức (6), ta có hệ số
xn trong f(x)g(x) là
a0bn + a1bn−1 + · · ·+ anb0
=
(
n
0
)(
n
n
)
+
(
n
1
)(
n
n− 1
)
+ · · ·+
(
n
n
)(
n
0
)
=
(
n
0
)2
+
(
n
1
)2
+ · · ·+
(
n
n
)2
.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 62 / 99
Hàm sinh Phân hoạch
Phân hoạch
Định nghĩa
Cho số nguyên dương n. Khi đó dãy (a1, a2, . . . , ak) được gọi là một phân
hoạch của n nếu 1 ≤ a1 ≤ a2 ≤ · · · ≤ ak ≤ n và a1 + a2 + · · ·+ ak = n.
Ví dụ
Số nguyên dương 5 có 7 phân hoạch là (1, 1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 3),
(1, 2, 2), (1, 4), (2, 3), và (5), trong đó 5 được gọi là một phân hoạch tầm
thường của chính nó.
Ví dụ
Liệt kê tất cả các phân hoạch của 6.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 63 / 99
Hàm sinh Phân hoạch
Phân hoạch
Chúng ta xây dựng một hàm sinh cho ar, với ar là số lượng các phân
hoạch của số nguyên r.
Một phân hoạch của số nguyên r được mô tả bằng số lượng các số 1,
2,...sao cho khi lấy tổng lại với nhau ta được r.
Gọi ek là số các số nguyên k xuất hiện trong phân hoạch, ta có
1e1 + 2e2 + 3e3 + · · ·+ kek + · · ·+ rer = r
Ta được hàm sinh cần tìm là
g(x) = (1 + x + x2 + · · ·+ xn + · · · )× (1 + x2 + x4 + · · ·+ x2n + · · · )×
· · · × (1 + xk + x2k + · · ·+ xkn + · · · )
Dễ dàng thấy được g(x) = 1
(1− x)(1− x2)(1− x3) . . . (1− xk) . . .
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 64 / 99
Hàm sinh Phân hoạch
Phân hoạch
Ví dụ
Tìm hàm sinh cho ar, với ar là số cách biểu diễn r như tổng của các số
nguyên khác nhau.
Tương tự như trên ta cũng gọi ek là số các số nguyên k xuất hiện trong
phân hoạch của r, ta có
1e1 + 2e2 + 3e3 + · · ·+ kek + · · ·+ rer = r
Do yêu cầu của bài toán các ei chỉ nhận giá trị là 0 hoặc 1. Ta được hàm
sinh của ar là
g(x) = (1 + x)(1 + x2)(1 + x3) . . .
Ví dụ
Tìm hàm sinh cho ar, với ar là số cách chọn các đồng xu 1 đồng, 2 đồng,
5 đồng để được tổng là r đồng.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 65 / 99
Hàm sinh Phân hoạch
Phân hoạch
Ví dụ
Chứng minh rằng mọi số nguyên dương đều được viết như là tổng duy
nhất của các lũy thừa khác nhau của 2.
Gọi ar là số cách để viết một số nguyên r thành tổng của các lũy thừa
khác nhau của 2. Ta tìm hàm sinh cho ar. Tương tự như hàm sinh cho
tổng các số nguyên khác nhau trong ví dụ trên, nhưng trong trường hợp
này ta chỉ xét các số nguyên là lũy thừa của 2. Gọi ek là số các số nguyên
2k trong phân hoạch, thì ta có
1e0 + 2e1 + 22e2 + · · ·+ 2kek + · · · = r
Hàm sinh của ar là
g(x) = (1 + x)(1 + x2)(1 + x4)(1 + x8) . . . (1 + x2k) . . .
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 66 / 99
Hàm sinh Phân hoạch
Phân hoạch
Để chứng minh mọi số nguyên đều được viết dưới dạng tổng duy nhất của
các lũy thừa khác nhau của 2, ta phải chứng minh hệ số của mỗi lũy thừa
của x trong g(x) bằng 1. Nghĩa là chứng minh
g(x) = 1 + x + x2 + x3 + · · · = 11− x
Ta thấy
(1− x)g(x) = (1− x)(1 + x)(1 + x2)(1 + x4) . . . (1 + x2k) . . .
= (1− x2)(1 + x2)(1 + x4) . . . (1 + x2k) . . .
= (1− x4)(1 + x4) . . . (1 + x2k) . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
= 1
Do đó g(x) = 1 + x + x2 + x3 + · · · . Vậy ta được điều cần chứng minh.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 67 / 99
Hàm sinh Hàm sinh mũ
Hàm sinh mũ
Trong phần này chúng ta sẽ nói về hàm sinh mũ và sử dụng chúng để giải
quyết các bài toán liên quan đến sự sắp xếp có lặp lại.
Ví dụ
Tìm số các từ khác nhau có 4 ký tự được tạo thành từ các chữ a, b, c, và
mỗi từ chứa ít nhất hai chữ a?
Từ tập hợp các ký tự sau đây ta có thể sắp xếp để được các từ cần tìm:
{a, a, a, a}, {a, a, a, b}, {a, a, a, c}, {a, a, b, b}, {a, a, b, c}, {a, a, c, c}. Dễ
dàng thấy rằng số từ có thể có được là
4!
4!0!0! +
4!
3!1!0! +
4!
3!0!1! +
4!
2!2!0! +
4!
2!1!1! +
4!
2!0!2!
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 68 / 99
Hàm sinh Hàm sinh mũ
Hàm sinh mũ
Gọi e1, e2, e3 là số chữ a, b, c xuất hiện trong một từ. Thoạt nhìn, bài toán
của chúng ta sẽ tương đương với bài toán tìm số nghiệm nguyên của
phương trình
e1 + e2 + e3 = 4
với e1 ≥ 2 , e2, e3 ≥ 0, và chúng ta có thể dùng hàm sinh thông thường
để giải. Sự khác biệt ở đây nằm ở chỗ ứng với mỗi nghiệm nguyên của
phương trình trên ta được số lượng các chữ cái mỗi loại, và ứng với số
lượng các chữ cái đó ta có thể sắp xếp để cho ra nhiều từ khác nhau.
Nghĩa là ứng với một nghiệm nguyên của phương trình trên cho ta 4!e1!e2!e3!
từ có thể. Trong trường hợp này người ta đưa ra khái niệm hàm sinh mũ.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 69 / 99
Hàm sinh Hàm sinh mũ
Hàm sinh mũ
Định nghĩa
Cho {ar}r≥0 là một dãy các số thực. Khi đó chuỗi lũy thừa hình thức
E(x) = a0 + a1x + a2
x2
2! + a3
x3
3! + · · ·+ ar
xr
r! + · · ·
được gọi là hàm sinh mũ của dãy {ar}r≥0.
Chúng ta xây dựng hàm sinh mũ giống như cách xây dựng hàm sinh
thông thường: một nhân tử đa thức cho mỗi đối tượng, mỗi nhân tử chứa
tập hợp các lũy thừa của x. Tuy nhiên mỗi lũy thừa xr được chia cho r!.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 70 / 99
Hàm sinh Hàm sinh mũ
Hàm sinh mũ
Ví dụ
Tìm hàm sinh mũ cho ar, số các bộ gồm k phần tử không lặp lại có sắp
thứ tự từ n phần tử?, (ar là chỉnh hợp chập r của n phần tử. )
Do không có sự lặp lại, nên hàm sinh mũ cần tìm là (1+ x)n. Hệ số của xr
là
(
n
r
)
. Hệ số của xrr! là ar = n!/(n− r)!
Hay nói cách khác, ta có ar =
n!
(n− r)! , do đó hàm sinh mũ là
E(x) = 1 + nx + n!
(n− 2)!
x2
2! +
n!
(n− 3)!
x3
3! + · · ·+
n!
(n− r)!
xr
r! + · · · .
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 71 / 99
Hàm sinh Hàm sinh mũ
Hàm sinh mũ
Ví dụ
Tìm hàm sinh mũ cho ar, với ar là số cách sắp xếp khác nhau của r vật
thể được chọn ra từ 4 loại vật thể khác nhau, sao cho mỗi loại vật thể
xuất hiện ít nhất 2 lần và không quá 5 lần?
Gọi ei là số lượng loại vật thể thứ i, i = 1, 2, 3, 4, xuất hiện trong số r vật
thể cần sắp xếp. Ta có e1 + e2 + e3 + e4 = r và 2 ≤ ei ≤ 5, với
i = 1, 2, 3, 4. Nhân tử đa thức ứng với mỗi loại vật thể là
x2
2! +
x3
3! +
x4
4! +
x5
5!
. Từ đó suy ra hàm sinh cần tìm là(
x2
2! +
x3
3! +
x4
4! +
x5
5!
)4
.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 72 / 99
Hàm sinh Hàm sinh mũ
Hàm sinh mũ
Ví dụ
Tìm hàm sinh mũ cho số cách xếp r người vào trong 3 căn phòng với ít
nhất một người mỗi phòng?
Dễ dàng thấy hàm sinh mũ cần tìm là(
x + x
2
2! +
x3
3! +
x4
4! + · · ·
)3
.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 73 / 99
Hàm sinh Hàm sinh mũ
Một số khai triển cơ bản của hàm sinh mũ
Ta có
ex = 1 + x + x
2
2! +
x3
3! + · · ·+
xr
r! + · · ·
Thay x bởi nx ta được
enx = 1 + nx + n
2x2
2! +
n3x3
3! + · · ·+
nrxr
r! + · · · .
Ta cũng suy ra được là
x2
2! +
x3
3! +
x4
4! + · · · = e
x − 1− x
Một số khai triển hữu ích thường gặp
1
2(e
x + e−x) = 1 + x
2
2! +
x4
4! +
x6
6! + . . .
1
2(e
x − e−x) = x + x
3
3! +
x5
5! +
x7
7! + · · ·
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 74 / 99
Hàm sinh Hàm sinh mũ
Hàm sinh mũ
Ta xem một số ứng dụng:
Ví dụ
Tìm số cách sắp xếp r đối tượng được chọn ra từ n loại đối tượng khác
nhau?
Ta dễ dàng thấy hàm sinh của nó là(
1 + x + x
2
2! +
x3
3! + · · ·
)n
= (ex)n = enx
Theo công thức khai triển trên ta dễ dàng thấy được hệ số của xrr! trong
hàm sinh trên là nr (công thức chỉnh hợp lặp).
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 75 / 99
Hàm sinh Hàm sinh mũ
Hàm sinh mũ
Ví dụ
Tìm số cách để chia 25 người vào trong 3 căn phòng với ít nhất một
người mỗi phòng?
Ta dễ dàng thấy được hàm sinh mũ là
(
x + x22! +
x3
3! + · · ·
)3
= (ex − 1)3 để
tìm hệ số của xr/r! ta khai triển biểu thức của ex,
(ex − 1)3 = e3x − 3e2x + 3ex − 1
Thay vào ta được
e3x − 3e2x + 3ex − 1 =
∞∑
r=0
3r x
r
r! − 3
∞∑
r=0
2r x
r
r! + 3
∞∑
r=0
xr
r! − 1
Suy ra hệ số của x25/25! là 325 − (3× 225) + 3.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 76 / 99
Hàm sinh Phương pháp tổng
Phương pháp tổng
Trong phần này ta chỉ ra cách xây dựng hàm sinh thông thường h(x) mà
hệ số của xr phụ thuộc vào r.
Ta có một số quy luật sau đây để xây dựng hàm sinh mới từ các hàm sinh
đã có sẵn. Giả sử A(x) =
∑
anxn, B(x) =
∑
bnxn, C(x) =
∑
cnxn.
Nếu bn = dan, thì B(x) = dA(x) với mọi hằng số d.
Nếu cn = an + bn, thì C(x) = A(x) + B(x).
Nếu cn =
∑n
i=0 aibn−i, thì C(x) = A(x)B(x).
Nếu bn = an−k, ngoại trừ bi = 0 với i < k, thì B(x) = xkA(x).
Nếu g(x) = a0 + a1x+ a2x2 + a3x3 + · · ·+ arxr + · · · , lấy đạo hàm của g(x)
ta được ddxg(x) = a1 + 2a2x + 3a3x
2 + · · ·+ rarxr−1 + · · · .
Nhân hai vế cho x ta được
x
[
d
dxg(x)
]
= a1x + 2a2x2 + 3a3x3 + · · ·+ rarxr + · · ·
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 77 / 99
Hàm sinh Phương pháp tổng
Phương pháp tổng
Ví dụ
Xây dựng hàm sinh h(x) với hệ số ar = 2r2.
Từ 11−x = 1 + x + x
2 + x3 + · · · , ta được
x
(
d
dx
1
1−x
)
= x
(
1
(1−x)2
)
= 1x + 2x2 + 3x3 + · · ·+ rxr + · · ·
Ta lặp lại quá trình trên với x
(1−x)2 ta được
x
(
d
dx
x
(1−x)2
)
= x(1+x)
(1−x)3 = 1
2x + 22x2 + 32x3 + · · ·+ r2xr + · · · Cuối cùng
nhân 2 vào hai vế của phương trình trên ta được
h(x) = 2x(1+x)
(1−x)3 = (2× 12)x + (2× 22)x2 + · · ·+ (2× r2)xr + · · · .
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 78 / 99
Hàm sinh Phương pháp tổng
Phương pháp tổng
Ví dụ
Xây dựng hàm sinh h(x) với hệ số ar = (r + 1)r(r− 1).
Ta có
3! 1
(1− x)4 = 3!
(
1 +
(
1 + 4− 1
1
)
x +
(
2 + 4− 1
r
)
x2 + · · ·
)
Hệ số ar của khai triển trên là
ar = 3!
(
r + 4− 1
r
)
= 3! (r + 3)!r!3! = (r + 3)(r + 2)(r + 1)
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 79 / 99
Hàm sinh Phương pháp tổng
Phương pháp tổng
Khi đó khai triển lũy thừa của 3! 1
(1−x)4 là:
3!
(1− x)4 = (3× 2× 1) + (4× 3× 2)x + · · ·+ (r + 3)(r + 2)(r + 1)x
r + · · ·
Nhân hai vế cho x2 ta được
3!x2
(1− x)4 = (3× 2× 1)x
2 + (4× 3× 2)x3 + · · ·+ (r + 1)r(r− 1)xr + · · ·
Vậy hàm sinh cần tìm là h(x) = 3!x2
(1−x)4 .
Tổng quát, ta thấy (n− 1)!(1− x)−n có hệ số ar là
ar = (n− 1)!C(r + n− 1, r) = [r + (n− 1)][r + (n− 2)] · · · (n + 1)
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 80 / 99
Hàm sinh Phương pháp tổng
Phương pháp tổng
Định lý
Nếu h(x) là hàm sinh với ar là hệ số của xr, thì h∗(x) = h(x)/(1− x) là
hàm sinh của tổng các ar, nghĩa là
h∗(x) = a0 + (a0 + a1)x + (a0 + a1 + a2)x2 + · · ·+
( r∑
i=0
ai
)
xr + · · · .
Ví dụ
Tính tổng 2× 12 + 2× 22 + 2× 32 + · · ·+ 2n2.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 81 / 99
Hàm sinh Phương pháp tổng
Phương pháp tổng
Hàm sinh h(x) cho ar = 2r2 là
2x(1 + x)/(1− x)3
Theo định lý trên, tổng cần tìm a1 + a2 + · · ·+ an là hệ số của xn trong
h∗(x) = h(x)/(1− x) = 2x(1 + x)/(1− x)4 = 2x(1− x)−4 + 2x2(1− x)−4
Hệ số của xn trong 2x(1− x)−4 là hệ số của xn−1 trong 2(1− x)−4, và hệ
số của xn trong 2x2(1− x)−4 là hệ số của xn−2 trong 2(1− x)−4.
Do đó tổng cần tìm bằng
2
(
(n− 1) + 4− 1
(n− 1)
)
+ 2
(
(n− 2) + 4− 1
(n− 2)
)
= 2
(
n + 2
3
)
+ 2
(
n + 1
3
)
.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 82 / 99
Hàm sinh Phương pháp tổng
Phương pháp tổng
Ví dụ
Tính tổng 3× 2× 1 + 4× 3× 2 + · · ·+ (n + 1)n(n− 1).
Hàm sinh h(x) cho ar = (r + 1)r(r− 1) là:
h(x) = 6x2(1− x)−4.
Bởi định lý trên, tổng cần tìm là hệ số của xn trong
h∗(x) = h(x)/(1− x) = 6x2(1− x)−5. Hệ số của xn trong h∗(x) bằng với
hệ số của xn−2 trong 6(1− x)−5, và bằng
6C((n− 2) + 5− 1,n− 2) = 6C(n + 2, 4).
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 83 / 99
Hàm sinh Bài toán đệ quy
Ứng dụng hàm sinh thông thường trong bài toán đệ quy
Trong phần này, chúng ta sẽ trình bày một ứng dụng quan trọng của hàm
sinh trong việc giải bài toán đệ quy, ta gọi G(x) là hàm sinh của dãy
{an}n≥0 và tiến hành các bước sau:
(1) Chuyển công thức đệ quy thành một phương trình của G(x), thường
được thực hiện bằng cách nhân cả hai vế của phương trình đệ quy
cho xn, hay xn+1, hay xn+k với một k nào đó, và lấy tổng trên tất cả
các số nguyên không âm n.
(2) Giải phương trình để tìm G(x).
(3) Tìm hệ số của xn trong G(x), hệ số đó chính bằng an, và ta được một
công thức tường minh cho an.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 84 / 99
Hàm sinh Bài toán đệ quy
Ứng dụng hàm sinh thông thường trong bài toán đệ quy
Ví dụ
Một người gửi 1000 đô la vào trong một tài khoản tiết kiệm với lãi suất là
5 phần trăm một năm. Bắt đầu mỗi năm, người đó lại chuyển vào tài
khoản đó 500 đô la nữa. Hỏi số tiền trong tài khoản tiết kiệm của người
đó sau n năm là bao nhiêu?
Gọi an là số dư trong tài khoản tiết kiệm sau n năm. Ta thấy a0 = 1000,
an+1 = 1.05an + 500. Gọi G(x) =
∑
n≥0 anxn là hàm sinh của dãy
{an}n≥0. Bây giờ ta giải bài toán theo các bước như trên:
(1) Nhân cả hai vế của hệ thức đệ quy với xn+1 và lấy tổng trên tất cả các
số nguyên không âm n, ta được∑
n≥0
an+1xn+1 =
∑
n≥0
1.05anxn+1 +
∑
n≥0
500xn+1
Phương trình trên tương đương với: G(x)− a0 = 1.05xG(x) + 500x1−x
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 85 / 99
Hàm sinh Bài toán đệ quy
Ứng dụng hàm sinh thông thường trong bài toán đệ quy
(2)Do đó ta được
G(x) = 10001− 1.05x +
500x
(1− x)(1− 1.05x)
(3)Ta thấy
1000
1− 1.05x = 1000 ·
∑
n≥0
1.05nxn
do đó hệ số của xn trong biểu thức trên là 1000 · 1.05n.
Xét thành phần thứ hai 500x(1−x)(1−1.05x) = 500x.
(∑
n≥0 xn
)(∑
n≥0 1.05nxn
)
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 86 / 99
Hàm sinh Bài toán đệ quy
Ứng dụng hàm sinh thông thường trong bài toán đệ quy
Trong tích trên xn−1 được tạo thành từ xi của tổng thứ nhất và
1.05n−1−ixn−1−i từ tổng thứ hai với 0 ≤ i ≤ n− 1. Do đó hệ số của xn
trong 500x(1−x)(1−1.05x) là
500
n−1∑
i=0
1.05i = 5001.05
n − 1
1.05− 1 = 10000 · (1.05
n − 1)
Ta được hệ số
an = 1000 · 1.05n + 10000 · (1.05n − 1) = 1.05n.11000− 10000.
Thử lại ta được kết quả đúng.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 87 / 99
Hàm sinh Bài toán đệ quy
Ứng dụng hàm sinh thông thường trong bài toán đệ quy
Ví dụ
Cho hệ thức đệ quy an+1 = 4an − 100, và a0 = 50. Tìm công thức cho an.
Đáp án: an = 50 · 4n − 100 · 4n−13 .
Ví dụ
Cho hệ thức đệ quy an+2 = 3an+1 − 2an, và a0 = 0, a1 = 1. Tìm công
thức cho an.
Đáp án: an = 2n − 1.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 88 / 99
Hàm sinh Bài toán đệ quy
Định lý (Công thức tích cho hàm sinh thông thường)
Gọi an là số cách để xây dựng một cấu trúc nào đó trên tập n phần tử, và
bn là số cách để xây dựng một cấu trúc khác trên tập n phần tử. Gọi cn
là số cách để chia [n] thành các đoạn S = {1, 2, · · · , i} và
T = {i + 1, i + 2, · · · ,n}, (S và T có thể bằng rỗng), và xây dựng cấu trúc
loại thứ nhất lên S, và cấu trúc loại thứ hai lên T. Gọi A(x), B(x), và C(x)
là các hàm sinh tương ứng của các dãy {an}, {bn}, và {cn}. Thì
A(x)B(x) = C(x).
Ví dụ
Một học kỳ ở một trường đại học có n ngày. Đầu mỗi học kỳ, cô hiệu
trưởng chia học kỳ đó ra làm 2 phần, k ngày đầu tiên sẽ dùng cho lý
thuyết, và n− k ngày còn lại sẽ được dùng cho thực hành (ở đây
1 ≤ k ≤ n− 2). Trong đợt dạy lý thuyết sẽ có 1 ngày nghỉ, và trong đợt
dạy thực hành sẽ có 2 ngày nghỉ. Hỏi cô hiệu trưởng có bao nhiêu cách
khác nhau để làm như vậy?
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 89 / 99
Hàm sinh Bài toán đệ quy
Ứng dụng hàm sinh thông thường trong bài toán đệ quy
Nếu đợt dạy lý thuyết có k ngày thì ta sẽ có k cách để chọn ra một ngày
nghỉ, và nếu đợt dạy thực hành có n− k ngày thì có
(
n− k
2
)
cách để
chọn ra 2 ngày nghỉ. Các hàm sinh tương ứng là A(x) =
∑
k≥1 kxk, và
B(x) =
∑
m≥2
(
m
2
)
xm. Ta có
∑
i≥0 xi = 11−x .
Lấy đạo hàm ta được A(x) = x
(1−x)2 và B(x) =
x2
(1−x)3 Gọi fn là số cách để
chia học kỳ ra hai phần và chọn ngày nghỉ, và gọi F(x) là hàm sinh của
nó. Khi đó ta có A(x)B(x) = F(x). Do đó
F(x) = x
3
(1− x)5 = x
3
∑
n≥0
(
n + 4
4
)
xn =
∑
n≥3
(
n + 1
4
)
xn
Từ đó suy ra fn =
(
n + 1
4
)
.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 90 / 99
Hàm sinh Bài toán đệ quy
Ứng dụng hàm sinh thông thường trong bài toán đệ quy
Ví dụ
Tương tự như ví dụ trên nhưng ở đây thay vì chọn ngày nghỉ, hiệu trưởng
chọn ra một số ngày tự học trong cả hai phần của học kỳ. Hỏi có bao
nhiêu cách khác nhau để hiệu trưởng làm như vậy?
Gọi gn là số cách mà hiệu trưởng có thể chọn. Chia bài toán ra thành 2
phần. Gọi C(x) là hàm sinh cho số cách để chọn ra một tập các ngày tự
học trong phần thứ nhất của học kỳ. Bởi vì một tập k phần tử sẽ có 2k tập
con, ta có C(x) =
∑
k≥0 2kxk = 11−2x . Ta thấy phần thứ hai cũng có hàm
sinh giống như phần thứ nhất. Do đó hàm sinh cần tìm là
F(x) = C(x)C(x) = 1
(1−2x)2 =
∑
n≥0
(
n + 2− 1
n
)
(2x)n =∑
n≥0
(
n + 1
1
)
(2x)n =
∑
n≥0(n + 1)2nxn. Vậy ta được gn = (n + 1)2n.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 91 / 99
Hàm sinh Bài toán đệ quy
Ứng dụng hàm sinh thông thường trong bài toán đệ quy
Ví dụ
Tìm số cách để chia n ngày của một học kỳ ra thành ba phần. Trong đó, ở
phần thứ nhất số ngày nghỉ được chọn tùy ý, ở phần thứ hai số ngày nghỉ
là số lẻ, và ở phần thứ ba số ngày nghỉ là số chẵn.
Đáp án: gn = 2n−3n(n + 3).
Ví dụ
Gọi p≤k(n) là số các phân hoạch của số nguyên n thành những phần có
nhỏ hơn hay bằng k, chứng minh rằng
∞∑
n≥0
p≤k(n)xn =
k∏
i=1
1
1− xi
= (1+ x+ x2 + x3 + · · · )(1+ x2 + x4 + x6 + · · · ) · · · (1+ xk + x2k + x3k + · · · ).
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 92 / 99
Hàm sinh Bài toán đệ quy
Ứng dụng hàm sinh mũ trong bài toán đệ quy
Tương tự như hàm sinh thông thường, gọi G(x) là hàm sinh mũ cho dãy
{an}, ta thực hiện theo một số bước như sau:
(1) Chuyển hệ thức đệ quy thành một phương trình trong G(x), thường
được thực hiện bằng cách nhân cả hai vế của phương trình đệ quy
cho xn/n!, hay xn+1/(n + 1)!, hay xn+k/(n + k)! với một k nào đó, và
lấy tổng trên tất cả các số nguyên không âm n.
(2) Giải G(x).
(3) Tìm hệ số của xn/n! trong G(x), hệ số đó chính bằng an, và ta được
một công thức tường minh cho an.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 93 / 99
Hàm sinh Bài toán đệ quy
Ứng dụng hàm sinh mũ trong bài toán đệ quy
Ví dụ
Cho a0 = 1, và an+1 = (n + 1)(an − n + 1), nếu n ≥ 0. Tìm một công
thức cho an.
Chú ý
Nếu chúng ta giải bài toán trên bằng cách dùng hàm sinh thông thường,
thì sẽ gặp vấn đề lúc đưa ra kết quả. Dãy {an} tăng khá nhanh, và
chúng ta không tìm được dạng hàm sinh thông thường tương ứng. Do đó
bài toán trên sẽ được giải bằng hàm sinh mũ.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 94 / 99
Hàm sinh Bài toán đệ quy
Ứng dụng hàm sinh mũ trong bài toán đệ quy
Gọi A(x) =
∑
n≥0 an x
n
n! là hàm sinh mũ của dãy {an}n≥0. Ta nhân cả hai
vế của hệ thức đệ quy với xn+1(n+1)! , và lấy tổng với mọi n ≥ 0, ta được∑
n≥0
an+1
xn+1
(n + 1)! =
∑
n≥0
an
xn+1
n! −
∑
n≥0
(n− 1)x
n+1
n!
Ta thấy vế trái là A(x)− 1, hạng tử đầu tiên của vế phải là xA(x). Từ đó ta
được phương trình trên tương đương với
A(x)− 1 = xA(x)− x2ex + xex.
A(x) = 11− x + xe
x =
∑
n≥0
xn +
∑
n≥0
xn+1
n!
Hệ số của xn/n! trong
∑
n≥0 xn là n!, trong khi hệ số của xn/n! trong∑
n≥0
xn+1
n! là n. Vậy hệ số của x
n/n! trong A(x) là n! + n.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 95 / 99
Hàm sinh Bài toán đệ quy
Ứng dụng hàm sinh mũ trong bài toán đệ quy
Ví dụ
Cho f0 = 0, và fn+1 = 2(n+ 1)fn + (n+ 1)! nếu n ≥ 0. Tìm một công thức
cho fn.
Gọi F(x) =
∑
n≥0 fn x
n
n! là hàm sinh mũ của dãy {fn}. Nhân cả hai vế của
hệ thức trên với xn+1/(n + 1)!, và lấy tổng với mọi n ≥ 0. Ta được∑
n≥0 fn+1 x
n+1
(n+1)! = 2x
∑
n≥0 fn x
n
n! +
∑
n≥0 xn+1
Do f0 = 0 nên vế trái bằng F(x), hạng tử thứ nhất của vế phải bằng
2xF(x), và hạng tử thứ hai của vế phải bằng x/(1− x). Do đó, ta có được
F(x) = 2xF(x) + x1−x , hay F(x) =
x
(1−x)(1−2x) Suy ra,
F(x) =
∑
n≥0
(2n − 1)xn
Ta được hệ số của xn/n! trong F(x) là fn = (2n − 1)n!
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 96 / 99
Hàm sinh Bài toán đệ quy
Ứng dụng hàm sinh mũ trong bài toán đệ quy
Ví dụ
Cho f0 = 0, và fn+1 = 2(n+ 1)fn + (n+ 1)! nếu n ≥ 0. Tìm một công thức
cho fn.
Gọi F(x) =
∑
n≥0 fn x
n
n! là hàm sinh mũ của dãy {fn}. Nhân cả hai vế của
hệ thức trên với xn+1/(n + 1)!, và lấy tổng với mọi n ≥ 0. Ta được∑
n≥0 fn+1 x
n+1
(n+1)! = 2x
∑
n≥0 fn x
n
n! +
∑
n≥0 xn+1
Do f0 = 0 nên vế trái bằng F(x), hạng tử thứ nhất của vế phải bằng
2xF(x), và hạng tử thứ hai của vế phải bằng x/(1− x). Do đó, ta có được
F(x) = 2xF(x) + x1−x , hay F(x) =
x
(1−x)(1−2x) Suy ra,
F(x) =
∑
n≥0
(2n − 1)xn
Ta được hệ số của xn/n! trong F(x) là fn = (2n − 1)n!
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 96 / 99
Hàm sinh Bài toán đệ quy
Ứng dụng hàm sinh mũ trong bài toán đệ quy
Bổ đề
Gọi {ai} và {bk} là hai dãy, và gọi A(x) =
∑
i≥0 ai x
i
i! , và B(x) =
∑
k≥0 bk x
k
k!
là các hàm sinh của nó. Gọi cn =
∑n
i=0
(
n
i
)
aibn−i, và C(x) là hàm
sinh của dãy {cn}. Thì
A(x)B(x) = C(x)
Hay nói cách khác, hệ số của xn/n! trong A(x)B(x) là
cn =
∑n
i=0
(
n
i
)
aibn−i.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 97 / 99
Hàm sinh Bài toán đệ quy
Ứng dụng hàm sinh mũ trong bài toán đệ quy
Định lý (Công thức tích cho hàm sinh mũ)
Gọi an là số cách để xây dựng một cấu trúc nào đó trên một tập hợp n
phần tử, và bn là số cách để xây dựng một cấu trúc khác trên tập n phần
tử. Gọi cn là số cách để chia đoạn [n] thành những tập con rời nhau S và
T, (S ∪ T = [n]), và xây dựng một cấu trúc trên S, và một cấu trúc thứ
hai lên T. Gọi A(x), B(x), và C(x) là các hàm sinh mũ tương ứng của các
dãy {an}, {bn}, và {cn}, thì
A(x)B(x) = C(x).
Ví dụ
Một đội bóng có n cầu thủ. Huấn luyện viên chia đội bóng ra thành hai
nhóm, và mỗi nhóm đứng thành một dòng. Các thành viên của nhóm thứ
nhất mặt áo cam, áo trắng, hoặc áo xanh. Các thành viên của nhóm còn
lại mặc áo đỏ. Hỏi có bao nhiêu cách để thực hiện các việc trên?
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 98 / 99
Hàm sinh Bài toán đệ quy
Ứng dụng hàm sinh mũ trong bài toán đệ quy
Giả sử huấn luyện viên chọn ra k người để tạo thành nhóm thứ nhất. Gọi
ak là số cách để k người này có thể chọn áo cam, trắng, hoặc xanh, và
đứng thành một dòng. Thì ak = k!3k, hàm sinh mũ của dãy {ak} là
A(x) =
∑
k≥0 k!3k x
k
k! =
1
1−3x .
Tương tự, giả sử có m người trong nhóm thứ hai. Gọi bm là số cách để m
người này đứng thành một dòng, bm = m!, và hàm sinh mũ của dãy bm là
B(x) =
∑
m≥0 m! x
m
m! =
1
1−x .
Gọi cn là số cách để thực hiện tất cả những việc trên, và C(x) là hàm sinh
mũ tương ứng của nó. Theo công thức trên ta có
C(x) = A(x)B(x) = 11−3x · 11−x . Do 11−3x =
∑
k≥0 3kxk, và 11−x =
∑
m≥0 xm,
ta có hệ số của xn/n! trong C(x) là cn = n!(3n+1 − 1)/2.
Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 99 / 99
Các file đính kèm theo tài liệu này:
- nhap_mon_ly_thuyet_to_hoptohopc2_0723_2012633.pdf