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

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

Thêm vào BST

Báo xấu

61
lượt xem 5
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: Hàm sinh cung cấp cho người học những nội dung kiến thức như: Đếm và đa thức, định nghĩa hàm sinh, các phép toán trên hàm sinh, một bài toán đếm. 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: Hàm sinh - Trần Vĩnh Đức

Hàm sinh Trần Vĩnh Đức HUST Ngày 26 tháng 4 năm 2016 CuuDuongThanCong.com https://fb.com/tailieudientucntt 1 / 51
Nội dung Đếm và đa thức Định nghĩa hàm sinh Các phép toán trên hàm sinh Một bài toán đếm CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ký hiệu hình thức ▶ Có 2 quả táo, 3 quả mận, và 4 quả đào. ▶ Ta ký hiệu T := “lấy một quả táo” M := “lấy một quả mận” D := “lấy một quả đào”. ▶ Lấy 1 quả táo, 2 quả mận, và 3 quả đào: TMMDDD = TM2 D3 . ▶ Lấy 1 quả táo, 1 quả mận, và 1 quả đào hoặc lấy 1 quả táo, 1 quả đào, và 2 quả mận”: TMD + TMD2 . CuuDuongThanCong.com https://fb.com/tailieudientucntt 3 / 51
Câu hỏi Xâu sau đây biểu diễn những lựa chọn gì? TMD + TMD2 + TM2 D + T2 MD + TM2 D2 + · · · + T2 M3 D4 = (T + T2 )(M + M2 + M3 )(D + D2 + D3 + D4 ). Lời giải Đây như một chuỗi hình thức mô tả mọi khả năng chọn trong số 2 quả táo, 3 quả mận, và 4 quả đào, mỗi loại ít nhất một quả. CuuDuongThanCong.com https://fb.com/tailieudientucntt 4 / 51
Bài tập Có bao nhiêu cách chọn 6 quả trong số 2 quả táo, 3 quả mận, và 4 quả đào, mỗi loại ít nhất một quả? Lời giải ▶ Ta chỉ cần thay thế mỗi T, M, D bằng biến hình thức x trong chuỗi (T + T2 )(M + M2 + M3 )(D + D2 + D3 + D4 ). ▶ Vậy mọi số hạng có số mũ 6 ứng với số lần x6 xuất hiện. ▶ Hệ số của x6 chính là số cách chọn 6 quả. CuuDuongThanCong.com https://fb.com/tailieudientucntt 5 / 51
Đa thức và đếm ▶ Khi thay thế T, M, D bằng x thì hệ số của xk chính là số cách chọn đúng k quả. ▶ Ta có (x + x2 )(x + x2 + x3 )(x + x2 + x3 + x4 ) = x3 (1 + x)(1 + x + x2 )(1 + x + x2 + x3 ) = x3 (1 + 2x + 2x2 + x3 )(1 + x + x2 + x3 ) = x3 + 3x4 + 5x5 + 6x6 + 5x7 + 3x8 + x9 . ▶ Vậy có 6 cách lựa chọn 6 quả, 5 cách chọn 7 quả . . . . CuuDuongThanCong.com https://fb.com/tailieudientucntt 6 / 51
Câu hỏi ▶ Giả sử một quả mận có 20 calo, một quả đào có 40 calo, và một quả táo có 60 calo. ▶ Nếu ta thay thế T → x60 , M → x40 D → x20 trong chuỗi hình thức (T + T2 )(M + M2 + M3 )(D + D2 + D3 + D4 ). thì hệ số của xn là gì? CuuDuongThanCong.com https://fb.com/tailieudientucntt 7 / 51
Lời giải ▶ Ta thay thế T → x60 , M → x40 D → x20 ▶ Vậy thì hệ số của xn của đa thức là số cách chọn quả để có n calo. ▶ Vì khi chọn Ti Mj Dk ta được 60i + 40j + 20k calo. CuuDuongThanCong.com https://fb.com/tailieudientucntt 8 / 51
Ví dụ ▶ Từ đa thức (x60 + x120 )(x40 + x80 + x120 )(x20 + x40 + x60 + x80 ) = x120 (1 + x20 + 2x40 + 3x60 + 3x80 + 4x100 + 3x120 + 3x140 + 2x160 + x180 + x200 ) = x120 + x140 + 2x160 + 3x180 + 3x200 + 4x220 + 3x240 + 3x260 + 2x280 + x300 + x320 ▶ Ta thấy có 3 cách chọn quả để có 200 calo. CuuDuongThanCong.com https://fb.com/tailieudientucntt 9 / 51
Bài tập ▶ Biết rằng quả táo giá 60 đồng, quả mận giá 40 đồng, và đào giá 20 đồng. ▶ Có bao nhiêu cách chọn các quả giá 200 đồng, có thể có loại quả không được chọn? CuuDuongThanCong.com https://fb.com/tailieudientucntt 10 / 51
Bài tập Hãy tìm đa thức có hệ số xk là số nghiệm nguyên không âm của phương trình x1 + x2 + x3 = k. CuuDuongThanCong.com https://fb.com/tailieudientucntt 11 / 51
Câu hỏi Ta có thể dùng kỹ thuật mô tả ở phần trước để lựa chọn các quả táo, đào và mận nhưng không hạn chế bao nhiêu quả cần lấy. T0 M0 D0 + TM0 D0 + · · · + TMD + TMD2 + · · · + Ti Mj Dk + · · · CuuDuongThanCong.com https://fb.com/tailieudientucntt 12 / 51
Tính toán hình thức ▶ Việc chọn không, một,. . . tới một số bất kỳ táo (mận, đào ) có thể biểu diễn một cách hình thức là T0 + T1 + T2 + · · · + Ti + · · · M0 + M1 + M2 + · · · + Mj + · · · D0 + D1 + D2 + · · · + Dk + · · · ▶ Việc chọn táo, đào, mận với số lượng tùy ý có thể viết dưới dạng tích ( 0 )( )( ) T + T1 + · · · M0 + M1 + · · · D0 + D1 + · · · . CuuDuongThanCong.com https://fb.com/tailieudientucntt 13 / 51
Ví dụ Nếu thay thế T, M, D bởi x thì hệ số của xn trong tích của ba chuỗi vô hạn sau chính là số cách chọn đúng n quả. (1 + x + x2 + · · · + xi + · · · )3 . CuuDuongThanCong.com https://fb.com/tailieudientucntt 14 / 51
Nội dung Đếm và đa thức Định nghĩa hàm sinh Các phép toán trên hàm sinh Một bài toán đếm CuuDuongThanCong.com https://fb.com/tailieudientucntt
Định nghĩa Hàm sinh của dãy số ⟨g0 , g1 , g2 , · · · ⟩ là chuỗi vô hạn G(x) = g0 + g1 x + g2 x2 + · · · . Ta sử dụng ký hiệu mũi tên hai phía để chỉ tương ứng giữa một dãy số và hàm sinh của nó như sau: ⟨g0 , g1 , g2 , · · · ⟩ ←→ g0 + g1 x + g2 x2 + · · · . CuuDuongThanCong.com https://fb.com/tailieudientucntt 16 / 51
Đị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 17 / 51
Ví dụ Dưới đây là một vài dãy số và hàm sinh của chúng: ⟨0, 0, 0, 0, · · · ⟩ ←→ 0 + 0x + 0x2 + 0x3 + · · · = 0 ⟨1, 0, 0, 0, · · · ⟩ ←→ 1 + 0x + 0x2 + 0x3 + · · · = 1 ⟨3, 2, 1, 0, · · · ⟩ ←→ 3 + 2x + 1x2 + 0x3 + · · · = 3 + 2x + x2 CuuDuongThanCong.com https://fb.com/tailieudientucntt 18 / 51
Ví dụ ▶ Hàm sinh cho dãy vô hạn ⟨1, 1, 1, · · · ⟩ là chuỗi hình học G(x) := 1 + x + x2 + x3 + · · · Ta có G(x) = 1 + x + x2 + x3 + · · · + xn + · · · −xG(x) = 1 − x − x2 − x3 − · · · − xn − · · · G(x) − xG(x) = 1 ▶ Vậy hàm sinh của dãy 1, 1, . . . là ∑ ∞ 1 = G(x) := xn . 1−x n=0 CuuDuongThanCong.com https://fb.com/tailieudientucntt 19 / 51
Bài tập Hãy tìm công thức đóng cho hàm sinh của các dãy sau: 1. ⟨ 0, 0, 0, 0, −6, 6, −6, 6, −6, 6, · · · ⟩ 2. ⟨1, 0, 1, 0, 1, 0, · · · ⟩ 3. ⟨1, 1, 0, 1, 1, 0, 1, 1, 0, · · · ⟩ CuuDuongThanCong.com https://fb.com/tailieudientucntt 20 / 51