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!
Môn: Toán rời rạc (BKHN)
Trường: Đại học Bách Khoa Hà Nội
Thông tin:
Tác giả:
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