›
›

Giáo trình Toán rời rạc - Bài 15: Kỹ thuật hàm sinh - Trần Vĩnh Đức

Download
Kỹ thuật Hàm sinh  
Trần Vĩnh Đức  
HUST  
Ngày 24 tháng 7 năm 2018  
1 / 26  
Nội dung  
Tính các hệ số của hàm sinh  
Dãy Fibonacci  
Đị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.  
3 / 26  
Bài tập  
Tìm hệ số của xn trong hàm sinh  
1
.
(1 − x)c  
4 / 26  
Lời giải  
Ta có  
1
= (1 + x + x2 + · · · )c.  
(1 − x)c  
Hệ số của xn trong hàm sinh trên chính là số nghiệm nguyên  
không âm của phương trình  
e1 + e2 + · · · + ec = n.  
5 / 26  
Lời giải (tiếp)  
Xét song ánh giữa các nghiệm của phương trình  
e1 + e2 + · · · + ec = n  
với  
”các dãy nhị phân gồm n số 1 và c − 1 số 0”  
như sau:  
e1 + e2 + · · · + ec = n  
⇔
11 · · · 1 0 11 · · · 1 0 · · · 0 11 · · · 1  
| {z } | {z }  
| {z }  
e1  
e2  
ec  
6 / 26  
Lời giải (tiếp)  
Theo luật BOOKEEPER thì  
”số dãy nhị phân gồm n số 1 và c − 1 số 0”  
bằng  
(
)
n + c − 1  
(n + c − 1)!  
n!(c − 1)!  
=
.
n
7 / 26  
Dãy hệ số tổ hợp  
Vậy ta có  
⟨
(
) (  
) (  
)
⟩
c + 1  
2
c + 2  
3
c + 3  
4
1
1, c,  
,
,
, · · ·  
←→  
.
(1 − x)c  
8 / 26  
Bài tập  
Tìm hệ số của xn trong hàm sinh  
(x2 + x3 + x4 + · · · )5.  
Hệ số này chính là số cách chọn n chiếc kẹo từ 5 loại kẹo, mỗi loại  
lấy ít nhất hai chiếc.  
9 / 26  
Bài tập  
Tìm hệ số của xn trong hàm sinh  
(1 + x)c.  
10 / 26  
Bài tập  
▶
▶
▶
Ta cần $15 để đóng góp cứu trợ đồng bào vùng bão lụt.  
Có 20 sinh viên tham gia đóng góp.  
Biết rằng 19 người đầu tiên sẽ góp $1 hoặc không, người  
thứ 20 sẽ góp $1 hoặc $5 (hoặc không góp).  
▶
Hãy dùng hàm sinh để tính số cách quyên góp $15.  
11 / 26  
Bài tập  
Hãy tính số cách để lấy 25 quả bóng giống nhau từ 7 chiếc hộp  
biết rằng hộp đầu tiên có không nhiều hơn 10 quả, còn các hộp  
khác có số quả tuỳ ý.  
12 / 26  
Bài tập  
Có bao nhiêu cách chọn n quả với các rằng buộc sau?  
▶
▶
▶
▶
Số táo phải chẵn.  
Số chuối phải chia hết cho 5.  
Có nhiều nhất bốn quả cam.  
Có nhiều nhất một quả đào.  
13 / 26  
Ví dụ  
Chứng minh đẳng thức sau dùng hàm sinh.  
( )  
( )  
( )  
(
)
2
2
2
n
n
n
n
2n  
n
+
+ · · · +  
=
.
0
1
14 / 26  
Chứng minh.  
Hệ số của xn trong hàm sinh F(x) = (1 + x)2n là  
(
)
2n  
n
.
Đặt G(x) = H(x) = (1 + x)n. Vậy hệ số xr trong G(x) = H(x) là  
( )  
(
)
n
r
n
n − r  
=
.
Theo luật tích, hệ số xn trong hàm sinh G(x)H(x) = F(x) là  
( )( ) ( )(  
)
( )( )  
n
n
n
n
n
n
n
n
+
+
+ · · · +  
0
1
n − 1  
0
( )  
n
( )  
( )  
2
2
2
n
n
1
=
+
· · ·  
+
0
n
15 / 26  
Nội dung  
Tính các hệ số của hàm sinh  
Dãy Fibonacci  
Dãy Fibonacci  
Dãy Fibonacci  
⟨0, 1, 1, 2, 3, 5, 8, 13, · · · ⟩  
được định nghĩa bởi  
f0 = 0  
f1 = 1  
fn = fn−1 + fn−2  
(với n ≥ 2).  
17 / 26  
Bài tập  
Hãy tìm hàm sinh F(x) cho dãy Fibonacci.  
⟨0, 1, f1 + f0, f2 + f1, f3 + f2, · · · ⟩  
18 / 26  
Lời giải  
⟨
⟨
0,  
0,  
0,  
1,  
f0,  
0,  
0,  
f1,  
f0,  
0,  
f2,  
f1,  
0, · · · ⟩  
f3, · · · ⟩  
f2, · · · ⟩  
←→  
x
←→ xF(x)  
2
+
⟨
⟨
←→ x F(x)  
0, 1 + f0, f1 + f0, f2 + f1, f3 + f2, · · · ⟩  
Vậy ta có  
F(x) = x + xF(x) + x2F(x)  
x
=
.
2
1 − x − x  
19 / 26  
Bài tập  
Hãy viết ra công thức tường minh cho dãy sinh bởi hàm sinh  
x
F(x) :=  
.
2
1 − x − x  
20 / 26  
Tải về để xem bản đầy đủ
pdf 26 trang Thùy Anh 26/04/2022 5900
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 15: Kỹ thuật 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_15_ky_thuat_ham_sinh_tran_vinh_d.pdf