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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:26

Thêm vào BST

Báo xấu

41
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 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