Xem mẫu
- 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
nguon tai.lieu . vn
