Bài giảng Toán rời rạc - Bài 16: Công thức truy hồi - Trần Vĩnh Đức

Công thức truy hồi Trần Vĩnh Đức HUST Ngày 24 tháng 7 năm 2018 1 / 45 Nội dung Ví dụ Công thức truy hồi Công thức truy hồi và hàm sinh Số Catalan Công thức truy hồi tuyến tính Ví dụ Một quần thể vi trùng có số lượng cá thể tăng gấp đôi sau mỗi giờ. Nếu thoạt đầu có 5 cá thể hỏi sau 5 giờ số lượng của chúng là bao nhiêu? { an = 2an−1 a0 = 5 3 / 45 Bài tập Hãy tìm công thức tường minh cho dãy{ an = 2an a0 = 5 4 / 45 Ví dụ Xét một cầu thang với n bậc thang. Có bao nhiêu cách để đi lên cầu thang nếu chúng ta có thể leo lên 1 bậc hoặc 2 bậc trong mỗi bước? S1 = 1 S2 = 2 Sn+2 = Sn+1 + Sn với n ≥ 1 5 / 45 Ví dụ Có bao nhiêu xâu nhị phân độ dài n không chứa hai bit 0 liên tiếp? an+1 = an + an−1 a1 = 2 a2 = 3 6 / 45 Bài tập Hãy dùng kỹ thuật hàm sinh để tìm công thức tường minh cho dãy an+1 = an + an−1 a1 = 2 a2 = 3 7 / 45 Ví dụ Có bao nhiêu xâu tam phân độ dài n không chứa dãy con ”012”? an+3 = 3an+2 − an a1 = 3 a2 = 9 8 / 45 Nội dung Ví dụ Công thức truy hồi Công thức truy hồi và hàm sinh Số Catalan Công thức truy hồi tuyến tính Công thức truy hồi Định nghĩa Công thức truy hồi đối với dãy số 〈an〉 là công thức biểu diễn an qua một hay nhiều số hạng đi trước của dãy. 10 / 45 Ví dụ Xét dãy số 〈an〉 thỏa mãn công thức{ an = an−1 − an−2 a0 = 3a1 = 5 Từ công thức truy hồi ta có a2 = a1 − a0 = 5− 3 = 2 a3 = a2 − a1 = 2− 5 = −3 11 / 45 Định nghĩa Một dãy số được gọi là nghiệm của công thức truy hồi nếu các số hạng của nó thỏa mãn công thức truy hồi này. 12 / 45 Ví dụ ▶ Xét công thức truy hồi an = 2an−1 − an−2 với n ≥ 2. ▶ Dãy số 〈an〉 với an = 3n có phải là nghiệm của hệ thức truy hồi trên hay không? ▶ Còn dãy an = 2n? ▶ Còn dãy an = 5? 13 / 45 Ví dụ Giả sử một người gửi 10, 000 đô la vào tài khoản của mình tại một ngân hàng với lãi kép 11% mỗi năm. Hỏi sau 30 năm anh ta có bao nhiêu tiền trong tài khoản ngân hàng.{ Pn = Pn−1 + 0.11Pn−1 = 1.11Pn−1 P0 = 10, 000 đô la. 14 / 45 Ví dụ ▶ Một hệ máy tính coi một xâu các chữ số hệ thập phân là một từ mã hợp lệ nếu nó chứa một số chẵn chữ số 0. ▶ Chẳng hạn, 1230407869 là hợp lệ, còn 120987045608 là không hợp lệ. ▶ Giả sử an là số các từ mã độ dài n. ▶ Hãy tìm công thức truy hồi cho an. an = 9an−1 + (10n−1 − an−1) = 8an−1 + 10n−1. 15 / 45 Ví dụ ▶ Chúng ta vẽ n đường thẳng trên giấy sao cho mọi cặp đường thẳng đều cắt nhau và không có ba đường thẳng nào đồng quy. ▶ Các đường thẳng này chia mặt phẳng thành bao nhiêu miền? P1: JSN WB00623-07 WB00623-Tucker October 28, 2011 12:25 7.1 Recurrence Relation Models 285 Is there some systematic way to enumerate the ways to climb four stairs that breaks the problem into parts involving the ways to climb three or fewer stairs? Clearly, once the first step is taken there are three or fewer stairs remaining to climb. Thus we see that after a first step of one stair, there are a3 ways to continue the climb up the remaining three stairs. If the first step covers two stairs, then there are a2 ways to continue up the remaining two stairs. So a4 = a3+ a2. We confirm that the values for a4, a3, a2 satisfy this relation: 5= 3+ 2. This argument applies to the first step when climbing any number of stairs, as is shown in Figures 7.1b and 7.1c. Thus an = an−1+ an−2. In Section 7.3 we obtain an explicit solution to this recurrence relation. The rela- tion an = an−1+ an−2 is called the Fibonacci relation. The numbers an generated by the Fibonacci relation with the initial conditions a0 = a1 = 1 are called the Fibonacci numbers. They begin 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89. Fibonacci numbers arise natu- rally in many areas of combinatorial mathematics. There is even a journal, Fibonacci Quarterly, devoted solely to research involving the Fibonacci relation and Fibonacci numbers. Fibonacci numbers have been applied to other fields of mathematics, such as numerical analysis. They occur in the natural world—for example, the arrangements of petals in some flowers. For more information about the occurrences of Fibonacci numbers in nature, see [1]. Example 3: Dividing the Plane Suppose we draw n straight lines on a piece of paper so that every pair of lines intersect (but no three lines intersect at a common point). Into how many regions do these n lines divide the plane? Again we approach the problem initially by examining the situation for small values of n. With one line, the paper is divided into two regions. With two lines, we get four regions—that is, a2 = 4. See Figure 7.2a. From Figure 7.2b, we see that a3 = 7. The skeptical reader may ask: how do we know that three intersecting lines will always create seven regions? Let us go back one step, then. Clearly two intersecting lines will always yield four regions, as shown in Figure 7.2a. Now let us examine the effect of drawing the third line (labeled “3” in Figure 7.2b). It must cross each of the other two lines (at different points). Before, between, and after these two intersection points, the third line cuts through three of the regions formed by the first two lines (this action of the third line does not depend on how it is drawn, just that it intersects the other two lines). So in severing three regions, the third line must form three new regions, actually creating six new regions out of three old regions. Thus a3 = a2+ 3= 4+ 3= 7, independently of how the third line is drawn. 2 3 4 1 2 3 1 2 1 (b) (c)(a)Figure 7.2 16 / 45 Ví dụ (Chọn không lặp) Đặt an,k là số cách chọn tập con k phần tử từ tập n phần tử. Hãy tìm công thức truy hồi cho ak,n. an,k = an−1,k + an−1,k−1 (Đẳng thức Pascal) 17 / 45 Ví dụ (Bỏ bóng) Hãy tìm công thức truy hồi cho số cách bỏ n quả bóng giống nhau và k chiếc hộp phân biệt sao cho mỗi hộp chỉ có 2 hoặc 3 hoặc 4 quả bóng. an,k = an−2,k−1 + an−3,k−1 + an−4,k−1. 18 / 45 Ví dụ (Hệ thức truy hồi) Tìm công thức truy hồi cho: Số xâu tam phân độ dài n với một số chẵn 0 và một số lẻ 1. an = bn−1 + cn−1 + an−1 bn = 3n−1 − cn−1 cn = 3n−1 − bn−1 19 / 45 Nội dung Ví dụ Công thức truy hồi Công thức truy hồi và hàm sinh Số Catalan Công thức truy hồi tuyến tính Ví dụ Tìm hàm sinh cho dãy số là nghiệm của công thức truy hồi an = an−1 + n a0 = 1 21 / 45 Ví dụ (Chọn không lặp) Đặt gn(x) là họ các hàm sinh gn(x) = an,0 + an,1x+ · · ·+ an,kxk + . . . an,nxn thỏa mãn công thức truy hồi an,k = an−1,k + an−1,k−1 an,0 = an,n = 1 an,k = 0 với mọi k > n Hãy tìm dạng đóng cho hàm sinh gn(x) và dùng nó để tìm công thức tường minh cho an,k. 22 / 45 Giải gn(x)− 1 = n∑ k=1 an,kxk = n∑ k=1 (an−1,kxk + an−1,k−1xk) = n∑ k=1 an−1,kxk + x n−1∑ h=0 an−1,hxk) = gn−1(x)− 1 + xgn−1(x) Vậy ta được gn(x) = gn−1(x) + xgn−1(x) = (1 + x)gn−1(x) Giải công thức truy hồi trên, ta được gn(x) = (1 + x)ng0(x) = (1 + x)n. 23 / 45 Nội dung Ví dụ Công thức truy hồi Công thức truy hồi và hàm sinh Số Catalan Công thức truy hồi tuyến tính Số Catalan Có bao nhiêu cách đặt dấu ngoặc cho tổng n số để chỉ định trình tự thực hiện phép cộng? Ví dụ Với n = 4 ta có 5 khả năng: (((a+ b) + c) + d) ((a+ (b+ c)) + d) ((a+ b) + (c+ d)) (a+ ((b+ c) + d)) (a+ (b+ (c+ d))) 25 / 45 Công thức truy hồi cho các số Catalan Cn = C1Cn−1 + C2Cn−2 + · · ·+ Cn−1C1 = n−1∑ i=1 CiCn−i. Công thức này suy ra từ các cách đặt dấu ngoặc: (1 . . .n) = (1)(2 . . .n), (1 2)(3 . . .n), · · · (1 . . .n− 1)(n). Ta đặt C0 = 0 và ta biết C1 = 1. 26 / 45 Công thức truy hồi cho các số Catalan Cn = C0Cn + C1Cn−1 + C2Cn−2 + · · ·+ Cn−1C1 + CnC0 = n∑ i=0 CiCn−i. 27 / 45 Hàm sinh của số Catalan Xét hàm sinh của Cn: C(x) = 0 + x+ x2 + 2x3 + 5x4 + · · · = 0 + ∑ n≥1 Cnxn = ∑ n≥1 n∑ i=0 (CiCn−i) xn Theo luật tích C(x)2 = C02 + (C0C1 + C1C0)x+ (C0C2 + C1C1 + C2C0)x2 + · · · = 0 + 0 + ∑ n≥2 ( n∑ i=0 CiCn−i ) xn = C(x)− x 28 / 45 Hàm sinh cho các số Catalan Giải phương trình C(x)2 − C(x) + x = 0. Ta được C(x) = 1± √ 1− 4x 2 = 1± (1− 4x)1/2 2 . Vì C0 = 0, ta lấy nghiệm C(x) = 1− (1− 4x) 1/2 2 . 29 / 45 Định lý nhị thức tổng quát Với số thực q bất kỳ, khai triển của chuỗi (1 + y)q = (q 0 ) + (q 1 ) y+ (q 2 ) y2 + · · ·+ (q n ) yn + · · · có hệ số (q n ) của yn được định nghĩa bởi(q n ) := q(q− 1)(q− 2)× · · · × [q− (n− 1)] n! . (Công thức cho hệ số tổng quát (q n ) xuất hiện từ chuỗi Taylor cho (1 + y)q.) 30 / 45 Bổ đề Với mỗi n ≥ 1, ( 1/2 n ) = (−1)n−1 n × ( 2n−2 n−1 ) 22n−1 31 / 45 Định lý Hàm sinh của dãy số Catalan là C(x) = 1− (1− 4x) 1/2 2 = ∞∑ n=1 1 n ( 2n− 2 n− 1 ) xn. 32 / 45 Số Catalan Cn = 1 n ( 2n− 2 n− 1 ) . 33 / 45 Bài tập Xét bàn cờ n× n: Xét đường đi ngắn nhất từ góc A tới góc B đi qua các cạnh (mỗi đường qua 2n cạnh). 1. Có bao nhiêu đường như vậy? 2. Chứng minh rằng số đường không xuống dưới đường chéo chính là số Catalan Cn. 3. Hãy tìm cách chứng minh số Catalan Cn = 1n ( 2n−2 n−1 ) mà không dùng hàm sinh. 34 / 45 Nội dung Ví dụ Công thức truy hồi Công thức truy hồi và hàm sinh Số Catalan Công thức truy hồi tuyến tính Định nghĩa Một hệ thức truy hồi tuyến tính thuần nhất bậc k với hệ số hằng là hệ thức truy hồi có dạng an = c1an−1 + c2an−2 + · · ·+ ckan−k trong đó c1, c2, . . . , ck là các số thực và ck ̸= 0. 36 / 45 Ví dụ ▶ Công thức truy hồi Pn = (1.11)Pn−1 là tuyến tính thuần nhất bậc một. ▶ Công thức fn = fn−1 + fn−2 là tuyến tính thuần nhất bậc hai. 37 / 45 Định lý Cho c1, c2 là hai số thực. Giả sử phương trình r2 − c1r− c2 = 0 có hai nghiệm phân biệt r1, r2. Khi đó dãy 〈an〉 là nghiệm của hệ thức truy hồi an = c1an−1 + c2an−2 nếu và chỉ nếu an = α1r1n + α2r2n trong đó α1, α2 là các hằng số. 38 / 45 Ví dụ Tìm nghiệm của hệ thức truy hồi an = an−1 + 2an−2 với a0 = 2, a1 = 7. 39 / 45 Bài tập Hãy chứng minh định lý trước dùng hàm sinh. 40 / 45 Định lý Cho c1 và c2 là hai số thực và c2 ̸= 0. Giả sử phương trình r2 − c1r− c2 = 0 có nghiệm kép r0. Khi đó dãy 〈an〉 là nghiệm của hệ thức truy hồi an = c1an−1 + c2an−2 nếu và chỉ nếu an = α1r0n + α2nr0n trong đó α1, α2 là các hằng số. 41 / 45 Ví dụ Tìm nghiệm của hệ thức truy hồi an = 6an−1 − 9an−2 với a0 = 1, a1 = 6. 42 / 45 Bài tập Hãy chứng minh định lý trước dùng hàm sinh. 43 / 45 Định lý Cho c1, c2, . . . , ck là các số thực. Giả sử phương trình rk − c1rk−1 − · · · − ck = 0 có k nghiệm phân biệt r1, r2, . . . , rk. Khi đó dãy 〈an〉 là nghiệm của hệ thức truy hồi an = c1an−1 + c2an−2 + · · ·+ ckan−k nếu và chỉ nếu an = α1r1n + α2r2n + · · ·+ αkrkn trong đó αi là các hằng số. 44 / 45 Ví dụ Tìm nghiệm của hệ thức truy hồi an = 6an−1 − 11an−2 + 6an−3 với a0 = 2, a1 = 5 và a2 = 15. 45 / 45