Kỹ thuật Hàm sinh
HUST
Trần Vĩnh Đức
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
1 / 26
Ngày 24 tháng 7 năm 2018
Nội dung
Tính các hệ số của hàm sinh
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
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 + (cid:1) (cid:1) (cid:1) :
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
3 / 26
Có nghĩa rằng [xn]G(x) = gn:
Bài tập Tìm hệ số của xn trong hàm sinh
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
4 / 26
1 (1 (cid:0) x)c :
Lời giải Ta có
1 (1 (cid:0) x)c = (1 + x + x2 + (cid:1) (cid:1) (cid:1) )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
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
5 / 26
e1 + e2 + (cid:1) (cid:1) (cid:1) + ec = n:
Lời giải (tiếp) Xét song ánh giữa các nghiệm của phương trình
e1 + e2 + (cid:1) (cid:1) (cid:1) + ec = n
với
”các dãy nhị phân gồm n số 1 và c (cid:0) 1 số 0”
như sau:
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
6 / 26
0 (cid:1) (cid:1) (cid:1) 0 11 (cid:1) (cid:1) (cid:1) 1 | {z } ec e1 + e2 + (cid:1) (cid:1) (cid:1) + ec = n , 11 (cid:1) (cid:1) (cid:1) 1 | {z } e1 0 11 (cid:1) (cid:1) (cid:1) 1 | {z } e2
Lời giải (tiếp) Theo luật BOOKEEPER thì
”số dãy nhị phân gồm n số 1 và c (cid:0) 1 số 0”
bằng ( )
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
7 / 26
= : n + c (cid:0) 1 n (n + c (cid:0) 1)! n!(c (cid:0) 1)!
Dãy hệ số tổ hợp
Vậy ta có ⟨ ( ) ( ) ( ) ⟩
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
8 / 26
! 1; c; ; ; ; (cid:1) (cid:1) (cid:1) c + 1 2 c + 2 3 c + 3 4 1 (1 (cid:0) x)c :
Bài tập Tìm hệ số của xn trong hàm sinh
(x2 + x3 + x4 + (cid:1) (cid:1) (cid:1) )5:
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
9 / 26
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.
Bài tập Tìm hệ số của xn trong hàm sinh
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
10 / 26
(1 + x)c:
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).
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
11 / 26
▶ Hãy dùng hàm sinh để tính số cách quyên góp $15.
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ỳ ý.
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
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?
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
13 / 26
▶ 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.
Ví dụ Chứng minh đẳng thức sau dùng hàm sinh.
2
2
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
14 / 26
( ) ( ( ) ( ) ) 2 + + (cid:1) (cid:1) (cid:1) + : = n 0 n 1 n n 2n n
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 (cid:0) r
( Theo luật tích, hệ số xn trong hàm sinh G(x)H(x) = F(x) là )( )( ) ) ( )( ( )
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
15 / 26
+ (cid:1) (cid:1) (cid:1) + + n n n 0 ( n 1 ( ( n n ) 2 n n (cid:0) 1 ) 2 n 0 ) 2 = + + (cid:1) (cid:1) (cid:1) + n 0 n 1 n n
Nội dung
Tính các hệ số của hàm sinh
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
Dãy Fibonacci
Dãy Fibonacci
Dãy Fibonacci
⟨0; 1; 1; 2; 3; 5; 8; 13; (cid:1) (cid:1) (cid:1) ⟩
được định nghĩa bởi
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
17 / 26
(với n (cid:21) 2): f0 = 0 f1 = 1 fn = fn(cid:0)1 + fn(cid:0)2
Bài tập Hãy tìm hàm sinh F(x) cho dãy Fibonacci.
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
18 / 26
⟨0; 1; f1 + f0; f2 + f1; f3 + f2; (cid:1) (cid:1) (cid:1) ⟩
Lời giải
x
! ! xF(x) ! x2F(x) ⟨ ⟨ + ⟨ ⟨ 0, 0; 0; 0; 1, f0; 0; 1 + f0; 0, f1; f0; f1 + f0; 0, f2; f1; f2 + f1; 0; (cid:1) (cid:1) (cid:1) ⟩ f3; (cid:1) (cid:1) (cid:1) ⟩ f2; (cid:1) (cid:1) (cid:1) ⟩ f3 + f2; (cid:1) (cid:1) (cid:1) ⟩
Vậy ta có
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
19 / 26
= F(x) = x + xF(x) + x2F(x) x 1 (cid:0) x (cid:0) x2 :
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
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
20 / 26
F(x) := x 1 (cid:0) x (cid:0) x2 :
Lời giải Đầu tiên, ta phân tích mẫu số
1 (cid:0) x (cid:0) x2 = (1 (cid:0) (cid:11)1x)(1 (cid:0) (cid:11)2x):
Ta được
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
21 / 26
p (1 + 5) (cid:11)1 = p (1 (cid:0) 5) (cid:11)2 = 1 2 1 2
Lời giải (tiếp) Sau đó, ta tìm A1; A2 thoả mãn
+ : x 1 (cid:0) x (cid:0) x2 = A1 1 (cid:0) (cid:11)1x A2 1 (cid:0) (cid:11)2x
bằng cách giải hệ phương trình tuyến tính. Ta được
= A1 =
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
22 / 26
A2 = 1 (cid:11)1 (cid:0) (cid:11)2 (cid:0)1 (cid:11)1 (cid:0) (cid:11)2 1p 5 = (cid:0) 1p 5
Lời giải (tiếp) Bây giờ ta đã có
) (
(cid:0) : x 1 (cid:0) x (cid:0) x2 = 1 1 (cid:0) (cid:11)1x 1 1 (cid:0) (cid:11)2x 1p 5
Theo công thức hàm sinh ta có
1x2 + (cid:11)3
1x3 + (cid:1) (cid:1) (cid:1)
= 1 + (cid:11)1x + (cid:11)2
2x2 + (cid:11)3
2x3 + (cid:1) (cid:1) (cid:1)
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
23 / 26
= 1 + (cid:11)2x + (cid:11)2 1 1 (cid:0) (cid:11)1x 1 1 (cid:0) (cid:11)2x
Lời giải (tiếp) Vậy thì
) (
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
24 / 26
(cid:0) F(x) = 1 1 (cid:0) (cid:11)1x ( = (1 + (cid:11)1x + (cid:11)2 ) 2x2 + (cid:1) (cid:1) (cid:1) ) 1 1 (cid:0) (cid:11)2x 1x2 + (cid:1) (cid:1) (cid:1) ) (cid:0) (1 + (cid:11)2x + (cid:11)2 1p 5 1p 5
Lời giải (tiếp) Cuối cùng ta được công thức lạ cho số Fibonacci thứ n:
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
25 / 26
(cid:11)n 1 fn = ( ) (cid:0) (cid:11)n 2p 5 (( p ) n ) n 5 p 5 (cid:0) : = 1 (cid:0) 2 1 + 2 1p 5
Phân thức đơn giản
Bổ đề
▶ Xét p(x) là đa thức có bậc nhỏ hơn n với (cid:11)1; (cid:1) (cid:1) (cid:1) ; (cid:11)n là các nghiệm khác 0 đôi một phân biệt.
▶ Khi đó tồn tại các hằng số c1; (cid:1) (cid:1) (cid:1) ; cn thỏa mãn
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
26 / 26
= + (cid:1) (cid:1) (cid:1) + : p(x) (1 (cid:0) (cid:11)1x) (cid:1) (cid:1) (cid:1) (1 (cid:0) (cid:11)nx) c1 1 (cid:0) (cid:11)1x cn 1 (cid:0) (cid:11)nx
