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. | Kỹ thuật Hàm sinh Trần Vĩnh Đức HUST Ngày 24 tháng 7 năm 2018 https tailieudientucntt 1 26 Nội dung Tính các hệ số của hàm sinh Dãy Fibonacci https 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 . https tailieudientucntt 3 26 Bài tập Tìm hệ số của xn trong hàm sinh 1 . 1 x c https 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. https 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 https 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 https 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 https 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. https tailieudientucntt 9 26 Bài tập Tìm hệ số của xn trong hàm sinh 1 x c . https 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. https 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ỳ ý. https tailieudientucntt 12 26 .
