Bài giảng Toán học tổ hợp và cấu trúc rời rạc - Chương 2: Phương pháp đém dùng hàm sinh

hườ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 Toán học tổ hợp và Cấu trúc rời rạc 2016 25 / 54
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 + x + 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 Toán học tổ hợp và Cấu trúc rời rạc 2016 26 / 54
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 Toán học tổ hợp và Cấu trúc rời rạc 2016 27 / 54
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 Toán học tổ hợp và Cấu trúc rời rạc 2016 28 / 54
Hàm sinh mũ
Một 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 Toán học tổ hợp và Cấu trúc rời rạc 2016 29 / 54
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 Toán học tổ hợp và Cấu trúc rời rạc 2016 30 / 54
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 Toán học tổ hợp và Cấu trúc rời rạc 2016 31 / 54
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 Toán học tổ hợp và Cấu trúc rời rạc 2016 32 / 54
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 Toán học tổ hợp và Cấu trúc rời rạc 2016 33 / 54
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− 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 Toán học tổ hợp và Cấu trúc rời rạc 2016 34 / 54
Phương pháp tổng
Phương pháp tổng
Khi đó khai triển lũy thừa của 3!(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 Toán học tổ hợp và Cấu trúc rời rạc 2016 35 / 54
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 Toán học tổ hợp và Cấu trúc rời rạc 2016 36 / 54
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 Toán học tổ hợp và Cấu trúc rời rạc 2016 37 / 54
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 Toán học tổ hợp và Cấu trúc rời rạc 2016 38 / 54
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 Toán học tổ hợp và Cấu trúc rời rạc 2016 39 / 54
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 Toán học tổ hợp và Cấu trúc rời rạc 2016 40 / 54
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 Toán học tổ hợp và Cấu trúc rời rạc 2016 41 / 54
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 Toán học tổ hợp và Cấu trúc rời rạc 2016 42 / 54
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 Toán học tổ hợp và Cấu trúc rời rạc 2016 43 / 54
Bài toán đệ quy
Định lý
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 Toán học tổ hợp và Cấu trúc rời rạc 2016 44 / 54
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 Toán học tổ hợp và Cấu trúc rời rạc 2016 45 / 54
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 Toán học tổ hợp và Cấu trúc rời rạc 2016 46 / 54
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 Toán học tổ hợp và Cấu trúc rời rạc 2016 47 / 54
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 Toán học tổ hợp và Cấu trúc rời rạc 2016 48 / 54
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 Toán học tổ hợp và Cấu trúc rời rạc 2016 49 / 54
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 Toán học tổ hợp và Cấu trúc rời rạc 2016 50 / 54
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 Toán học tổ hợp và Cấu trúc rời rạc 2016 51 / 54
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 Toán học tổ hợp và Cấu trúc rời rạc 2016 52 / 54
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 Toán học tổ hợp và Cấu trúc rời rạc 2016 53 / 54
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 Toán học tổ hợp và Cấu trúc rời rạc 2016 54 / 54