Bài giảng Kỹ thuật Hàm sinh - Toán rời rạc thầy Trần Vĩnh Đức | Trường Đại học Bách khoa Hà Nội

Nhờ vào hàm sinh, chúng ta có thể áp dụng cỗ máy này vào các bài toán dãy số. Bằng cách này, chúng ta có thể sử dụng hàm sinh trong việc giải tất cả các dạng toán về phép đếm. Tài liệu được sưu tầm, giúp bạn ôn tập và đạt kết quả cao. Mời bạn đọc đón xem!

Kỹ thuật Hàm sinh
Trần Vĩnh Đức
HUST
Ngày 24 tháng 7 năm 2018
1 / 26
Nội dung
Tính các hệ số của hàm sinh
y Fibonacci
Định nghĩa
Ta hiệu [x
n
]G(x) hệ số của x
n
trong hàm sinh
G(x) = g
0
+ g
1
x + g
2
x
2
+ ··· .
nghĩa rằng [x
n
]G(x) = g
n
.
3 / 26
Bài tập
Tìm hệ số của x
n
trong hàm sinh
1
(1 x)
c
.
4 / 26
Lời giải
Ta
1
(1 x)
c
= (1 + x + x
2
+ ···)
c
.
Hệ số của x
n
trong hàm sinh trên chính số nghiệm nguyên
không âm của phương trình
e
1
+ e
2
+ ··· + e
c
= n.
5 / 26
Lời giải (tiếp)
Xét song ánh giữa các nghiệm của phương trình
e
1
+ e
2
+ ··· + e
c
= n
với
”các y nhị phân gồm n số 1 c 1 số 0
như sau:
e
1
+ e
2
+ ··· + e
c
= n 11 ···1
| {z }
e
1
0 11 ···1
| {z }
e
2
0 ···0 11 ···1
| {z }
e
c
6 / 26
Lời giải (tiếp)
Theo luật BOOKEEPER thì
”số y nhị phân gồm n số 1 c 1 số 0
bằng
(
n + c 1
n
)
=
(n + c 1)!
n!(c 1)!
.
7 / 26
y hệ số tổ hợp
Vy ta
1, c,
(
c + 1
2
)
,
(
c + 2
3
)
,
(
c + 3
4
)
, ···
1
(1 x)
c
.
8 / 26
Bài tập
Tìm hệ số của x
n
trong hàm sinh
(x
2
+ x
3
+ x
4
+ ···)
5
.
Hệ số y chính số cách chọn n chiếc kẹo từ 5 loại kẹo, mỗi loại
lấy ít nhất hai chiếc.
9 / 26
Bài tập
Tìm hệ số của x
n
trong hàm sinh
(1 + x)
c
.
10 / 26
Bài tập
Ta cần $15 để đóng góp cứu trợ đồng bào vùng bão lụt.
20 sinh viên tham gia đóng góp.
Biết rằng 19 người đầu tiên sẽ góp $1 hoặc không, người
thứ 20 sẽ góp $1 hoặc $5 (hoặc không góp).
y dùng hàm sinh để tính số cách quyên góp $15.
11 / 26
Bài tập
y tính số cách để lấy 25 quả bóng giống nhau từ 7 chiếc hộp
biết rằng hộp đầu tiên không nhiều hơn 10 quả, còn các hộp
khác số quả tuỳ ý.
12 / 26
Bài tập
bao nhiêu cách chọn n quả với các rằng buộc sau?
Số táo phải chẵn.
Số chuối phải chia hết cho 5.
nhiều nhất bốn quả cam.
nhiều nhất một quả đào.
13 / 26
dụ
Chứng minh đẳng thức sau dùng hàm sinh.
(
n
0
)
2
+
(
n
1
)
2
+ ··· +
(
n
n
)
2
=
(
2n
n
)
.
14 / 26
Chứng minh.
Hệ số của x
n
trong hàm sinh F(x) = (1 + x)
2n
(
2n
n
)
.
Đặt G(x) = H(x) = (1 + x)
n
. Vy hệ số x
r
trong G(x) = H(x)
(
n
r
)
=
(
n
n r
)
.
Theo luật tích, hệ số x
n
trong hàm sinh G(x)H(x) = F(x)
(
n
0
)(
n
n
)
+
(
n
1
)(
n
n 1
)
+ ··· +
(
n
n
)(
n
0
)
=
(
n
0
)
2
+
(
n
1
)
2
+ ··· +
(
n
n
)
2
15 / 26
Nội dung
Tính các hệ số của hàm sinh
y Fibonacci
y Fibonacci
y Fibonacci
0, 1, 1, 2, 3, 5, 8, 13, ···
được định nghĩa bởi
f
0
= 0
f
1
= 1
f
n
= f
n1
+ f
n2
(với n 2).
17 / 26
Bài tập
y tìm hàm sinh F(x) cho dãy Fibonacci.
0, 1, f
1
+ f
0
, f
2
+ f
1
, f
3
+ f
2
, ···
18 / 26
Lời giải
0, 1, 0, 0, 0, ··· x
0, f
0
, f
1
, f
2
, f
3
, ··· xF(x)
+ 0, 0, f
0
, f
1
, f
2
, ··· x
2
F(x)
0, 1 + f
0
, f
1
+ f
0
, f
2
+ f
1
, f
3
+ f
2
, ···
Vy ta
F(x) = x + xF(x) + x
2
F(x)
=
x
1 x x
2
.
19 / 26
Bài tập
y viết ra công thức tường minh cho dãy sinh bởi hàm sinh
F(x) :=
x
1 x x
2
.
20 / 26
| 1/26

Preview text:

Kỹ thuật Hàm sinh Trần Vĩnh Đức HUST Ngày 24 tháng 7 năm 2018 1 / 26 Nội dung
Tính các hệ số của hàm sinh Dãy Fibonacci Định nghĩa
Ta ký hiệu [xn]G(x) là hệ số của xn trong hàm sinh
G(x) = g0 + g1x + g2x2 + · · · .
Có nghĩa rằng [xn]G(x) = gn. 3 / 26 Bài tập
Tìm hệ số của xn trong hàm sinh 1 . (1 − x)c 4 / 26 Lời giải Ta có 1
= (1 + x + x2 + · · · )c. (1 − x)c
Hệ số của xn trong hàm sinh trên chính là số nghiệm nguyên
không âm của phương trình
e1 + e2 + · · · + ec = n. 5 / 26 Lời giải (tiếp)
Xét song ánh giữa các nghiệm của phương trình
e1 + e2 + · · · + ec = n với
”các dãy nhị phân gồm n số 1 và c − 1 số 0” như sau:
e1 + e2 + · · · + ec = n
11 · · · 1 | {z } 0 11 · · · 1
| {z } 0 · · · 0 11 · · · 1 | {z } e1 e2 ec 6 / 26 Lời giải (tiếp) Theo luật BOOKEEPER thì
”số dãy nhị phân gồm n số 1 và c − 1 số 0” bằng ( ) n + c − 1 (n + c − 1)! = . n n!(c − 1)! 7 / 26 Dãy hệ số tổ hợp Vậy ta có ⟨ ( ) ( ) ( ) ⟩ c + 1 c + 2 c + 3 1, c, , , , · · · ←→ 1 . 2 3 4 (1 − x)c 8 / 26 Bài tập
Tìm hệ số của xn trong hàm sinh
(x2 + x3 + x4 + · · · )5.
Hệ số này chính là số cách chọn n chiếc kẹo từ 5 loại kẹo, mỗi loại lấy ít nhất hai chiếc. 9 / 26 Bài tập
Tìm hệ số của xn trong hàm sinh (1 + x)c. 10 / 26 Bài tập
▶ Ta cần $15 để đóng góp cứu trợ đồng bào vùng bão lụt.
▶ Có 20 sinh viên tham gia đóng góp.
▶ Biết rằng 19 người đầu tiên sẽ góp $1 hoặc không, người
thứ 20 sẽ góp $1 hoặc $5 (hoặc không góp).
▶ Hãy dùng hàm sinh để tính số cách quyên góp $15. 11 / 26 Bài tập
Hãy tính số cách để lấy 25 quả bóng giống nhau từ 7 chiếc hộp
biết rằng hộp đầu tiên có không nhiều hơn 10 quả, còn các hộp khác có số quả tuỳ ý. 12 / 26 Bài tập
Có bao nhiêu cách chọn n quả với các rằng buộc sau? ▶ Số táo phải chẵn.
▶ Số chuối phải chia hết cho 5.
▶ Có nhiều nhất bốn quả cam.
▶ Có nhiều nhất một quả đào. 13 / 26 Ví dụ
Chứng minh đẳng thức sau dùng hàm sinh. ( ) ( ) ( ) ( ) n 2 n 2 n 2 2n + + · · · + = . 0 1 n n 14 / 26 Chứng minh.
Hệ số của xn trong hàm sinh F(x) = (1 + x)2n là ( ) 2n . n
Đặt G(x) = H(x) = (1 + x)n. Vậy hệ số xr trong G(x) = H(x) là ( ) ( ) n n = . r n − r
Theo luật tích, hệ số xn trong hàm sinh G(x)H(x) = F(x) là ( )( ) ( )( ) ( )( ) n n n n n n + + · · · + 0 n 1 n − 1 n 0 ( ) ( ) ( ) n 2 n 2 n 2 = + + · · · + 0 1 n 15 / 26 Nội dung
Tính các hệ số của hàm sinh Dãy Fibonacci Dãy Fibonacci Dãy Fibonacci
0, 1, 1, 2, 3, 5, 8, 13, · · · ⟩ được định nghĩa bởi f0 = 0 f1 = 1
fn = fn−1 + fn−2 (với n ≥ 2). 17 / 26 Bài tập
Hãy tìm hàm sinh F(x) cho dãy Fibonacci.
0, 1, f1 + f0, f2 + f1, f3 + f2, · · · ⟩ 18 / 26 Lời giải 0, 1, 0, 0, 0, · · · ⟩ ←→ x 0, f0, f1, f2, f3, · · · ⟩ ←→ xF(x) + 0, 0, f0, f1, f2, · · · ⟩
←→ x2F(x)
0, 1 + f0, f1 + f0, f2 + f1, f3 + f2, · · · ⟩ Vậy ta có
F(x) = x + xF(x) + x2F(x) x = . 1 − x − x2 19 / 26 Bài tập
Hãy viết ra công thức tường minh cho dãy sinh bởi hàm sinh x F(x) := . 1 − x − x2 20 / 26