Chương 3 – Bài toán đếm
3.1. Giới thiệu bài toán
3.2. Nguyên lý bù trừ
3.3. Hệ thức truy hồi
3.4. Hàm sinh và bài toán đếm
3.5. Bài tập
Định nghĩa hàm sinh
•Định nghĩa: Hàm sinh g(x) của dãy số {hn | n =
0,1,2,…} là đa thức
•Ví dụ 1:
–g1(x) là hàm sinh của dãy tổ hợp hk = C(m,k)
–g2(x) là hàm sinh của dãy hk = 1
2
0 1 2
0
( ) ...
i
i
i
g x h h x h x h x
=
= + + + =
( )
1
0
2
2
( ) 1
1
( ) 1 ...
1
m
mk k
m
k
g x x C x
g x x x
x
=
= + =
= = + + +
−
Định nghĩa hàm sinh
•Ví dụ 2: Xét hàm sau:
g(x) là hàm sinh của dãy hn (hệ số của số
hạng xn )
hn là số nghiệm nguyên không âm của
phương trình:
( )
2
1 1
( ) 1 ...
(1 ) 1
kk
k
g x x x
x x
� �
= = = + + +
� �
− −
� �
1 2
...
k
n
n k
t t t n
h R
+ + + =
=�
( )
( )
( )
( )
( )
2 3
0
2 2 3 3
0
2 3 1 2
1
2
1 2 1
11 ...
1
11 ...
1
1 ... ...
1
11 ...
1
11 ....
1
....
1
kn n
k
k
n
kn n n
k
k
n
k
k k k k
k
k
k k
k
k k
k
x x x R x
x
rx r x r x R r x
rx
xx x x x x x x
x
xx x
x
x x
x
xx x x
x
=
=
+ +
+
+ +
= + + + + =
−
= + + + + =
−
= + + + + = + + +
−
−= + + +
−
= + + +
−
= + + +
−
Hàm sinh và bài toán đếm
•Ví dụ 3: Phương trình: x1 + x2 + x3 + x4 = 29
có bao nhiêu nghiệm nguyên không âm thỏa
mãn: x1 <3, x2 <8
•Lời giải:
–hn là số nghiệm nguyên không âm của phương
trình
x1 + x2 + x3 + x4 = n thỏa mãn: x1 <3, x2 <8
–hn có hàm sinh:
Cần tìm h29
( ) ( ) ( )
2
2 2 7 2
( ) 1 1 ... 1 ...g x x x x x x x x= + + + + + + + + +