Chương
3
Bài
toán
đếm
3.1.
Giới
thiệu
bài
toán
3.2.
Nguyên
trừ
3.3.
Hệ
thức
truy
hồi
3.4.
Hàm
sinh
bài
toán
đếm
3.5.
Bài
tập
g(x) = h + h
0 1
i
k
Định
Định nghĩa hàm sinh
nghĩa: Hàm sinh g(x) của dãy số
{hn
|
n
=
0,1,2,…} là đa thứcx
+h2x2
+...
=
h xi
i=0
dụ
1:
g1(x) = (1+ x)m = m Cmxk
k=0
g2(x) = 1 1x =1+ x + x2 +...
g1(x)
hàm
sinh
của
dãy
tổ
hợp
hk
=
C(m,k)
g2(x)
hàm
sinh
của
dãy
hk
=
1
k
=
� �
1
t + t +...+ t
1 2 k
n
= n
dụ
2:
Định nghĩa
Xét hàm sau:
hàm
sinh
g(x)
=
(1
1
x)k
=
1
x
(1+
x +
x2
+...)k
g(x)
hàm
sinh
của
dãy
hn
(hệ
số
của
số
hạng
xn
)
hn là số nghiệm nguyên
phương trình: hn = Rk
không
âm
của