Hàm sinh và ứng dụng

27/03/2008 1 HÀM SINH VÀ ỨNG DỤNG Phạm Thế Bảo Khoa Toán – Tin học Trường Đại học Khoa học Tự nhiên Tp.HCM • Bài toán: có 12 trái táo chia cho 03 bạn A, B, C. Theo qui định: A lấy ít nhất 04 trái, B và C lấy ít nhất 02 trái, C không lấy quá 05 trái. Vậy, có bao nhiêu cách chia? Giới thiệu Giải: gọi a, b, c là số táo của các bạn A, B, C được chia. Ta có: 12 4 2 (*) a b c a b ⎧ + + =⎪⎪⎪ ≥⎪⎪⎨⎪ ≥⎪ Số cách chia táo chính là số nghiệm của phương trình (*) 5 2c⎪⎪ ≥ ≥⎪⎩ Phạm Thế Bảo 27/03/2008 2 • Hay gọi G={a+b+c=12/ a≥4, b ≥2, 5≥c ≥2}. Thì |G|=số lời giải. Ta đặt H={xa+b+c/ a,b,c∈N, xa+b+c = x12, a≥4, b ≥2, 5≥c ≥2} thì |G|= |H|Æ cần tìm |H|Æ chính là hệ số của x12 trong phương trình f(x)=(x4+x5+ )(x2+x3+ )(x2+ +x5)... ... ... = Khi k=12 thì ak chính là giá trị cần tìm Æ mục tiêu ể 4 8 2 2 5 a b c k k a k b c x a x+ + ≤ ≤∞ = ≤ ≤∞ ≤ ≤ =∑ ∑ của bài toán là tìm khai tri n của f(x). Phạm Thế Bảo • Xét chuỗi lũy thừa nếu Chuỗi lũy thừa 0 n vôùi a n n n a z C ∞ = ∈∑ • Cho dãy số {an}∞n=0. Hàm sinh của dãy này là h ỗi 0 ( ) n n=0 hoäi tuï veà G(z) thì chuoãi hoäi tuï vaø G(z)= a n k n k k n S z a z z = ∞ = ∑ ∑ ∞∑c u . 0 n n n a z = Phạm Thế Bảo 27/03/2008 3 • Quay lại bài toán chia táo. Thay vì 4≤a≤∞ và 2≤b≤∞ ta cũng có thể viết 4≤a≤8 và 2≤b≤6. Thì: 8 6 5 ( ) a b cf ⎛ ⎞⎛ ⎞⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟∑ ∑ ∑ 4 2 2 4 2 3 4 2 2 3 4 2 2 3 8 2 3 4 2 2 3 25 4 8 8 5 2 4 3 (1 ) (1 ) (1 ) (1 ) (1 ) 1 1 1(1 ) (1 ) ( ) = a b c z z z z z z z z z z z z z z z z z z z z z z z z z z z zz z z z = = = = ⎝ ⎠⎝ ⎠⎝ ⎠ = + + + + + + + + + + + = + + + + + + + ⎛ ⎞ ⎛ ⎞− − = − −⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠1 1 1 caàn xaùc ñònh heä soá c z z z− − − ⇒ 5 2 4 31(1 ) (1 ) (1 ) 4uûa z trong z z z − − − Phạm Thế Bảo Theo chuỗi lũy thừa ta có: Nê t ó hệ ố ủ 4 t h ỗi à là 2 3 3 4 21 1 ... ... 1 2(1 ) kkz z z kz ⎛ + ⎞⎛ ⎞ ⎛ ⎞ ⎛ ⎞= + + + + +⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟− ⎝ ⎠ ⎝ ⎠ ⎝ ⎠⎝ ⎠ n a c s c a z rong c u n y Vậy có 14 cách giải bài toán chia táo. 6 6! 5*61 1 1 14 4 4!2! 2 ⎛ ⎞= − = − = − =⎜ ⎟⎝ ⎠ Phạm Thế Bảo 27/03/2008 4 Tương tự cho bài toán: Xét tập hợp {1,2, ...,15} có bao nhiêu tập con có 04 phần tử mà không chứa 02 số liên tiếp nhau. Vị trí các phền tử trong một tập con không quan trọng, ví dụ: {4,7,9,12} và {9,12,4,7} là như nhau. Phạm Thế Bảo Dùng hàm sinh giải hệ thức truy hồi • Trong quá trình phân tích thuật toán, chúng ta tì đ độ hứ t ủ th ật t á là ôm ược p c ạp c a u o n c ng thức truy hồi.Ví dụ: 0 0 11 1 2 0 0 0 5 2 2 6 5 0 2 2 hay n n n nn k k x a a n a a a nx x n − − − = = = =+ − + = ∀ ≥= + ∑ • Chúng ta sẽ dùng hàm sinh để tìm nghiệm (độ phức tạp của thuật toán) Phạm Thế Bảo 27/03/2008 5 Hàm sinh của dãy xác suất • Xét biến A có thể lấy các giá trị 0, 1, 2, ... Với á ấ là Với ≥0 à hì1∞∑x c su t p0, p1, p2, ... pi v t hàm sinh của dãy xác suất (phân bố) là Ví d ét th ật t á tì ố lớ hất t 0 k k p = = 0 ( ) kk k G z p z ∞ = = ∑ • ụ x u o n m s n n rong mảng (ví dụ 3 – phần đánh giá bằng công cụ toán học cơ bản). Phạm Thế Bảo • Có thể thấy độ phức tạp là O(n). Vậy số lần thực hiện α: • Tối thiểu: 0 • Tối đa: n-1 • Trung bình: ? Nếu xét n=3, dữ liệu là một dãy số đôi một phân biệt {a[0], a[1], a[0]} Æ có ? tổ hợp thứ tự với xác suất ngang nhau là ? 6 1/6 Phạm Thế Bảo 27/03/2008 6 Vị trí Số lần gán Trung bình A[0] < A[1] < A[2] A[0] < A[2] < A[1] A[1] < A[0] < A[2] A[1] < A[2] < A[0] 2 1 1 0 =5/6 A[2] < A[0] < A[1] A[2] < A[1] < A[0] 1 0 Dùng hàm sinh tính giá trị trung bình của α. Giả sử mỗi n, gọi An là số lần thực hiện α thì 0≤An≤n-1. Với mỗi k gọi pn,k là xác suất để Ak =k. Có pn,k ≥0, ∀k∈{0,1,2,...,n-1} và , 0 1n k k p ∞ = =∑ Phạm Thế Bảo • Hàm sinh • Gọi B là biến cố an lớn nhất trong {a1, a2, ..., an} , 0 ( ) kn n k k G z p z ∞ = = ∑ 1( ) (xaùc suaát taïi böôùc thöù n coù 1 pheùp gaùn)P B = n-1vaø P(B)=1-P(B)= (xaùc suaát taïi böôùc thöù n khoâng coù pheùp gaùn) n n ) ( ). ( / ) ( ). ( / )n n n-1,k-1 n n-1,k coù P(A vaø P(A /B)=p , P(A / B)=p n nP B P A B P B P A B= + 1 n,k n-1,k-1 n-1,k n-1 p p + p nn ⇒ = Phạm Thế Bảo 27/03/2008 7 • Tại bước thứ n có 01 phép gán thì n-1 bước trước đó có k-1 phép gán. • Tại bước thứ n không có phép gán thì n-1 bước trước đó có k phép gán. 1, 1 1, 1 1 1 1( ) 1 ( ) n-1= + n k k n n k n k k k n G z p z p z n z n G z − − − = = + −= ∑ ∑ 1 2 1... 1 2 1 1 1( ) 1 truy hoài ... = haïng töû thöù k: 1ø t ù n z n z n z n n z k z k k − + − + − +⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟ ⎜ ⎟−⎝ ⎠ ⎝ ⎠ ⎝ ⎠ + − − − 1 kg ma a co k neân laø haøm sinh cuûa da z k k k k z k k = = + + = + − 2 2 1) ( )n õy xaùc suaát mean(G n n k k k mean g k= = ⇒ = =∑ ∑ Phạm Thế Bảo Q l i bài t á khi 3 t ó• uay ạ o n n= a c mean(G3) = 1/2 +1/3 =5/6 Phạm Thế Bảo