Bài giảng Toán rời rạc - Chương 1: Bài toán đếm - Nguyễn Đức Nghĩa

9.8.7 = 5040. Toán rời rạc Chỉnh hợp không lặp Chú ý: Để giải ví dụ 2 có thể lập luận trực tiếp theo nguyên lý nhân: Ta lần lượt xếp các học sinh vào chỗ ngồi. Học sinh thứ nhất có 10 cách xếp Tiếp đến học sinh thứ hai có thể xếp vào 1 trong 9 chỗ còn lại, ... Theo nguyên lý nhân có 10.9.8.7 cách xếp Toán rời rạc Hoán vị Định nghĩa. Ta gọi hoán vị từ n phần tử của X là bộ có thứ tự gồm n thành phần, mỗi thành phần đều là phần tử của X, các thành phần khác nhau từng đôi . Ký hiệu số lượng hoán vị từ n phần tử là P n . Theo định nghĩa, một hoán vị từ n phần tử của X có thể biểu diễn bởi ( a 1 , a 2 , ..., a n ), a i  X , i = 1, 2, ..., n, a i  a j , i  j. Rõ ràng P n = P n n . Vì vậy, ta có Định lý 3. Toán rời rạc Hoán vị VÝ dô 1 . 6 ng­êi ®øng xÕp thµnh mét hµng ngang ®Ó chôp ¶nh. Hái cã thÓ bè trÝ bao nhiªu kiÓu? Gi¶i : Mçi kiÓu ¶nh lµ mét ho¸n vÞ cña 6 ng­êi. Tõ ®ã nhËn ®­îc sè kiÓu ¶nh cã thÓ bè trÝ lµ 6! = 720. VÝ dô 2. CÇn bè trÝ viÖc thùc hiÖn n ch­¬ng tr×nh trªn mét m¸y vi tÝnh. Hái cã bao nhiªu c¸ch? Gi¶i : §¸nh sè c¸c ch­¬ng tr×nh bëi 1, 2,..., n . Mçi c¸ch bè trÝ viÖc thùc hiÖn c¸c ch­¬ng tr×nh trªn m¸y cã thÓ biÓu diÔn bëi mét ho¸n vÞ cña 1, 2, ..., n . Tõ ®ã suy ra sè c¸ch bè trÝ cÇn t×m lµ n ! Toán rời rạc Hoán vị Ví dụ 3. Có bao nhiêu song ánh từ tập n phần tử X vào chính nó? (Mỗi song ánh như vậy được gọi là một phép thế). Giải. Mçi song ¸nh f cÇn ®Õm ®­îc x¸c ®Þnh bëi bé ¶nh ( f ( u 1 ), f ( u 2 ), ..., f ( u n )), trong ®ã f ( u i )  V , i =1, 2, ..., n , f ( u i )  f ( u j ) , i j. Tõ ®ã nhËn ®­îc sè cÇn t×m lµ n ! Ví dụ 4. Có bao nhiêu cách bố trí n thợ thực hiện n việc sao cho mỗi thợ thực hiện một việc và mỗi việc do đúng một thợ thực hiện Giải: n ! Toán rời rạc Tổ hợp Định nghĩa. Ta gọi tổ hợp chập m từ n phần tử của X là bộ không có thứ tự gồm m thành phần, mỗi thành phần đều là phần tử của X, các thành phần khác nhau từng đôi . Ký hiệu số lượng tổ hợp chập m từ n phần tử là C n m (đôi khi ta sẽ sử dụng ký hiệu C ( n,m )) Theo định nghĩa, một tổ hợp chập m từ n phần tử của X có thể biểu diễn bởi bộ không có thứ tự { a 1 , a 2 , ..., a m }, a i  X , i = 1, 2, ..., m, a i  a j , i  j. Với giả thiết X= {1, 2,..., n }, một tổ hợp chập m từ n phần tử của X có thể biểu diễn bởi bộ có thứ tự ( a 1 , a 2 , ..., a m ), a i  X , i = 1, 2, ..., m, 1  a 1 < a 2 < ...<a m  n. Toán rời rạc Tổ hợp ViÖc ®Õm c¸c tæ hîp cã khã kh¨n h¬n so víi việc đếm c¸c cÊu h×nh ®· tr×nh bµy, tuy nhiªn c¸ch ®Õm d­íi ®©y cho biÕt c¸ch vËn dông c¸c nguyªn lý cïng víi c¸c kÕt qu¶ ®Õm ®· biÕt trong viÖc ®Õm mét cÊu h×nh míi. XÐt tËp hîp tÊt c¶ c¸c chØnh hîp kh«ng lÆp chËp m cña n phÇn tö. Chia chóng thµnh nh÷ng líp sao cho hai chØnh hîp thuéc cïng mét líp chØ kh¸c nhau vÒ thø tù. Râ rµng c¸c líp nµy lµ mét ph©n ho¹ch trªn tËp ®ang xÐt vµ mçi líp nh­ thÕ lµ t­¬ng øng víi mét tæ hîp chËp m cña n . Sè chØnh hîp trong mçi líp lµ b»ng nhau vµ b»ng m ! (sè ho¸n vÞ). Sè c¸c líp lµ b»ng sè tæ hîp chËp m cña n . Theo nguyªn lý céng, tÝch cña m! víi sè nµy lµ b»ng sè c¸c chØnh hîp kh«ng lÆp chËp m cña n , nghÜa lµ b»ng n ( n- 1) .. .( n-m+ 1). Tõ ®ã nhËn ®­îc sè tæ hîp chËp m cña n lµ Toán rời rạc Tổ hợp Định lý 4. C ( n,m ) được gọi là hệ số tổ hợp. Khi nhËn xÐt r»ng, gi¸ trÞ cña phÐp chia trong công thức của định lý 4 lµ mét sè nguyªn, ta nhËn ®­îc mét kÕt qu¶ lý thó trong sè häc: TÝch cña k sè tù nhiªn liªn tiÕp bao giê còng chia hÕt cho k !. Toán rời rạc Tổ hợp VÝ dô 1 . Cã n ®éi bãng thi ®Êu vßng trßn. Hái ph¶i tæ chøc bao nhiªu trËn ®Êu? Gi¶i : Cø 2 ®éi th× cã mét trËn. Tõ ®ã suy ra sè trËn ®Êu sÏ b»ng sè c¸ch chän 2 ®éi tõ n ®éi, nghÜa lµ b»ng C ( n ,2) = n ( n -1)/2. VÝ dô 2 . Hái cã bao nhiªu giao ®iÓm cña c¸c ®­êng chÐo cña mét ®a gi¸c låi n (n  4 ) ®Ønh n»m ë trong ®a gi¸c, nÕu biÕt r»ng kh«ng cã ba ®­êng chÐo nµo ®ång quy t¹i ®iÓm ë trong ®a gi¸c? Gi¶i : Cø 4 ®Ønh cña ®a gi¸c th× cã mét giao ®iÓm cña hai ®­êng chÐo n»m trong ®a gi¸c. Tõ ®ã suy ra sè giao ®iÓm cÇn ®Õm lµ C ( n ,4) = n ( n -1)( n -2)( n -3)/24. Toán rời rạc Bài toán chia kẹo Giả sử k và n là các số nguyên không âm. Hỏi phương trình sau đây có bao nhiêu nghiệm? Nội dung thực tế: Cần chia n cái kẹo cho k em bé B 1 , B 2 , ,B k . Hỏi có bao nhiêu cách chia khác nhau? Toán rời rạc Bài toán chia kẹo Cần thả n quả bóng giống nhau vào k phòng: Room1, Room2, , Roomk. Hỏi có bao nhiêu cách phân bổ khác nhau? Nếu gọi t j là số lượng quả bóng thả vào Room j , j = 1, 2, ..., n ; thì vấn đề đặt ra dẫn về bài toán: Hỏi phương trình sau đây có bao nhiêu nghiệm nguyên không âm? Toán rời rạc Xét dãy n+k -1 hộp. Tô k -1 hộp nào đó bởi màu xám; các hộp xám này sẽ là vách ngăn: D1, D2, D(k-1). Ví dụ: với n =16, k =6 Thả n quả bóng vào n hộp còn lại, mỗi hộp 1 quả. Giải bài toán chia kẹo D1 D2 D3 D5 D4 Toán rời rạc Ví dụ, với n=16, k=6 Thả các quả bóng trước vách ngăn D1 vào Room1, các quả bóng giữa vách ngăn D1 và D2 vào Room2, vân vân, và cuối cùng các quả bóng sau D(k-1) vào Room(k). Giải bài toán chia kẹo Room1 Room2 Room3 Room4 Room5 Room6 D1 D2 D3 D5 D4 Toán rời rạc Như vậy, rõ ràng tồn tại tương ứng 1-1 giữa một cách phân bổ các quả bóng và một cách chọn k -1 hộp trong số n+k -1 hộp làm vách ngăn. Do có tất cả cách chọn k -1 hộp từ n+k -1 hộp, nên đó cũng chính là số cách phân bổ n quả bóng vào k phòng, cũng chính là số cách chia n cái kẹo cho k em bé và cũng chính là số nghiệm nguyên không âm của phương trình: Giải bài toán chia kẹo Toán rời rạc Bài toán chia kẹo 2. Có bao nhiêu cách chia n cái kẹo cho k em bé mà trong đó mỗi em được ít nhất một cái? Hay tương đương: Hỏi phương trình sau đây : t 1 + t 2 + ... + t k = n . có bao nhiêu nghiệm nguyên dương? Trước hết chia cho mỗi em 1 cái kẹo, n-k cái kẹo còn lại sẽ được chia cho k em bé. Bài toán dẫn về: Hỏi có bao nhiêu cách chia n-k cái kẹo cho k em bé. Sử dụng kết quả bài trước, ta có đáp số cần tìm là : Giải bài toán chia kẹo Toán rời rạc Hệ số tổ hợp D­íi ®©y lµ mét vµi tÝnh chÊt cña c¸c hÖ sè tæ hîp: a) §èi xøng C ( n,m ) = C ( n,n-m ) b) §iÒu kiÖn ®Çu C ( n ,0) = 1; C ( n,n ) = 1, n  0 c) C«ng thøc ®Ö qui C ( n,m ) = C ( n -1, m ) + C ( n -1, m -1), n > m > 0 Điều kiện đầu suy trực tiếp từ định nghĩa của hệ số tổ hợp. C¸c tính chất còn lại có thể chứng minh nhờ sử dụng công thức trong định lý 4. Toán rời rạc Tổ hợp Từ b) và c), ta có thể tính tất cả các hệ số tổ hợp chỉ bằng phép cộng. Các hệ số này được tính và viết lần lượt theo từng dòng (mỗi dòng ứng với một giá trị n= 0, 1, ...), trên mỗi dòng chúng được tính và viết lần lượt theo từng cột (mỗi cột ứng với một giá trị m = 0, 1, ..., n ) theo bảng tam giác dưới đây: B¶ng nµy ®­îc gäi lµ tam gi¸c Pascal . Toán rời rạc Tổ hợp Tam giác Pascal, n=8 Toán rời rạc Tổ hợp C¸c hÖ sè tæ hîp cã liªn quan chÆt chÏ víi viÖc khai triÓn luü thõa cña mét nhÞ thøc. ThËt vËy, trong tÝch ( x+y ) n = ( x+y ) ( x+y ) . . . ( x+y ) hÖ sè cña x m y n-m sÏ lµ sè c¸ch chän m nh©n tö ( x + y ) mµ tõ ®ã ta lÊy ra x vµ ®ång thêi trong n-m nh©n tö cßn l¹i ta lÊy ra y , nghÜa lµ C«ng thøc t rên ®­îc gäi lµ khai triÓn nhÞ thøc Newton vµ c¸c hÖ sè tæ hîp cßn ®­îc gäi lµ c¸c hÖ sè nhÞ thøc . Toán rời rạc Tổ hợp Trong c«ng thøc Niuton đặt y =1 ta có : (*) RÊt nhiÒu ®¼ng thøc vÒ hÖ sè tæ hîp ®­îc suy tõ (*). Ch¼ng h¹n, trong (*) chän x = 1 ta ®­îc: C ( n ,0) + C ( n ,1) + ...+ C ( n,n ) = 2 n , tøc lµ nhËn ®­îc kÕt qu¶ ®· biÕt: sè c¸c tËp con cña mét n -tËp b»ng 2 n , cßn nÕu chän x = -1 ta ®­îc: C ( n ,0) – C ( n ,1) + C ( n ,2) - ...+(-1) n C ( n,n ) = 0, tøc lµ sè c¸c tËp con ch½n (cã sè phÇn tö lµ sè ch½n) b»ng c¸c sè tËp con lÎ vµ b»ng 2 n- 1 . NhiÒu tÝnh chÊt cña hÖ sè tæ hîp cã thÓ thu ®­îc tõ (*) b»ng c¸ch lÊy ®¹o hµm hoÆc tÝch ph©n theo x hai vÕ cña ®¼ng thøc nµy mét sè h÷u h¹n lÇn, sau ®ã g¸n cho x nh÷ng gi¸ trÞ cô thÓ. Toán rời rạc Chương 1. BÀI TOÁN ĐẾM Nguyên lý cộng và nguyên lý nhân Các cấu hình tổ hợp cơ bản Nguyên lý bù trừ Công thức đệ qui Hàm sinh Toán rời rạc 3. Nguyên lý bù trừ (The inclusion-exclusion principle) 3.1. Phát biểu nguyên lý 3.2. Các ví dụ áp dụng Toán rời rạc 3.1. Phát biểu nguyên lý Nguyên lý bù trừ trong trường hợp hai tập: |A  B | = |A| + |B| - |A  B | (1) Giả sử A có 5 phần tử, B có 3 phần tử và có 1 phần tử thuộc vào cả A lẫn B Khi đó số phần tử của hợp hai tập là 5+3-1 = 7, chứ không phải là 8 CM: Toán rời rạc Nguyên lý bù trừ Mở rộng cho trường hợp 3 tập: Giả sử A, B, C là ba tập bất kỳ. Khi đó: |A B C | = |(A B)C) | = |A B | + |C|  |(A B)C | = |A| +| B | + |C|  |A B |  |(A C)(BC) | = |A| +| B | + |C|  |A B |  |A  C | |BC) |+ |A  B C) | Vậy |A BC | = |A|+| B |+ |C|  |A B |  |A  C | |BC) |+ |A  B C) | (2) Có thể chứng minh bằng lập luận trực tiếp! Toán rời rạc Nguyên lý bù trừ |A BC | = |A|+| B |+ |C|  |A B |  |A  C | |BC) |+ |A  B C) | (2) Có thể chứng minh bằng lập luận trực tiếp: Trong tổng của ba số hạng đầu tiên các phần tử chung của A và B được tính hai lần, vì vậy phải trừ bớt đi một lần. Tương tự như vậy đối với các phần tử chung của A và C và các phần tử chung của B và C. Thế nhưng, trừ như vậy là hơi quá, bởi vì những phần tử chung của cả ba tập A, B và C chưa được tính đến trong tổng của 6 số hạng đầu tiên. Vì vậy phải cộng bù lại . Toán rời rạc Nguyên lý bù trừ §Þnh lý. Gi¶ sö A 1 , A 2 , ... , A m lµ c¸c tËp h÷u h¹n. Khi ®ã trong ®ã ( N k lµ tæng sè phÇn tö cña tÊt c¶ c¸c tËp lµ giao cña k tËp lÊy tõ m tËp ®· cho, nãi riªng N 1 = N ( A 1 ) + ... + N ( A m ) , N m = N ( A 1  A 2  ...  A m ) ). Toán rời rạc Nguyên lý bù trừ Chøng minh. Chó ý r»ng, sè c¸c giao cña k tËp lÊy tõ m tËp b»ng C ( m,k ), k = 1,2 ,...,m. §Ó chøng minh c«ng thøc cña nguyªn lý bï trõ, ta sÏ tÝnh xem mçi phÇn tö cña tËp A 1  A 2  . . .  A m ®­îc ®Õm bao nhiªu lÇn trong vÕ ph¶i: XÐt mét phÇn tö tuú ý a  A 1  A 2  . . .  A m . Gi¶ sö a lµ phÇn tö cña k tËp trong sè m tËp ®· cho. Khi ®ã a ®­îc ®Õm ë vÕ ph¶i cña c«ng thøc C ( k ,1) – C ( k ,2)+ ... + (-1) k -1 C ( k,k ) lÇn. Do C ( k ,1) – C ( k ,2)+ ... + (-1) k -1 C ( k,k ) = 1 – [ C ( k ,0) – ( C ( k ,1) – C ( k ,2)+ ... + (-1) k -1 C ( k,k )) ] = 1 – (1 – 1) k = 1 Tõ ®ã suy ra ®¼ng thøc cÇn chøng minh lµ ®óng Toán rời rạc Nguyên lý bù trừ B©y giê ta ®ång nhÊt tËp A k víi tÝnh chÊt A k cho trªn mét tËp X nµo ®ã vµ ®Õm xem cã bao nhiªu phÇn tö cña X kh«ng tho¶ m·n bÊt cø mét tÝnh chÊt A k nµo c¶. Gäi N lµ sè cÇn ®Õm . Do A 1  A 2  . . .  A m lµ tËp tÊt c¶ c¸c phÇn tö cña X tho¶ m·n Ýt nhÊt mét trong sè m tÝnh chÊt ®· cho, nªn ta cã: N = N ( X ) – N ( A 1  A 2  . . .  A m ) = N ( X ) – N 1 + N 2 -...+( – 1) m N m trong ®ã N k lµ tæng c¸c phÇn tö cña X tho¶ m·n k tÝnh chÊt lÊy tõ m tÝnh chÊt ®· cho. C«ng thøc thu ®­îc cho phÐp tÝnh N qua c¸c N k trong tr­êng hîp c¸c sè nµy dÔ tÝnh to¸n h¬n. Toán rời rạc 3. Nguyên lý bù trừ (The inclusion-exclusion principle) 3.1. Phát biểu nguyên lý 3.2. Các ví dụ áp dụng Toán rời rạc Nguyên lý bù trừ VÝ dô 1. Hái trong tËp X = {1, 2, ..., 10000} cã bao nhiªu sè kh«ng chia hÕt cho bÊt cø sè nµo trong c¸c sè 3, 4, 7? Gi¶i. Gäi A i ={ x  X : x chia hÕt cho i } , i = 3, 4, 7. Khi ®ã A 3  A 4  A 7 lµ tËp c¸c sè trong X chia hÕt cho Ýt nhÊt mét trong 3 sè 3, 4, 7, suy ra sè l­îng c¸c sè cÇn ®Õm sÏ lµ N ( X ) - N ( A 3  A 4  A 7 ) = 10000 – ( N 1 - N 2 + N 3 ). Ta cã N 1 = N ( A 3 ) + N ( A 4 ) + N ( A 7 ) = [10000/3] + [10000/4] + [10000/7] = 3333 + 2500 + 1428 =7261, Toán rời rạc Nguyên lý bù trừ N 2 = N ( A 3  A 4 ) + N ( A 3  A 7 ) + N ( A 4  A 7 ) = [10000/(3  4)] + [10000/(3  7)] + [10000/(4  7)] = 833 + 476 + 357 = 1666, N 3 = N ( A 3  A 4  A 7 ) = [10000/(3  4  7) ] = 119, ë ®©y ký hiÖu [ r ] ®Ó chØ sè nguyªn lín nhÊt kh«ng v­ît qu¸ r . Tõ ®ã sè l­îng c¸c sè cÇn ®Õm lµ 10000 - 7261 + 1666 - 119 = 4286. Toán rời rạc Nguyên lý bù trừ VÝ dô 2. Cã bao nhiªu x©u nhÞ ph©n ®é dµi 10 hoÆc lµ b¾t ®Çu bëi 00 hoÆc lµ kÕt thóc bëi 11? Gi¶i . DÔ thÊy lµ sè x©u nhÞ ph©n ®é dµi 10 b¾t ®Çu bëi 00 lµ 2 8 = 256 vµ sè x©u nhÞ ph©n ®é dµi 10 kÕt thóc bëi 11 lµ 2 8 = 256. Ngoµi ra, sè x©u nhÞ ph©n ®é dµi 10 b¾t ®Çu bëi 00 vµ kÕt thóc bëi 11 lµ 2 6 = 64. Theo nguyªn lý bï trõ suy ra sè x©u nhÞ ph©n hoÆc b¾t ®Çu bëi 00 hoÆc kÕt thóc bëi 11 lµ 256 + 256 - 64 = 448. Toán rời rạc Nguyên lý bù trừ: Bài toán bỏ thư Bµi to¸n bá th­ . Cã n l¸ th­ vµ n phong b× ghi s½n ®Þa chØ. Bá ngÉu nhiªn c¸c l¸ th­ vµo c¸c phong b×. Hái x¸c suÊt ®Ó x¶y ra kh«ng mét l¸ th­ nµo bá ®óng ®Þa chØ lµ bao nhiªu? Gi¶i : §¸nh sè c¸c l¸ th­ tõ 1 ®Õn n , c¸c phong b× t­¬ng øng víi chóng còng ®­îc ®¸nh sè tõ 1 ®Õn n . Mçi c¸ch bá th­ vµo phong b× cã thÓ biÓu diÔn bëi bé cã thø tù ( p 1 , p 2 , ..., p n ), trong ®ã p i lµ phong b× bá l¸ thø thø i . Tõ ®ã suy ra tån t¹i t­¬ng øng 1-1 gi÷a mét c¸ch bá th­ vµo phong b× víi mét ho¸n vÞ cña n sè. VËy cã tÊt c¶ n ! c¸ch bá th­. Toán rời rạc Nguyên lý bù trừ: Bài toán bỏ thư VÊn ®Ò cßn l¹i lµ ®Õm sè c¸ch bá th­ sao cho kh«ng cã l¸ th­ nµo ®óng ®Þa chØ. Gäi X lµ tËp hîp tÊt c¶ c¸c c¸ch bá th­ vµ A k lµ tÝnh chÊt l¸ th­ thø k bá ®óng ®Þa chØ. Khi ®ã, theo nguyªn lý bï trõ ta cã: N = N ( X ) – N 1 + N 2 – ...+( – 1) n N n trong ®ã  N lµ sè cÇn t×m, N ( X ) = n !, cßn N k lµ sè tÊt c¶ c¸c c¸ch bá th­ sao cho cã k l¸ th­ ®óng ®Þa chØ. Toán rời rạc Nguyên lý bù trừ: Bài toán bỏ thư Chó ý lµ nghÜa lµ, N k lµ tæng theo mäi c¸ch lÊy k l¸ th­ tõ n l¸, víi mçi c¸ch lÊy k l¸ th­, cã ( n-k )! c¸ch bá trong ®ã k l¸ nµy ®óng ®Þa chØ, ta nhËn ®­îc: N k = C ( n, k ).( n-k )! = n ! / k ! Do ®ã VËy x¸c suÊt cÇn t×m lµ: Toán rời rạc Nguyên lý bù trừ Mét ®iÒu lý thó lµ x¸c suÊt nµy dÇn ®Õn e -1 (nghÜa lµ cßn lín h¬n 1/3) khi n kh¸ lín. Sè trong bµi to¸n trªn ®­îc gäi lµ sè mÊt thø tù vµ ®­îc ký hiÖu lµ D n . D­íi ®©y lµ mét vµi gi¸ trÞ cña D n , cho ta thÊy D n t¨ng nhanh thÕ nµo so víi n : n 2 3 4 5 6 7 8 9 10 11 D n 1 2 9 44 265 1854 14833 133496 1334961 4890741 Số lượng toàn ánh Giả sử A ={ a 1 , a 2 , ..., a m } và B ={ b 1 , b 2 , ..., b n }. Trong các phần trước ta đã chứng minh: Số lượng ánh xạ từ A vào B là n m Số lượng đơn ánh từ A vào B là n ( n- 1) ... ( n - m+ 1) ( n  m ) . Số lượng song ánh từ A vào B là n ! ( n=m ). Bây giờ giả sử m  n , ta cần đếm số lượng toàn ánh từ A vào B. Nhắc lại: Ánh xạ f từ A vào B là toàn ánh nếu với mỗi phần tử b thuộc B đều tìm được a thuộc A sao cho f ( a )= b . (Do mỗi phần tử của A qua ánh xạ f được đặt tương ứng với đúng một phần tử của B , nên muốn có toàn ánh từ A vào B thì rõ ràng ta phải có m  n. ) Số lượng toàn ánh A f B Không tồn tại điểm không có mũi tên đi vào Ta muốn tất cả b i đều thuộc miền giá trị của f . Gọi P i là tính chất " b i không nằm trong miền giá trị của f ". Khi đó ta cần đếm số ánh xạ không có bất cứ tính chất nào trong số các tính chất P 1 ,..., P n . Ký hiệu: P i = tập các ánh xạ từ A vào B có tính chất P i , i = 1, 2, ..., n . Số lượng toàn ánh Theo nguyên lý bù trừ số lượng toàn ánh cần đếm là: N – N 1 + N 2 – ... +(–1) n N n . Ta có: N - số ánh xạ từ m -tập A vào n -tập B : n m Do N ( P i ) - số ánh xạ không có b i trong miền giá trị, nên N ( P i ) = ( n -1) m , do đó N 1 = C ( n ,1) ( n -1) m Do N ( P i  P j ) - số ánh xạ không có b i và b j trong miền giá trị, nên N ( P i  P j ) = ( n -2) m , do đó N 2 = C ( n ,2) ( n -2) m . Tổng quát ta có: dó đó N k = C ( n,k ) ( n - k ) m . Từ đó ta có số lượng toàn ánh là: n m – C ( n ,1)( n -1) m + C ( n ,2)( n -2) m – ...+ (-1) n -1 C ( n,n -1)1 m . Số lượng toàn ánh Ta viết gọn công thức n m – C ( n ,1)( n -1) m + C ( n ,2)( n -2) m – ...+ (-1) n -1 C ( n,n -1)1 m . dưới dạng sau đây: Toán rời rạc Chương 1. BÀI TOÁN ĐẾM Nguyên lý cộng và nguyên lý nhân Các cấu hình tổ hợp cơ bản Nguyên lý bù trừ Công thức đệ qui Hàm sinh Toán rời rạc 4. Công thức đệ qui Công thức đệ qui là công thức cho phép tính giá trị của các đại lượng theo từng bước, dựa vào các giá trị tính ở các bước trước và một số giá trị đầu. Là một kỹ thuật quan trọng cho phép giải nhiều bài toán đếm Toán rời rạc 4. Công thức đệ qui 4.1. Xây dựng công thức đệ qui 4.2. Giải công thức đệ qui Toán rời rạc 4.1 Xây dựng công thức đệ qui Ví dụ 1. Xây dựng công thức đệ qui cho C ( n,k ) - số lượng tập con k phần tử của tập n phần tử X . Giải: Theo định nghĩa C ( n ,0) = 1 và C ( n,n ) = 1 (1) Giả sử n > k > 0, ta xây dựng công thức đệ qui để tính C ( n,k ). Cố định một phần tử x  X . Phân tập các tập con k phần tử của X ra thành 2 tập: A – tập các tập con k phần tử có chứa x B – tập các tập con k phần tử không chứa x Toán rời rạc 4.1 Xây dựng công thức đệ qui Rõ ràng A và B tạo thành phân hoạch của tập tất cả các tập con k phần tử của X . Do đó, theo nguyên lý cộng: C ( n,k ) = | A | + | B |. Ta có: Do mỗi tập con trong A có chứa x , nên k -1 phần tử còn lại của nó là một tập con k -1 phần tử của tập X \{ x }, suy ra | A | = C ( n -1, k -1) Tương tự như vậy, | B | = C ( n -1, k ) Vậy, C ( n,k ) = C ( n -1, k -1) + C ( n -1, k ), n > k > 0 (2) Toán rời rạc 4.1 Xây dựng công thức đệ qui Công thức đệ qui (2) cùng với điều kiện đầu (1) cho phép tính giá trị của C ( n,k ) với mọi giá trị của n và k . Công thức đệ qui (2) cho phép viết hàm đệ qui sau đây để tính giá trị của C ( n,k ): function C(n,k: integer): longint; begin if (k=0) or (k=n) then C:=1 else C:= C(n-1,k-1) + C(n-1,k); end; Toán rời rạc 4.1 Xây dựng công thức đệ qui Hàm vừa xây dựng không cho một cách tính hiệu quả. Thực vậy, nếu gọi C * ( n,k ) là số phép toán “gán giá trị” phải thực hiện bởi lệnh gọi hàm C ( n,k ), dễ thấy C * ( n ,0) =1; C * ( n,n ) = 1 C * ( n,k ) = C * ( n -1, k -1) + C * ( n -1, k )+1, n > k > 0 tức là C * ( n,k ) thoả mãn công thức đệ qui tương tự như hệ số tổ hợp C ( n, k ), do đó: C * ( n,k )  n !/[ k !( n-k )!] và giá trị này là rất lớn khi n lớn và k = n /2. Dễ dàng xây dựng một hàm lặp để tính giá trị của C ( n,k ) một cách hiệu quả hơn. Toán rời rạc 4.1 Xây dựng công thức đệ qui VÝ dô 2 . Trªn mÆt ph¼ng, kÎ n ®­êng th¼ng sao cho kh«ng cã 2 ®­êng nµo song song vµ 3 ®­êng nµo ®ång quy. Hái mÆt ph¼ng ®­îc chia thµnh mÊy phÇn ? Gi¶i : Gäi sè phÇn mÆt ph¼ng ®­îc chia bëi n ®­êng th¼ng lµ S n . Râ ràng S 1 = 2, (3) XÐt n > 1, ta t×m c«ng thøc ®Ö qui cho S n . Toán rời rạc 4.1 Xây dựng công thức đệ qui Gi¶ sö ®· kÎ n -1 ®­êng th¼ng, khi ®ã mÆt ph¼ng ®­îc chia ra lµm S n -1 phÇn. B©y giê kÎ thªm ®­êng th¼ng thø n. §­êng th¼ng nµy c¾t n -1 ®­êng th¼ng ®· vÏ t¹i n -1 giao ®iÓm. C¸c giao ®iÓm nµy chia ®­êng th¼ng thø n ra lµm n phÇn, mçi phÇn nh­ vËy sÏ chia mét phÇn nµo ®ã sinh bëi n -1 ®­êng th¼ng vÏ tr­íc ®ã ra lµm hai phÇn. Tõ ®ã suy ra, sau khi vÏ ®­êng th¼ng thø n sè phÇn t¨ng thªm lµ n . Tõ ®ã nhËn ®­îc c«ng thøc ®Ö qui S n = S n- 1 + n , n  2 (4) Toán rời rạc 4.1 Xây dựng công thức đệ qui l 1 l 2 l 3 l 4 G 1 G 2 G 3 phần 1 phần 2 phần 3 phần 4 Toán rời rạc 4.1 Xây dựng công thức đệ qui §Ó t×m c«ng thøc trùc tiÕp, ta céng c¸c hÖ thøc S k = S k -1 + k víi k = 2 , ..., n . S 1 = 2 S 2 = S 1 + 2 S 3 = S 2 + 3 ... S n -1 = S n -2 + ( n -1) S n = S n -1 + n S n = 2 + 2 + 3 + ...+( n- 1) + n = n ( n+ 1)/2 + 1 = ( n 2 +n+ 2)/2 Toán rời rạc 4.1 Xây dựng công thức đệ qui Ví dụ 3. Xây dựng công thức đệ qui cho f n là số chỉnh hợp lặp chập n từ hai phần tử 0, 1 (cũng chính là xâu nhị phân độ dài n ) không chứa hai số 0 liền nhau. Giải. Ta có f 1 = 2; f 2 = 3 Giả sử n > 2. Phân tập các chỉnh hợp cần đếm ra thành 2 tập: A – tập các chỉnh hợp cần đếm chứa 1 ở vị trí đầu tiên; B – tập các chỉnh hợp cần đếm chứa 0 ở vị trí đầu tiên; Rõ ràng A và B tạo thành phân hoạch của tập tất cả các chỉnh hợp cần đếm. Toán rời rạc 4.1 Xây dựng công thức đệ qui Do đó, theo nguyên lý cộng: f n = | A | + | B |. Ta có: Do mỗi chỉnh hợp trong A chứa 1 ở vị trí đầu tiên, nên n -1 phần tử còn lại sẽ tạo thành một chỉnh hợp cần đếm độ dài n -1, suy ra: | A | = f n -1 Do mỗi chỉnh hợp trong B chứa 0 ở vị trí đầu tiên, nên vị trí thứ hai của nó phải là 1 còn n -2 phần tử còn lại sẽ tạo thành một chỉnh hợp cần đếm độ dài n -2, suy ra: | B | = f n -2 Vậy, ta thu được công thức đệ qui f 1 = 2; f 2 = 3; f n = f n -1 + f n -2 , n > 2 (5) Toán rời rạc 4.1 Xây dựng công thức đệ qui Ví dụ 4. Xây dựng công thức đệ qui cho Q n là số lượng cách phủ lưới ô vuông kích thước 2  n bằng các quân bài domino. Giải. Ta có Q 1 = 1; Q 2 = 2 (xem hình vẽ) Giả sử n > 2. Phân tập các cách phủ cần đếm ra thành 2 tập: A – tập các cách phủ trong đó ô ở góc trên trái được phủ bởi quân bài nằm đứng; B – tập các cách phủ trong đó ô ở góc trên trái được phủ bởi quân bài nằm ngang. Rõ ràng A và B tạo thành phân hoạch của tập tất cả các cách phủ cần đếm. Toán rời rạc 4.1 Xây dựng công thức đệ qui Do đó, theo nguyên lý cộng: Q n = | A | + | B |. Ta có: | A | = Q n -1 | B | = Q n -2 Vậy, ta thu được công thức đệ qui Q 1 = 1; Q 2 = 2; Q n = Q n -1 + Q n -2 , n > 2 (6) ... ... ... ... A B Toán rời rạc 4.1 Xây dựng công thức đệ qui VÝ dô 5. (Bµi to¸n th¸p Hµ néi). Trß ch¬i th¸p Hµ néi ®­îc tr×nh bµy nh­ sau: “ Cã 3 cäc a, b, c. Trªn cäc a cã mét chång gåm n c¸i ®Üa ®­êng kÝnh gi¶m dÇn tõ d­íi lªn trªn. CÇn ph¶i chuyÓn chång ®Üa tõ cäc a sang cäc c tu©n thñ qui t¾c: mçi lÇn chØ chuyÓn 1 ®Üa vµ chØ ®­îc xÕp ®Üa cã ®­êng kÝnh nhá h¬n lªn trªn ®Üa cã ®­êng kÝnh lín h¬n. Trong qu¸ tr×nh chuyÓn ®­îc phÐp dïng cäc b lµm cäc trung gian”. Bµi to¸n ®Æt ra lµ: Tìm công thức đệ qui cho h n là sè lÇn di chuyÓn ®Üa Ýt nhÊt cÇn thùc hiÖn ®Ó hoàn thành nhiÖm vô ®Æt ra trong trß ch¬i th¸p Hµ néi. Toán rời rạc 4.1 Xây dựng công thức đệ qui Gi¶i: R â rµng: h 1 = 1. Gi¶ sö n ≥ 2. ViÖc di chuyÓn ®Üa gåm c¸c b­íc: (i) ChuyÓn n -1 ®Üa tõ cäc a ®Õn cäc b sö dông cäc c lµm trung gian. B­íc nµy ®­îc thùc hiÖn nhê gi¶ thiÕt quy n¹p. (ii) ChuyÓn 1 ®Üa (®Üa víi ®­êng kÝnh lín nhÊt) tõ cäc a ®Õn cäc c . (iii) ChuyÓn n -1 ®Üa tõ cäc b ®Õn cäc c (sö dông cäc a lµm trung gian). B­íc nµy ®­îc thùc hiÖn nhê gi¶ thiÕt quy n¹p. Toán rời rạc 4.1 Xây dựng công thức đệ qui B­íc (i) vµ (iii) ®ßi hái gi¶i bµi to¸n th¸p Hµ néi víi n -1 ®Üa, v× vËy sè lÇn di chuyÓn ®Üa Ýt nhÊt cÇn thùc hiÖn trong hai b­íc nµy lµ 2 h n -1 . Do ®ã ta cã c«ng thøc ®Ö qui sau: h n = 2 h n -1 + 1, n ≥ 2. Sö dông c«ng thøc ®Ö qui vµ ®iÒu kiÖn ®Çu võa t×m ®­îc ®èi víi h n ta cã thÓ dÔ dµng chøng minh b»ng qui n¹p lµ h n = 2 n – 1, n ≥ 1. Toán rời rạc 4.1 Xây dựng công thức đệ qui Ta có thể tìm được công thức trực tiếp cho h n bằng phương pháp thế: h n = 2 h n −1 + 1 = 2 (2 h n −2 + 1) + 1 = 2 2 h n −2 + 2 + 1 = 2 2 (2 h n −3 + 1) + 2 + 1 = 2 3 h n −3 + 2 2 + 2 + 1 = 2 n −1 h 1 + 2 n −2 + + 2 + 1 = 2 n −1 + 2 n −2 + + 2 + 1 (do h 1 = 1) = 2 n − 1 Toán rời rạc Tower of Hanoi: n=5 Cọc a Cọc c Cọc b Toán rời rạc 4. Công thức đệ qui 4.1. Xây dựng công thức đệ qui 4.2. Giải công thức đệ qui Toán rời rạc §4.2. Giải công thức đệ qui Ta hiểu việc giải công thức đệ qui là việc tìm công thức dưới dạng hiện cho số hạng tổng quát của dãy số thoả mãn công thức đệ qui đã cho. Chưa có phương pháp giải mọi công thức đệ qui. Sẽ xét phương pháp giải công thức đệ qui tuyến tính thuần nhất hệ số hằng (sẽ viết tắt là CTĐQ TTTNHSH) Toán rời rạc §4.2. Giải công thức đệ qui Định nghiã. Công thức đệ qui tuyến tính thuần nhất hệ số hằng bậc k là công thức đệ qui sau a n = c 1 a n −1 + + c k a n − k , trong đó c i là các hằng số, và c k ≠ 0 . Dãy số thoả mãn công thức đã cho là xác định duy nhất nếu đòi hỏi nó thoả mãn k điều kiện đầu a 0 = C 0 , a 1 = C 1 , ..., a k -1 = C k- 1 , trong đó C 0 , C 1 , ..., C k -1 là các hằng số. Ví dụ: 1) a n = 4 a n -1 +2 na n -3 2) h n = 2 h n- 1 + 1 3) b n = 5 b n -2 + 2( b n -3 ) 2 4) q n = 3 q n -6 + q n -8 Fall 2006 Toán rời rạc Toán rời rạc Giải CTĐQ TTTNHSH Ta sẽ tìm nghiệm dưới dạng a n = r n , trong đó r là hằng số. Dãy số { a n = r n } thoả mãn CTĐQ đã cho nếu r thoả mãn phương trình: r n = c 1 r n −1 + + c k r n − k , hay  r k − c 1 r k −1 − − c k = 0 Phương trình cuối cùng được gọi là phương trình đặc trưng, còn nghiệm của nó sẽ được gọi là nghiệm đặc trưng của CTĐQ TTTNHSH. Ta có thể sử dụng nghiệm đặc trưng để thu được công thức cho dãy số. (chuyển vế và × với r k − n ) Toán rời rạc Giải CTĐQ TTTNHSH §Þnh lý 1. Cho c 1 , c 2 lµ c¸c h»ng sè thùc. Gi¶ sö ph­¬ng tr×nh r 2 - c 1 r - c 2 = 0 cã hai nghiÖm ph©n biÖt r 1 vµ r 2 . Khi ®ã d·y sè { a n } lµ nghiÖm cña c«ng thøc ®Ö qui a n = c 1 a n- 1 + c 2 a n- 2 khi vµ chØ khi a n =  1 ( r 1 ) n +  2 ( r 2 ) n (5) n = 0, 1, ..., trong ®ã  1 ,  2 lµ c¸c h»ng sè. Toán rời rạc Giải CTĐQ TTTNHSH Chøng minh. Tr­íc hÕt ta chøng minh r»ng nÕu r 1 vµ r 2 lµ hai nghiÖm ph©n biÖt cña ph­¬ng tr×nh ®Æc tr­ng, vµ  1 ,  2 lµ c¸c h»ng sè, th× d·y sè { a n } x¸c ®Þnh bëi c«ng thøc (5) lµ nghiÖm cña c«ng thøc ®Ö qui ®· cho. Thùc vËy, do r 1 vµ r 2 lµ nghiÖm ®Æc tr­ng nªn r 1 2 = c 1 r 1 + c 2 , r 2 2 = c 1 r 2 + c 2 Toán rời rạc Giải CTĐQ TTTNHSH Tõ ®ã suy ra c 1 a n -1 + c 2 a n -2 = c 1 (  1 r 1 n -1 +  2 r 2 n -1 ) + c 2 (  1 r 1 n -2 +  2 r 2 n -2 ) =  1 r 1 n -2 ( c 1 r 1 + c 2 ) +  2 r 2 n -2 ( c 1 r 2 + c 2 ) =  1 r 1 n- 2 r 1 2 +  2 r 2 n- 2 r 2 2 =  1 r 1 n +  2 r 2 n = a n . Toán rời rạc Giải CTĐQ TTTNHSH B©y giê ta sÏ chØ ra r»ng nghiÖm { a n } cña c«ng thøc ®Ö qui a n = c 1 a n -1 + c 2 a n -2 lu«n cã d¹ng (5) víi  1 ,  2 nµo ®ã. Thùc vËy, gi¶ sö { a n } lµ nghiÖm cña c«ng thøc ®· cho víi ®iÒu kiÖn ®Çu a 0 = C 0 , a 1 = C 1 , (6) Ta chØ ra r»ng cã thÓ t×m ®­îc c¸c sè  1 ,  2 ®Ó cho (5) lµ nghiÖm cña hÖ thøc víi ®iÒu kiÖn ®Çu nµy. Toán rời rạc Giải CTĐQ TTTNHSH Ta cã a 0 = C 0 =  1 +  2 , a 1 = C 1 =  1 r 1 +  2 r 2 . HÖ ph­¬ng tr×nh tuyÕn tÝnh phô thuéc hai Èn  1 ,  2 nµy cã ®Þnh thøc lµ r 2 – r 1  0 (do r 1  r 2 ) cã nghiÖm duy nhÊt  1 = ( C 1 - C 0 r 2 )/( r 1 - r 2 ) ,  2 = ( C 0 r 1 - C 1 )/( r 1 - r 2 ) . Víi nh÷ng gi¸ trÞ cña  1 ,  2 võa t×m ®­îc, d·y { a n } x¸c ®Þnh theo (5) lµ nghiÖm cña hÖ thøc ®· cho víi ®iÒu kiÖn ®Çu (6). Do hÖ thøc ®· cho cïng víi ®iÒu kiÖn ®Çu (6) x¸c ®Þnh duy nhÊt mét d·y sè, nªn nghiÖm cña hÖ thøc ®­îc cho bëi c«ng thøc (5). §Þnh lý ®­îc chøng minh. Toán rời rạc VÝ dô D·y Fibonaci trong to¸n häc ®­îc ®Þnh nghÜa b»ng hÖ thøc truy håi: F n = F n -1 + F n- 2 , n  2, F 0 = 0, F 1 = 1. T×m c«ng thøc hiÖn cho F n . Gi¶i: Gi¶i ph­¬ng tr×nh ®Æc tr­ng: r 2 - r - 1 = 0 , ta thu ®­îc hai nghiÖm ®Æc tr­ng Leonardo Fibonacci1170-1250 Toán rời rạc VÝ dô Do ®ã c«ng thøc hiÖn cã d¹ng: F n =  1 .( r 1 ) n +  2 .( r 2 ) n trong ®ã  1 ,  2 lµ c¸c h»ng sè cÇn x¸c ®Þnh tõ c¸c gi¸ trÞ ban ®Çu F 0 , F 1 . Gi¶i hÖ PTTT nµy, ta cã: vµ tõ ®ã thu ®­îc C«ng thøc Muavre F 0 =  1 +  2 = 0 F 1 =  1 r 1 +  2 r 2 = 1 Toán rời rạc Great Pyramid at Gizeh Toán rời rạc b a Toán rời rạc Tỷ lệ giữa chiều cao và lưng Toán rời rạc Định nghĩa tỷ lệ vàng  (Euclid) Tỷ lệ thu được khi chia đoạn thẳng ra 2 phần không bằng nhau sao cho tỷ lệ giữa đoạn thẳng đã cho và đoạn con lớn hơn là bằng tỷ lệ giữa đoạn lớn hơn và đoạn nhỏ hơn. A B C Toán rời rạc Toán rời rạc Trường hợp nghiệm kép §Þnh lý 2. Cho c 1 , c 2 lµ c¸c h»ng sè thùc, c 2  0 . Gi¶ sö ph­¬ng tr×nh r 2 - c 1 r - c 2 = 0 cã nghiÖm kÐp r 0 . Khi ®ã d·y sè { a n } lµ nghiÖm cña c«ng thøc ®Ö qui a n = c 1 a n- 1 + c 2 a n -2 khi vµ chØ khi n = 0, 1, ..., trong ®ã  1 ,  2 lµ c¸c h»ng sè. Toán rời rạc Ví dụ T×m nghiÖm cho c«ng thøc ®Ö qui a n = 6 a n- 1 - 9 a n -2 víi ®iÒu kiÖn ®Çu a 0 = 1 vµ a 1 = 6. Gi¶i: PT§T r 2 - 6 r + 9 = 0 cã nghiÖm kÐp r = 3. Do ®ã nghiÖm cña hÖ thøc cã d¹ng: a n =  1 3 n +  2 n 3 n . §Ó t×m  1 ,  2 , sö dông ®iÒu kiÖn ®Çu ta cã a 0 = 1 =  1 , a 1 = 6 =  1 . 3 +  2 . 3 . Gi¶i hÖ nµy ta t×m ®­îc  1 = 1 vµ  2 = 1 . Tõ ®ã nghiÖm cña hÖ thøc ®· cho lµ: a n = 3 n + n 3 n . Toán rời rạc Trường hợp tổng quát §Þnh lý 3. Cho c 1 , c 2 , ..., c n lµ c¸c sè thùc. Gi¶ sö ph­¬ng tr×nh ®Æc tr­ng r k - c 1 r k -1 - c 2 r k- 2 - . . . - c k = 0 cã k nghiÖm ph©n biÖt r 1 , r 2 , ..., r k . Khi ®ã d·y sè { a n } lµ nghiÖm cña c«ng thøc a n = c 1 a n -1 + c 2 a n -2 +...+ c k a n-k , khi vµ chØ khi a n =  1 r 1 n +  2 r 2 n + . . . +  k r k n víi n = 0, 1, 2 ,..., trong ®ã  1 ,  2 , ...,  k lµ c¸c h»ng sè. Toán rời rạc Ví dụ T×m nghiÖm cña công thức đệ qui a n = 6 a n -1 - 11 a n- 2 + 6 a n -3 víi ®iÒu kiÖn ®Çu a 0 = 2 , a 1 = 5 , a 2 = 15. Gi¶i: Ph­¬ng tr×nh ®Æc tr­ng r 3 - 6 r 2 + 11 r - 6 = 0 cã 3 nghiÖm r 1 = 1, r 2 = 2, r 3 = 3. V× vËy, nghiÖm cã d¹ng a n =  1 1 n +  2 2 n +  3 3 n . Toán rời rạc Ví dụ Sö dông c¸c ®iÒu kiÖn ®Çu ta cã hÖ ph­¬ng tr×nh sau ®©y ®Ó x¸c ®Þnh c¸c h»ng sè  1 ,  2 ,  3 : a 0 = 2 =  1 +  2 +  3 a 1 = 5 =  1 +  2 .2 +  3 .3 a 2 = 15 =  1 +  2 . 4 +  3 .9 . Gi¶i hÖ ph­¬ng tr×nh trªn ta thu ®­îc  1 = 1 ,  2 = -1 vµ  3 = 2 . VËy nghiÖm cña c«ng thøc ®· cho lµ a n = 1 - 2 n + 2. 3 n . Toán rời rạc Trường hợp tổng quát Xét CTĐQ TTTNHSH bậc k : PTĐT của nó là: Định lý 4: Nếu PTĐT có t nghiệm r 1 ,, r t với bội tương ứng là m 1 ,, m t ( m 1 + + m t = k ). Khi đó: với n ≥0 , và α ij là các hằng số. Toán rời rạc Ví dụ Giải công thức đệ qui: c n = – 4 c n -1 + 3 c n -2 + 18 c n -3 , n  3, c 0 = 1; c 1 = 2; c 2 = 13. Ph­¬ng tr ì nh ®Æc tr­ng : r 3 + 4 r 2 – 3 r – 18 = ( r – 2)( r + 3) 2 = 0 VËy nghiÖm tæng qu¸t cña c«ng thøc: c n = a 10 2 n + ( a 20 + a 21 n )( – 3) n trong đó a 10 , a 20 , a 21 là các h»ng sè Toán rời rạc Ví dụ Các hằng số được xác định từ các điều kiện đầu: Rút gọn ta thu được hệ Giải hệ ta nhận được: Cuối cùng nghiệm của công thức là: Toán rời rạc Công thức đệ qui tuyến tính không thuần nhất hệ số hằng Công thức đệ qui tuyến tính không thuần nhất hệ số hằng (Linear no nhomogeneous Recurrence Relation with constant coefficients) có chứa số hạng không thuần nhất F ( n ) phụ thuộc vào n (và không phụ thuộc vào bất cứ a i nào) : a n = c 1 a n −1 + + c k a n − k + F ( n ) CTĐQ TTTNHSH tương ứng với công thức không thuần nhất Phần không thuần nhất Toán rời rạc Giải công thức không thuần nhất(CTKTN) Kết quả sau đây là cơ sở để giải công thức không thuần nhất: Nếu a n = p ( n ) là một nghiệm riêng của CTKTN: Khi đó mọi nghiệm của CTKTN đều có dạng: a n = p ( n ) + h ( n ) ,trong đó a n = h ( n ) là nghiệm tổng quát của CTĐQ TTTNHSH tương ứng Toán rời rạc Giải công thức không thuần nhất Từ đó ta có cách giải CTKTN sau đây: Tìm nghiệm tổng quát h ( n ) của công thức thuần nhất tương ứng. Tìm nghiệm riêng p ( n ) của CTKTN. Nghiệm của công thức không thuần nhất có dạng: a n = h ( n ) + p ( n ) . Xác định các hằng số từ hệ phương trình thu được bởi đòi hỏi a n thoả mãn các điều kiện đầu Toán rời rạc Giải công thức không thuần nhất Tìm nghiệm riêng bằng cách nào? Để tìm nghiệm riêng có thể căn cứ vào dạng của phần không thuần nhất F ( n ): Nếu F ( n ) = P ( n )  s n , trong đó P ( n ) là đa thức của n còn s là hằng số và không là nghiệm đặc trưng, thì hãy tìm nghiệm riêng có dạng giống như F ( n ). Nếu F ( n ) = P ( n )  s n , trong đó P ( n ) là đa thức của n còn s là nghiệm đặc trưng với bội là m , thì hãy tìm nghiệm riêng dưới dạng n m  Q ( n )  s n Toán rời rạc Ví dụ Giải công thức đệ qui a n =5 a n -1 - 6 a n -2 +7 n , n 2, a 0 = 0; a 1 = 1 PT đặc trưng r 2 – 5 r +6 = 0 có nghiệm r 1 = 3, r 2 = 2. Do đó nghiệm tổng quát của CTĐQ thuần nhất tương ứng là: h ( n ) = c 1 3 n + c 2 2 n . Do F ( n ) = 7 n và 7 không là nghiệm đặc trưng nên nghiệm riêng tìm dưới dạng p ( n ) = C. 7 n . Toán rời rạc Ví dụ Nghiệm riêng tìm dưới dạng p ( n ) = C. 7 n . Thay vào công thức ta có C 7 n = 5 C 7 n -1 – 6 C 7 n -2 + 7 n Từ đó tìm được C = 49/20. Vậy p ( n ) = (49/20)7 n . Toán rời rạc Ví dụ Nghiệm tổng quát có dạng: a n = p ( n ) + h ( n ) = (49/20)7 n + c 1 3 n + c 2 2 n . Các hằng số c 1 , c 2 xác định từ hệ phương trình: a 0 = c 1 + c 2 + 49/20 = 0 a 1 = 3 c 1 + 2 c 2 +(49/20).7 = 1 ... Toán rời rạc Ví dụ Giải công thức đệ qui a n = 2 a n -1 + 1, n  1; a 1 = 1. PTĐT r - 2 = 0 có nghiệm r =2 . Nghiệm tổng quát của CTĐQ thuần nhất tương ứng là: h ( n ) = c 1 2 n . Do F ( n ) = 1, nên nghiệm riêng tìm dưới dạng p ( n ) = C . Thay vào công thức đã cho ta được: C = 2 C +1. Từ đó tìm được C = -1. Vậy nghiệm riêng là p ( n ) = -1. Toán rời rạc Ví dụ Nghiệm tổng quát của CTĐQ không thuần nhất là a n = c 1 2 n – 1. Hệ số c 1 xác định từ điều kiện đầu: a 1 = c 1 2 -1 = 1 Do đó c 1 = 1. Vậy nghiệm của CTĐQ không thuần nhất là a n = 2 n -1, n  1. Toán rời rạc Ví dụ Giải công thức đệ qui a n = a n -1 + n , n  1; a 1 = 2. PTĐT r - 1 = 0 có nghiệm r =1 . Nghiệm tổng quát của CTĐQ thuần nhất tương ứng là: h ( n ) = c 1 1 n . Do F ( n ) = n 1 n , và 1 là nghiệm đặc trưng bội 1, nên nghiệm riêng tìm dưới dạng p ( n ) = ( C 2 + C 3 n ). n . Thay vào công thức đã cho ta được: ( C 2 + C 3 n ). n = [ C 2 + C 3 ( n- 1)].( n- 1) + n. Từ đó tìm được C 2 = ½ và C 3 = ½ . Vậy nghiệm riêng là p ( n ) = ( n +1) n /2. Toán rời rạc Ví dụ Nghiệm tổng quát của CTĐQ không thuần nhất là a n = c 1 + ( n +1) n /2 . Hệ số c 1 xác định từ điều kiện đầu: a 1 = c 1 + 1 = 2 Do đó c 1 = 1. Vậy nghiệm của CTĐQ không thuần nhất là a n = 1+ ( n +1) n /2 , n  1. Toán rời rạc Nhận xét Phương pháp giải công thức đệ qui TTTNHSH trình bày ở trên cho phép qui dẫn việc tìm nghệm của nó về việc tìm tất cả các nghiệm của đa thức bậc k . Việc tìm tất cả các nghiệm của một đa thức bậc tuỳ ý là vấn đề không đơn giản: Ta có công thức để tìm nghiệm của đa thức bậc k  4 . Nhưng không có công thức để tìm tất cả các nghiệm của đa thức bậc k  5 (Định lý Aben). Toán rời rạc Chương 1. BÀI TOÁN ĐẾM Nguyên lý cộng và nguyên lý nhân Các cấu hình tổ hợp cơ bản Nguyên lý bù trừ Công thức đệ qui Hàm sinh 5. Hàm sinh (Generating Function) Giả sử { h n | n = 0, 1, 2, ....} là một dãy số. Ta viết dãy này như là dãy vô hạn phần tử, tuy nhiên ta coi rằng nó bao gồm cả trường hợp dãy hữu hạn. Nếu h 0 , h 1 , ..., h m là dãy hữu hạn, thì ta sẽ biến nó thành dãy vô hạn bằng cách đặt h i = 0 , i > m . Định nghĩa. Hàm sinh g ( x ) của dãy số { h n | n = 0, 1, 2, ....} là chuỗi vô hạn g ( x ) = h 0 + h 1 x + h 2 x 2 + ... = . Như vậy hàm g ( x ) sinh ra dãy số đã cho như là dãy các hệ số của nó. Nếu dãy là hữu hạn thì sẽ tìm được m sao cho h i = 0 , i > m. Trong trường hợp này g ( x ) là một đa thức bậc m. Ví dụ V í dụ 1. Một trong những nguồn gốc dẫn đến định nghĩa hàm sinh chính là định lý về khai triển nhị thức: Hàm g ( x ) = (1 + x ) m sinh ra dãy các hệ số tổ hợp { h k = C ( m, k ) , k= 0, 1,..., m }. Bởi vì Ví dụ 2. Hàm g ( x ) = 1/(1 -x ) sinh ra dãy 1, 1, 1, ... Dễ dàng chứng minh điều đó bằng cách thực hiện phép chia: 1/(1- x ) = 1 + x + x 2 + ... Ví dụ 3 Ví dụ 3. Với k > 0, hàm g ( x ) = 1/(1 -x ) k sinh ra dãy { C ( n+k -1 , n ): n = 0, 1, 2, ...}. Như vậy hệ số thứ n sẽ là số khả năng chọn n vật từ k loại đồ vật. Chứng minh. Thực vậy, ta có 1/(1- x ) k = [ 1/(1- x )] k = (1 + x + x 2 + ... ) k . Nếu ta khai triển biểu thức này bằng cách thực hiện nhân phá ngoặc, thì số lần xuất hiện số hạng x n sẽ bằng số nghiệm nguyên không âm của phương trình t 1 + t 2 + ... + t k = n, mà như đã biết là bằng C ( n+k- 1 , n ). Ví dụ 3 Ví dụ này có thể gợi ý cho ta cách giải nhiều bài toán đếm. Chẳng hạn xét hàm sinh g ( x ) = (1 + x + x 2 + x 3 ) (1 + x + x 2 ) (1 + x + x 2 + x 3 + x 4 ) . Giả sử x a , x b , x c tương ứng là các số hạng lấy từ các thừa số thứ nhất, hai, ba của vế phải, điều đó có nghĩa là 0  a  3, 0  b  2, 0  c  4. Khi khai triển vế phải , các thừa số này sẽ cho ta số hạng x n , với n = a + b + c. Như vậy hệ số của x n trong g ( x ) sẽ là số nghiệm nguyên không âm của phương trình n=a + b + c thoả mãn 0  a  3, 0  b  2, 0  c  4 . Suy ra hệ số này cũng cho ta số cách chọn n bông hoa từ 3 bông cúc, 2 bông layơn và 4 bông hồng. Ví dụ 3 Tất nhiên việc sử dụng hàm sinh để giải bài toán đếm sẽ đòi hỏi nhiều tính toán khi thực hiện phép nhân các đa thức, và không thích hợp cho việc tính tay. Tuy nhiên, việc đó lại có thể thực hiện nhanh chóng trên máy tính, và vì thế hàm sinh sẽ là một công cụ hữu hiệu để giải nhiều bài toán đếm trên máy tính. Ta dẫn ra một số khai triển đại số rất hay sử dụng trong việc sử dụng hàm sinh: x k /(1- x ) = x k (1 + x + x 2 + ...) = x k + x k+ 1 + x k+ 2 + ... (1- x k+ 1 )/(1 -x ) = 1 + x + x 2 + ... + x k . 1/(1- x 2 ) = 1 + x 2 + x 4 + x 6 + ... x/ (1 -x 2 ) = x (1 + x 2 + x 4 + x 6 + ...) = x + x 3 + x 5 + x 7 + ... Ví dụ 4 V í dụ 4. Có bao nhiêu cách chọn ra n quả từ 4 loại quả: táo, chuối, cam và đào (mỗi loại đều có số lượng ít ra là n ) mà trong đó có một số chẵn quả táo, số lẻ quả chuối, không quá 4 quả cam và ít ra 2 quả đào? Giải. Hàm sinh để giải bài toán này là g ( x ) = (1+ x 2 +x 4 +x 6 +... ) ( x+x 3 +x 5 +x 7 +... ) (1 +x+x 2 +x 3 +x 4 ) ( x 2 +x 3 +x 4 +... ). Trong công thức trên có 4 thừa số để đếm số quả táo (các số mũ chẵn), chuối (số mũ lẻ), cam (chỉ có đến số mũ 4) và đào (số mũ bắt đầu từ 2). Từ đó g ( x ) = [1/(1- x 2 )] [ x /(1- x 2 )] [(1- x 5 )/(1- x )] [ x 2 /(1- x )] = [ x 3 (1 -x 5 )]/[(1- x 2 ) 2 (1- x ) 2 ]. Câu trả lời là: Số cách cần đếm là hệ số thứ n trong khai triển g ( x ) dưới dạng chuỗi luỹ thừa. Tuy là chúng ta không có câu trả lời bằng số, nhưng sử dụng hàm xây dựng được ta có thể lập trình trên máy tính để đưa ra bảng đáp số cho các giá trị của n mong muốn. Ví dụ 5 V í dụ 5 . Tìm hàm sinh cho h n là số cách chọn ra n quả từ 4 loại quả: táo, chuối, cam và đào (mỗi loại đều có số lượng ít ra là n ) mà trong đó có một số chẵn quả táo, số lượng chuối chia hết cho 5, không quá 4 quả cam và không quá 1 quả đào? Giải. Hàm sinh có dạng g ( x )=(1 +x 2 +x 4 +x 6 +.. .)(1 +x 5 +x 10 +x 15 +... )(1 +x+x 2 +x 3 +x 4 )(1 +x ) = [1/(1- x 2 )] [1 / (1- x 5 )] [(1 -x 5 )/(1 -x )] (1+ x ) = [1/((1- x )(1 +x )] [1/(1 -x )] (1 +x ) = 1/(1- x ) 2 Từ đó ta có thể tìm công thức hiện cho lời giải, bởi vì , theo ví dụ 3, ta có . Vậy h n = n + 1 . Hàm sinh và công thức đệ qui H àm sinh có thể sử dụng để tìm công thức dưới dạng hiện cho số hạng tổng quát của dãy số { h n , n =0,1,2,...} xác định bởi công thức đệ qui. Nội dung của phương pháp có thể trình bày như sau : i) Xây dựng hàm sinh g ( x ) của dãy số này theo công thức g ( x ) = h 0 + h 1 x + h 2 x 2 + ... = ii) T ìm công thức giải tích cho hàm sinh g ( x ). ( Sử dụng các tính chất của dãy số suy từ công thức đệ qui xác định nó) . iii) Theo công thức tìm được , tìm k hai triển hàm g ( x ) dưới dạng chuỗi luỹ thừa (chuỗi Maclaurin). iv) So sánh hệ số ở các số hạng với cùng số mũ của x ta tìm được công thức cho h n . Phép toán với hàm sinh Trước hết ta đưa ra một số phép toán đối với hàm sinh. Giả sử là hai hàm sinh còn  là số thực, khi đó Tích Côsi của hai hàm sinh g ( x ) và f ( x ) : trong đó c k = a 0 b k + a 1 b k- 1 + ... + a k b 0 = . Chuỗi Maclaurin Từ giải tích ta biết rằng nếu chuỗi hội tụ ở lân cận điểm 0 thì tổng g ( x ) luôn là hàm giải tích trong lân cận này và h k = g ( k ) (0) /k ! , k = 0, 1, ... Khi đó chuỗi c hính là khai triển Macl aurin của hàm g ( x ). Như vậy có một tương ứng 1-1 giữa một hàm giải tích và một chuỗi hội tụ trong lân cận 0. Công thức hay dùng Trong việc áp dụng hàm sinh ta thường sử dụng công thức sau: mà trường hợp riêng của nó là 1/(1 - rx ) = 1 + rx + r 2 x 2 + r 3 x 3 + .... Dãy số Fibonaci Dãy số Fibonaci. Dãy số Fibonaci là dãy số được xác định bởi công thức đệ qui f n = f n- 1 + f n- 2 , n  2 , f 0 = 0 , f 1 = 1 . Ta sẽ tìm công thức cho số hạng tổng quát của dãy số nhờ phương pháp hàm sinh. Xét hàm sinh . Ta có Dãy số Fibonaci Từ đó suy ra Ta có (1- x - x 2 ) = (1 -  x ) (1 -  x ), với Viết lại F ( x ) dưới dạng Dãy số Fibonaci Từ đó tìm được Do đó Suy ra 6. Một số dãy số đặc biệt Dãy số Stirling Dãy số Bell Dãy số Catalan Nhắc lại: Số lượng ánh xạ Cho các tập hữu hạn A = { a 1 ,, a m } và B = { b 1 ,, b n }. Hỏi có bao nhiêu ánh xạ f : A  B ? Như ta đã chứng minh: Tổng số ánh xạ có thể: | B | | A | = n m . Số lượng đơn ánh: P ( n,m ) = n ∙( n –1)∙∙∙( n–m +1) = n !/( n–m )!. Số lượng song ánh là P ( n,n ) = n ! nếu | A | = | B | = n . Số lượng toàn ánh: với m ≥ n : Số Stirling loại 2 Số lượng toàn ánh từ tập A = { a 1 ,, a m } vào tập B = { b 1 ,, b n } liên quan đến một con số tổ hợp nổi tiếng đó là số Stirling loại 2 (Stirling Numbers of the 2 nd Kind). Định nghĩa. Số Stirling loại 2 , ký hiệu bởi S 2 ( m,n ), là số cách phân hoạch tập m phần tử thành n tập con ( m  n ). Ví dụ: Ta đếm số cách phân hoạch tập {1,2,3,4} ra thành 2 tập con. Ta có thể kể ra tất cả các cách phân hoạch như vậy: {{1,2,3},{4}}, {{1,2,4},{3}} , {{1,3,4},{2}}, {{2,3,4},{1}} , {{1,2},{3,4}}, {{1,3},{2,4}} ,{{1,4},{2,3}}. Vậy S 2 (4,2)=7. Trong nhiều tài liệu, số Stirling còn được ký hiệu bởi James Stirling 1692 – 1770 Scotland Số Stirling loại 2 Ta sẽ xây dựng công thức đệ qui để đếm số S 2 ( m,n ). Ta có: S 2 (0,0)=1. Nếu m > 0, thì S 2 ( m ,0) = 0, S 2 ( m ,1)=1, và S 2 ( m,m )=1. Định lý. Với m, n > 1, S 2 ( m , n ) = S 2 ( m –1, n –1) + n ∙ S 2 ( m –1, n ). Chứng minh. Ta cần đếm số cách phân hoạch tập m phần tử X = { x 1 , x 2 , , x m } ra thành n tập con. Công thức đệ qui Tập các cách phân hoạch như vậy có thể phân hoạch thành 2 tập: A = Tập các cách phân hoạch X ra thành n tập con trong đó có một tập con là { x m }; B = Tập các cách phân hoạch X ra thành n tập con trong đó không có tập con nào là { x m } (tức là x m không đứng riêng một mình!). Ta có: | A | = S 2 ( m –1, n –1) . | B | = n ∙ S 2 ( m –1, n ), bởi vì có S 2 ( m –1, n ) cách phân hoạch X \ { x m } ra thành n tập con và có n cách xếp x m vào một trong số các tập con này. Từ đó S 2 ( m,n )= | A | + | B | = S 2 ( m –1, n –1) + n ∙ S 2 ( m –1, n ). Định lý được chứng minh. Công thức tính số Stirling Từ công thức đệ qui có thể chứng minh bằng qui nạp toán học công thức sau đây: Nói chung để tính S 2 ( m , n ) người ta thường dùng công thức đệ qui, chứ không sử dụng công thức này. Điều này được giải thích tương tự như để tính hệ số tổ hợp người ta thường dùng tam giác Pascal. Liên hệ giữa số lượng toàn ánh và số Stirling Ta xét mối liên hệ giữa số Stirling loại 2 với số lượng toàn ánh từ tập m phần tử A vào tập n phần tử B (ký hiệu là S' ( m,n ) ). Giả sử cho f là toàn ánh từ A vào B . Đặt A i = { a  A| f ( a ) = b i }, i = 1, 2, ..., n, Rõ ràng các tập A 1 , A 2 , ..., A n tạo thành một phân hoạch của tập A . Ngược lại, cho một phân hoạch của tập A ra thành n tập con A 1 , A 2 , ..., A n và  (1) ,  (2) , ..., ( n ) là hoán vị của 1, 2, ..., n, thì ta có thể xây dựng được toàn ánh f từ A vào B theo qui tắc f ( a ) = b  ( i ) , a  A  ( i ) , i = 1,2, ..., n, Như vậy mỗi phân hoạch cho ta n ! toàn ánh. Vì thế, số lượng toàn ánh từ tập m phần tử vào tập n phần tử là bằng n ! nhân với số cách phân hoạch tập m phần tử ra thành n tập con, nghĩa là bằng n ! S 2 ( m,n ) Liên hệ giữa số lượng toàn ánh và số Stirling Như vậy ta có đẳng thức cho mối liên hệ giữa số toàn ánh từ tập m phần tử vào tập n phần tử S '( m,n ) và số Stirling loại 2 sau đây: S '( m,n ) = n ! S 2 ( m,n ) . Do đó từ công thức đã chứng minh ở mục trước Bảng giá trị của số Stirling loại 2 Số Bell Định nghĩa. Số Bell (Bell numbers) là số cách phân hoạch tập n phần tử ra thành các tập con khác rỗng. Các phần tử đầu tiên của dãy số này là 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, ... Ví dụ: Tập {1, 2, 3} có các cách phân hoạch sau đây: {{1}, {2}, {3}} , {{1, 2}, {3}}, {{1, 3}, {2}} , {{1}, {2, 3}}, {{1, 2, 3}}. Số Bell thứ n được tính bởi công thức trong đó S 2 ( n,k ) là số Stirling loại 2. Eric Temple Bell Born: 1883, ScotlandDied: 1960, USA Số Bell Tập {1, 2, 3} có 5 cách phân hoạch: Tập {1, 2, 3, 4, 5} có 52 cách phân hoạch: Số Catalan Định nghĩa. Số Catalan thứ n , ký hiệu là C n , là số cách đặt dấu ngoặc để tổ chức thực hiện việc tính tích của n +1 thừa số: P 0.. n = x 0 x 1 x 2 ... x n . Ví dụ: Có 2 cách để tính P 0..2 : x 0 * x 1 * x 2 = ( x 0 *( x 1 * x 2 )) = (( x 0 * x 1 )* x 2 ) Có 5 cách để tính P 0..3 : 1*2*3*4 = (1*(2*(3*4))) = (1*((2*3)*4)) = ((1*2)*(3*4)) = ((1*(2*3))* 4) = (((1*2)*3)*4) Có 14 cách để tính P 0..4 : 1*2*3*4*5 = (1 (2 (3 (4 5)))) = (1 (2 ((3 4) 5))) = (1 ((2 3) (4 5))) = (1 ((2 (3 4)) 5)) = (1 (((2 3) 4) 5)) = ((1 2) (3 (4 5))) = ((1 2) ((3 4) 5)) = ((1 (2 3)) (4 5)) = ((1 (2 (3 4))) 5) = ((1 ((2 3) 4)) 5) = (((1 2) 3) (4 5)) = (((1 2) (3 4)) 5) = (((1 (2 3)) 4) 5) = ((((1 2) 3) 4) 5) Số Catalan Ta xây dựng công thức đệ qui để tính C n . Rõ ràng C 0 = 1 và C 1 = 1. Giả sử n > 1. Sau khi đặt dấu ngoặc phân tách đầu tiên, tích x 0 x 1 x 2 ... x n được chia làm hai tích con. Ví dụ: P 0..4 = P 0..2 P 3..4 = ( x 0 x 1 x 2 ) ( x 3 x 4 ) Giả sử dấu ngoặc phân tách đầu tiên được đặt sau thừa số x k : P 0.. n = P 0.. k P k +1.. n = ( x 0 x 1 x 2 ... x k ) ( x k +1 x k +2 ... x n ) Khi đó ta có C k cách tính P 0.. k , C n-k- 1 cách tính P k +1.. n , và do đó việc tính P 0 ..n có thể thực hiện bởi C k C n-k -1 cách . Số Catalan Do dấu ngoặc phân tách đầu tiên có thể đặt vào sau bất cứ thừa số nào trong các thừa số x 0 , x 1 , ..., x n -1 , suy ra tổng số cách tính P 0.. n là: C n = C 0 C n -1 + C 1 C n -2 + ... + C n -1 C 0 . Như vậy ta thu được công thức đệ qui: Sử dụng công thức này có thể chứng minh công thức sau: Số Catalan Một số phần tử đầu tiên của dãy số Catalan: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, Số Catalan là lời giải của rất nhiều bài toán tổ hợp. Ta sẽ kể ra dưới đây một số bài toán như vậy. E. C. Catalan 1814 -1894 Belgium Tam giác phân đa giác C n là số cách chia đa giác n +2 đỉnh ra thành các tam giác nhờ vẽ các đường chéo không cắt nhau ở trong đa giác: C 3 = 5 C 2 = 2 C 4 = 14 C 5 = 42 Đường đi trên lưới ô vuông C n là số lượng đường đi đơn điệu (tức là đường đi xuất phát từ vị trí góc dưới-phải kết thúc ở góc trên-trái và chỉ đi sang trái hoặc lên trên) độ dài 2 n trên lưới ô vuông kích thước n  n không vượt lên trên đường chéo. C 5 = 42 C 4 = 14 C 2 = 2 C 3 = 5 Cây nhị phân đầy đủ C n là số lượng cây nhị phân đầy đủ không đẳng cấu có n đỉnh trong. Cây nhị phân có gốc được gọi là đầy đủ nếu mỗi đỉnh của nó hoặc là không có con hoặc có đúng hai con. Đỉnh trong (internal vertice) là đỉnh có con. n = 2 n = 3 n = 4 n = 1 C n là số cây nhị phân đầy đủ với n  + 1 lá. Có C 3 = 5 cây nhị phân đầy đủ với 4 lá: Cây nhị phân đầy đủ với n lá n 2 3 4 Toán rời rạc Ask questions! Toán rời rạc a n =5 a n -1 - 6 a n -2 +7 n , n 2, Toán rời rạc Toán rời rạc Toán rời rạc LiNoReCoCo Example Find all solutions to a n = 3 a n −1 +2 n . Which solution has a 1 = 3 ? Notice this is a 1-Li No ReCoCo. Its associated 1-Li Ho ReCoCo is a n = 3 a n −1 , whose solutions are all of the form a n = α 3 n . Thus the solutions to the original problem are all of the form  a n = p ( n ) + α 3 n . So, all we need to do is find one p ( n ) that works. Toán rời rạc Trial Solutions If the extra terms F ( n ) are a degree- t polynomial in n , you should try a general degree- t polynomial as the particular solution p ( n ) . This case: F ( n ) is linear so try a n = cn + d . cn+d = 3( c ( n −1)+ d ) + 2 n (for all n ) (2 c +2) n + (2 d −3 c ) = 0 (collect terms)  So c = −1 and d = −3/2 . So a n = − n − 3/2 is a solution. Check: a n ≥1 = {−5/2, −7/2, −9/2, } Toán rời rạc Finding a Desired Solution From the previous, we know that all general solutions to our example are of the form: a n = − n − 3/2 + α 3 n . Solve this for α for the given case, a 1 = 3 : 3 = −1 − 3/2 + α 3 1 α = 11/6 The answer is a n = − n − 3/2 + (11/6)3 n . Toán rời rạc Double Check Your Answer! Check the base case, a 1 =3: a n = − n − 3/2 + (11/6)3 n a 1 = −1 − 3/2 + (11/6)3 1  = −2/2 − 3/2 + 11/2 = −5/2 + 11/2 = 6/2 = 3 Check the recurrence, a n = 3 a n −1 +2 n : − n − 3/2 + (11/6)3 n = 3[−( n −1) − 3/2 + (11/6)3 n −1 ]+2 n= 3[− n − 1/2 + (11/6)3 n −1 ] + 2 n = −3 n − 3/2 + (11/6)3 n + 2 n = − n − 3/2 + (11/6)3 n ■ Toán rời rạc Ask questions! Fall 2006 Toán rời rạc Fall 2006 Toán rời rạc Fall 2006 Toán rời rạc Fall 2006 Toán rời rạc Fall 2006 Toán rời rạc Ask questions! Fall 2006 Toán rời rạc Fall 2006 Toán rời rạc