Bài giảng Hàm sinh - Toán rời rạc thầy Trần Vĩnh Đức | Trường Đại học Bách khoa Hà Nội

Hàm sinh Trần Vĩnh Đức HUST Ngày 26 tháng 4 năm 2016 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 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 = TM2D3.
▶ 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. 3 / 51 Câu hỏi
Xâu sau đây biểu diễn những lựa chọn gì?
TMD + TMD2 + TM2D + T2MD + TM2D2 + · · · + T2M3D4
= (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ả. 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ả. 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ả . . . . 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ì? 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 TiMjDk ta được 60i + 40j + 20k calo. 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. 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? 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. 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.
T0M0D0 + TM0D0 + · · · + TMD + TMD2 + · · · + TiMjDk + · · · 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 ( ) ( ) ( )
T0 + T1 + · · ·
M0 + M1 + · · ·
D0 + D1 + · · · . 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. 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 Định nghĩa
Hàm sinh của dãy số ⟨g0, g1, g2, · · · ⟩ là chuỗi vô hạn
G(x) = g0 + g1x + g2x2 + · · · .
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 + g1x + g2x2 + · · · . 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 + g1x + g2x2 + · · · .
Có nghĩa rằng [xn]G(x) = gn. 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 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 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, · · · ⟩ 20 / 51