Bài giảng Toán rời rạc: Kỹ thuật Hàm sinh - Trần Vĩnh Đức

Bài giảng Toán rời rạc: Kỹ thuật Hàm sinh cung cấp cho người học những nội dung kiến thức như: Tính các hệ số của hàm sinh, dãy Fibonacci, phân thức đơn giản. Mời các bạn cùng tham khảo để biết thêm nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Kỹ thuật Hàm sinh - Trần Vĩnh Đức Kỹ thuật Hàm sinh Trần Vĩnh Đức HUST Ngày 24 tháng 7 năm 2018CuuDuongThanCong.com https://fb.com/tailieudientucntt 1 / 26 Nội dung Tính các hệ số của hàm sinh Dãy FibonacciCuuDuongThanCong.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)cCuuDuongThanCong.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 ecCuuDuongThanCong.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)cCuuDuongThanCong.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 nCuuDuongThanCong.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à ( ) ...