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 =
i
2
=
+
+
= (cid:0)
0,1,2,…} là đa thức g x ( )
...
h x i
h 0
+ h x h x 1
2
=
i
0
m
m
k
=
+
=
(
)
(cid:0)
x
1
k C x m
g x ( ) 1
=
k
0
• Ví dụ 1:
1
2
=
= + +
+
x
x
1
...
g x ( ) 2
(cid:0)
x
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
-
Định nghĩa hàm sinh
• Ví dụ 2: Xét hàm sau:
k
2
=
=
=
+
(
)
+ + x
x
g x ( )
1
...
k
1 x
)
(1
k 1 � � � � -� � x 1
g(x) là hàm sinh của dãy hn (hệ số của số
hạng xn )
+
+
=
n
t
k
2
+ ... hn là số nghiệm nguyên không âm của n R k
t t 1 =� h n
phương trình:
-
k
(cid:0)
n
2
3
1 + + = =
)
(
n R x k
k
(cid:0) + + x x x 1 ...
=
)
(
n
0
- x 1
k
(cid:0)
n
2
3
1 + + + + = =
)
(
2 r x
3 r x
n n R r x k
k
(cid:0) rx 1 ...
=
)
(
n
0
k
+
- rx 1
k
k
k
k
2
3
+ 1
2
x = + + = + + +
)
(
x + + x x x x x x 1 ... ...
k
+ 1
-
k
- x x 1 1 = + + + x x 1 ...
k
k
2
- x
k
+ + x x = + 1 ....
k
k
+ 1
2
+ 1
- 1
k
+ + = + x x x ....
- 1 1 x x x 1
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
2
2
7
2
=
+
+
) (
) 2
x1 + x2 + x3 + x4 = n thỏa mãn: x1 <3, x2 <8 + + + x
+ + x
+ + x
x
x
x
x
g x ( )
...
1
1
...
) ( ( 1 – hn có hàm sinh:
Cần tìm h29
Hàm sinh và bài toán đếm • Ví dụ 4: 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 <4, x2 chia hết cho 4
• Lời giải:
– hn là số nghiệm nguyên không âm của phương
trình
2
8
3
2
+
=
+
+
+
+
) 2
) (
(
+ + x
+ + x
x
x
x
x
) ( ... 1
...
1
1
x1 + x2 + x3 + x4 = n thỏa mãn: x1 <4, x2 chia hết 4 x g x ( ) cho 4
– hn có hàm sinh:
Cần tìm h29
Hàm sinh và bài toán đếm • Ví dụ 5: Có bao nhiêu cách chọn ra n quả từ 4 loại quả: táo, chuối, cam, đào (mỗi loại đều có số lượng ít nhất là n) mà trong đó có số chẵn quả táo, số chuối chia hết cho 5, không quá 4 quả cam và không quá 1 quả đào?
• Lời giải:
– Gọi hn là số cách chọn thỏa mãn yêu cầu đề bài.
2
10
4
6
5
2
3
4
+
=
+
+
+
+
+
+
+
+
+
)
(
) (
x
x
x
x
x
x
x
1
1
5
2
1
2
=
+
=
=
+
) ( + + – Khi đó hàm sinh của dãy hn có dạng: x x g x .... 1 ( ) (
)
) ( ... 1 (
x )
+ + x
x
x
1
1
...
2
2
5
-
(
)
1 x
1 x
x x
1
1 1
1
x
1
+
(
) 1 !
=
=
=
- - - -
= + n
1
h n
n C + - n
n R 2
2 1
n n
!1!
(cid:0)
Hàm sinh và công thức truy hồi
• Ví dụ 6: Giải công thức truy hồi:
=
a
a
4
n
=
2 =
a
0;
1
0
n a 1
•
Lời giải:
– Gọi g(x) là hàm sinh của dãy số thỏa mãn hệ thức
2
3
=
+
+
+
a
g x ( )
...
0
+ a x a x 1
2
a x 3
truy hồi
2
3
+
+
+
=
+
4
4
...
a x 0
a x 1
– Ta có:
a 0 = + x
a x 1 24
x g x ( )
1
1
n
=
-
=
=
(
)
2
g x ( )
na
2
(cid:0) - - (cid:0) -
� n 2 �
� �
x
x
x
x 1 4
4 1 2
4 + 1 2
1 4
- -
Hàm sinh và công thức truy hồi
• Ví dụ 5: Giải công thức truy hồi:
a0=1 , a1= 2 và an = 3an-1 - 2an-2 + 2
•
Lời giải:
2
3
– Gọi g(x) là hàm sinh của dãy số thỏa mãn hệ thức +
=
a
g x ( )
...
0
2
a x 3
3
+ )
+ a x a x 1 ( + 2
+ )
a
x
x
g x ( )
2
2
a 3
2
...
0
a 3 1
+ 0
2
+ a 2 1
3
+
+ 2
+ 3
- -
+ 2 x a ...) 2 (
...)
+ 0
a x a x 1
2
a x 3
0
+ + 2 a x a x 1
2
+ a x 3
2
+
x a 3 ( +
truy hồi ( + + = a x a 1 – Ta có: + = + x x 3 1 2 + + x
x
2 x 2 (1
...)
2
x
2
- -
xg x
= - + x 1
3
( ) 2
+ x g x ( )
-
x
2 1
2
2
-
x
3
=
+
=
=
g x ( )
?
2
na
2
(
) (
)
+ x 1 2 ) 2
(
(
)
x
1 + x 1 3
x 2
x
x
1
x 2 + x 1 3
2
x
x
1
1 2
- - (cid:0) (cid:0) - - - - -
Bài tập
Sử dụng hàm sinh để giải các bài toán sau:
Bài 1: BPT: x1 + x2 + x3 + x4 + x5 +x6 ≤n có bao nhiêu nghiệm nguyên không âm thỏa mãn:
•
x3 ≤ 3 và x4 chia hết cho 4 dư 2.
•
x2 < 2 và x5 lẻ
Bài 2: Giải hệ thức truy hồi:
=
=
=
n
3;
4;
5
6
n 7 (
2)
a n
a n
a n
a 0
a 1
1
+ 2
- (cid:0) - -
Bài tập
BPT: x1 + x2 + x3 + x4 + x5 +x6 ≤n có bao nhiêu nghiệm nguyên không âm thỏa mãn:
•
x3 ≤ 3 và x4 chia hết cho 4 dư 2.
•
x2 < 2 và x5 lẻ
