Xem mẫu
- Kỹ thuật Hàm sinh
Trần Vĩnh Đức
HUST
Ngày 24 tháng 7 năm 2018
CuuDuongThanCong.com https://fb.com/tailieudientucntt 1 / 26
- Nội dung
Tính các hệ số của hàm sinh
Dãy Fibonacci
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Định nghĩa
Ta ký hiệu [xn ]G(x) là hệ số của xn trong hàm sinh
G(x) = g0 + g1 x + g2 x2 + · · · .
Có nghĩa rằng [xn ]G(x) = gn .
CuuDuongThanCong.com https://fb.com/tailieudientucntt 3 / 26
- Bài tập
Tìm hệ số của xn trong hàm sinh
1
.
(1 − x)c
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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} 0 11
| {z · · · 1} 0 · · · 0 11
| {z · · · 1}
| {z
e1 e2 ec
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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)!
CuuDuongThanCong.com https://fb.com/tailieudientucntt 7 / 26
- Dãy hệ số tổ hợp
Vậy ta có
⟨ ( ) ( ) ( ) ⟩
c+1 c+2 c+3 1
1, c, , , , ··· ←→ .
2 3 4 (1 − x)c
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 9 / 26
- Bài tập
Tìm hệ số của xn trong hàm sinh
(1 + x)c .
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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ỳ ý.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 13 / 26
- Ví dụ
Chứng minh đẳng thức sau dùng hàm sinh.
( )2 ( )2 ( )2 ( )
n n n 2n
+ + ··· + = .
0 1 n n
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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
( )2 ( )2 ( )2
n n n
= + + ··· +
0 1 n
CuuDuongThanCong.com https://fb.com/tailieudientucntt 15 / 26
- Nội dung
Tính các hệ số của hàm sinh
Dãy Fibonacci
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- 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).
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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 , · · · ⟩
CuuDuongThanCong.com https://fb.com/tailieudientucntt 18 / 26
- Lời giải
⟨ 0, 1, 0, 0, 0, · · · ⟩ ←→ x
⟨ 0, f0 , f1 , f2 , f3 , · · · ⟩ ←→ xF(x)
+ ⟨ 0, 0, f0 , f1 , f2 , · · · ⟩ ←→ x2 F(x)
⟨ 0, 1 + f0 , f1 + f0 , f2 + f1 , f3 + f2 , · · · ⟩
Vậy ta có
F(x) = x + xF(x) + x2 F(x)
x
= .
1 − x − x2
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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
CuuDuongThanCong.com https://fb.com/tailieudientucntt 20 / 26
nguon tai.lieu . vn
