Giáo trình Toán rời rạc - Bài 14: 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
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).
6
▶
Vậy mọi số hạng có số mũ 6 ứng với số lần x xuất hiện.
Hệ số của x chính là số cách chọn 6 quả.
6
▶
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ó
2
3
G(x)
=
=
=
1 + x + x + x + · · · + xn + · · ·
2
3
−xG(x)
1 − x − x − x − · · · − 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
Tải về để xem bản đầy đủ
51 trang
26/04/2022
3980
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Toán rời rạc - Bài 14: Hàm sinh - Trần Vĩnh Đức", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_toan_roi_rac_bai_14_ham_sinh_tran_vinh_duc.pdf
