›
›

Giáo trình Toán rời rạc - Bài 14: Hàm sinh - Trần Vĩnh Đức

Download
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 đủ
pdf 51 trang Thùy Anh 12320 Free
Download
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:

  • pdfgiao_trinh_toan_roi_rac_bai_14_ham_sinh_tran_vinh_duc.pdf