第7章 遞推關(guān)系和生成函數(shù).ppt

第7章遞推關(guān)系和生成函數(shù) 7 1一些數(shù)列 算術(shù)序列 等差數(shù)列 幾何序列 等比數(shù)列 例1 確定平面一般位置上的n個(gè)互相交疊的圓所形成的區(qū)域數(shù) 例2 Fibonacci問題 Fibonacci數(shù)列是遞推關(guān)系的又一典型問題 數(shù)列的本身有著許多應(yīng)用 1 問題的提出 假定初生的一對(duì)雌雄兔子 從出生的第2個(gè)月之后每個(gè)月都可以生出另外一對(duì)雌雄兔 如果第1個(gè)月只有一對(duì)初生的雌雄兔子 問n個(gè)月之后共有多少對(duì)兔子 1月 2月 3月 4月 5月 6月 2 求遞推關(guān)系 設(shè)滿n個(gè)月時(shí)兔子對(duì)數(shù)為Fn 則第n 1個(gè)月留下的兔子數(shù)目為Fn 1對(duì) 當(dāng)月新生兔數(shù)目為Fn 2對(duì) 即第n 2個(gè)月的所有兔子到第n個(gè)月都有繁殖能力 Fn Fn 1 Fn 2 F1 F2 1 7 1 由遞推關(guān)系 7 1 式可依次得到F3 F1 F2 2 F4 F2 F3 3 F5 F3 F4 3 2 5 前幾項(xiàng)為 0 1 1 2 3 5 8 13 21 34 55 89 144 233 3 Fibonacci數(shù)列的性質(zhì)部分和Sn f0 f1 f2 fn fn 2 1Fibonacci數(shù)列是偶數(shù)當(dāng)且僅當(dāng)n能被3整除Fibonacci數(shù)列滿足公式 例3 令g0 g1 g2 gn 是滿足下面給出的Fibonacci數(shù)列遞推關(guān)系和初始條件 gn gn 1 gn 2 n 2 g0 2 g1 1例4 確定2Xn棋盤用多米諾骨牌完美覆蓋的方法數(shù)hn 例5 確定用單牌和多米諾骨牌對(duì)1Xn棋盤完美覆蓋的方法數(shù)bn 定理7 1 2沿Pascal三角形左下到右上對(duì)角線上的二項(xiàng)式系數(shù)的和是Fibonacci數(shù) 7 2線性齊次遞推關(guān)系 數(shù)列h0 h1 h2 hn hn a1hn 1 a2hn 2 akhn k bn n k 錯(cuò)排數(shù)列Dn n 1 Dn 2 Dn 1 n 2 Dn nDn 1 1 n n 1 Fibonacci數(shù)列Fn Fn 1 Fn 2 n 2 階乘序列hn nhn 1 n 1 幾何序列hn qhn 1 n 1 hn a1hn 1 a2hn 2 akhn k n k 其中a1 a2 ak是常系數(shù) 稱為常系數(shù)線性齊次遞推關(guān)系 定理7 2 1令q為一非零數(shù) 則hn qn是hn a1hn 1 a2hn 2 akhn k 0 ak 0 n k 的解 當(dāng)且僅當(dāng)q是多項(xiàng)式方程xk a1xk 1 a2xk 2 ak 0的一個(gè)根 如果多項(xiàng)式方程有k個(gè)不同的根q1 q2 qk 則hn c1q1n c2q2n ckqkn 例6 求滿足初始值h0 1 h1 2 h2 0的遞推關(guān)系hn 2hn 1 hn 2 2hn 3 n 3 的解例7 只由三個(gè)字母a b c組成的長(zhǎng)度為n的一些單詞將在通信信道上傳輸 滿足條件 傳輸中不得有兩個(gè)a連續(xù)出現(xiàn)在任一單詞中 確定通信信道允許傳輸?shù)膯卧~個(gè)數(shù) 例8 遞推關(guān)系hn 4hn 1 4hn 2 n 2 的解定理7 2 2令q1 q2 qt為hn a1hn 1 a2hn 2 akhn k ak 0 n k 的特征方程的互異的根 此時(shí) 如果qi是si重根 則對(duì)qi部分一般解為Hn i c1 c2n csinsi 1 qin 7 3非齊次遞推關(guān)系 例9 Hanoi塔問題 n個(gè)圓盤依其半徑大小 從下而上套在柱A上 如圖3 1所示 每次只允許取一個(gè)轉(zhuǎn)移到柱B或C上 而且不允許大盤放在小盤上方 若要求把A上的n個(gè)盤轉(zhuǎn)移到C柱上 請(qǐng)?jiān)O(shè)計(jì)一種方法 并估計(jì)要移動(dòng)幾個(gè)盤次 現(xiàn)在只有A B C三根柱子可供使用 4 1 3 2 Hanoi塔是個(gè)經(jīng)典問題 對(duì)于這個(gè)問題 我們先要設(shè)計(jì)算法 進(jìn)而估計(jì)算法的計(jì)算復(fù)雜性 這里就是移動(dòng)的總次數(shù) 1 算法設(shè)計(jì) n 2時(shí) 圓盤1從A套在B上 把圓盤2從A轉(zhuǎn)移到C上 把圓盤1從B上轉(zhuǎn)移到C上 完畢 n 3時(shí) 把圓盤1從A轉(zhuǎn)移到C上 把圓盤2從A轉(zhuǎn)移到B上 把圓盤1從C上轉(zhuǎn)移到B上 把圓盤3從A套在C上 把圓盤1從B再轉(zhuǎn)移到A上 把圓盤2從B轉(zhuǎn)移到C上 把圓盤1從A套在C上 完畢 看看n 3的演示過程 A B C 假定n 1個(gè)盤子的轉(zhuǎn)移算法已經(jīng)確定 對(duì)n個(gè)圓盤問題 先把上面的圓盤1 2 n 1轉(zhuǎn)移到B上 再把最后一個(gè)盤子轉(zhuǎn)移到C上 然后把B上的n 1個(gè)圓盤轉(zhuǎn)移到柱C上 轉(zhuǎn)移完畢 這運(yùn)用的是遞歸算法n 2時(shí)給出了算法 n 3時(shí)先利用n 2時(shí)的算法把圓盤1 2移B上 再把圓盤3轉(zhuǎn)移到柱C上 再利用n 2時(shí)的算法把B上兩個(gè)圓盤轉(zhuǎn)移到柱C上 n 4 5 以此類推 2 算法分析 令hn表示n個(gè)圓盤所需要的轉(zhuǎn)移次數(shù) 根據(jù)算法先把前面n 1個(gè)盤子轉(zhuǎn)移到B上 然后把第n個(gè)盤子轉(zhuǎn)移到C上 最后再一次將B上的n 1個(gè)盤子轉(zhuǎn)到C上 算法可實(shí)現(xiàn)性可用歸納法得到 因n 2時(shí)對(duì) 假定n 1對(duì) 那么n自然也對(duì) 關(guān)于轉(zhuǎn)移次數(shù)容易得到一個(gè)遞歸關(guān)系 hn 2hn 1 1 h1 1 例10 解hn 3hn 1 4n n 1 h0 2步驟總結(jié)求齊次關(guān)系的一般解求非齊次關(guān)系的一個(gè)特解將一般解和特解聯(lián)合 按初始條件求系數(shù)困難在于特解的求解 例11 hn 2hn 1 3n n 1 h0 2例12 hn 3hn 1 3n n 1 h0 2例13 hn hn 1 n3 n 1 h0 0 7 4生成函數(shù) 母函數(shù) 母函數(shù)就象一根曬衣繩 我們把需要得到的一列數(shù)就掛在它上面 假定我們的問題的解是一列數(shù) a0 a1 a2 an 我們想知道這個(gè)數(shù)列是什么 我們期望得到怎樣的答案 當(dāng)然 最好的答案就是關(guān)于an的一個(gè)簡(jiǎn)單的公式 比如諸如an n2 3之類的表達(dá)式 即 通項(xiàng)公式 但是 如果一個(gè)未知數(shù)列沒有簡(jiǎn)單公式 或者即便存在 但是很復(fù)雜 很不容易得到 我們也不知道 該怎么辦 如果我們還希望研究這個(gè)數(shù)列 討論它的性質(zhì) 該如何下手 舉一個(gè)極端的例子 假定這個(gè)數(shù)列是2 3 5 7 11 13 17 19 23 此處an是第n個(gè)素?cái)?shù) 這樣的情況 期望任何簡(jiǎn)單的公式都是不合理的 母函數(shù)把數(shù)列的所有成員用一種非常巧妙的方法聯(lián)系在一起 雖然這樣做并不一定能得到數(shù)列的簡(jiǎn)單公式 可是也許能夠給出一個(gè)冪級(jí)數(shù)和的簡(jiǎn)單公式 展開這個(gè)和函數(shù) 所得到的冪級(jí)數(shù)的系數(shù)就是我們所要找的數(shù)列 比如后面我們將會(huì)學(xué)習(xí)到的Fibonacci數(shù)列 它滿足一個(gè)遞歸關(guān)系Fn 1 Fn Fn 1 n 2 F1 F2 1 1 母函數(shù)概念設(shè)有a b c三個(gè)不同的球 從中選取一個(gè) 或選a 或選b 或選c 把這些可能的選取形象地表示為a b c 類似地 從中選取二個(gè) 或選a和b 或選a和c 或選b和c 可形象地表示為ab ac bc 同樣 從中選取三個(gè) 只有一種方法 也可形象地表示為abc 從多項(xiàng)式 1 ax 1 bx 1 cx 7 2 1 a b c x ab ac bc x2 abc x3中發(fā)現(xiàn) 所有這些可能的選取方式正好是x冪的系數(shù) 其中xi的系數(shù)是從三個(gè)球中選取i個(gè)的方法之形象表示 因子 1 ax 形象地指出 對(duì)球a 有兩種選取方法 不選a 或選a 因子 1 ax 中的1表示不選a 而x的系數(shù)a表示選a 既然在上述多項(xiàng)式中 xi的系數(shù)表明選取i個(gè)球的方法 那么 1 ax 1 bx 1 cx 所表明的是 對(duì)a b c三球 選取的方法是 選a或不選a 和 選b或不選b 以及 選c或不選c 多項(xiàng)式中x的冪次表示選取球的個(gè)數(shù) 而其相應(yīng)系數(shù)表示一切可能的選取方法 如果我們只關(guān)心不同組合方案的數(shù)目 不關(guān)心各種方案的羅列 可以在 7 2 式中令a b c 1 則得到 1 x 3 C 3 0 C 3 1 x C 3 2 x2 C 3 3 x3 1 3x 3x2 x3 7 3 總方案數(shù)N C 3 0 C 3 1 C 3 2 C 3 3 1 3 3 1 8 7 3 就是一個(gè)關(guān)于形式變量x的冪函數(shù) 這個(gè)冪函數(shù)中不同冪次的系數(shù)都是一個(gè)組合數(shù) 這可以推廣到任意n個(gè)不同球所有可能組合的方案數(shù)情況 這其實(shí)就是我們大家熟悉的二項(xiàng)式系數(shù) 不過現(xiàn)在我們是用形式級(jí)數(shù)的觀點(diǎn)來看問題 利用這種形式級(jí)數(shù)不僅僅是一種不同的表達(dá)形式 還非常有用 2 母函數(shù)定義定義7 1利用給定序列a0 a1 a2 所構(gòu)造的函數(shù)F x a0 a1x a2x2 稱為序列a0 a1 a2 的母函數(shù) 母函數(shù)定義中的級(jí)數(shù)是形式冪級(jí)數(shù) 不必關(guān)心收斂性 x只是一個(gè)形式變量 有限序列a0 a1 an也可以定義它的母函數(shù) 后面添加0 3 母函數(shù)的運(yùn)算設(shè)序列 ai 的母函數(shù)A x aixi bi 的母函數(shù)為B x bixi 運(yùn)算定義如下 1 相等 A x B x ai bi ai bi i 1 2 2 相加 A x B x ai bi xi 3 相減 A x B x ai bi xi 4 數(shù)乘 cA x cai xi 5 相乘 A x B x cixi 其中c0 a0b0 c1 a0b1 a1b0 c2 a0b2 a1b1 a2b0 cr a0br a1br 1 arb0 6 逆 如果A x B x 1 則稱B x 為A x 的逆 記為B x A 1 x 1 A x 顯然兩者互為逆 例14設(shè)F x 1 x x2 G x 1 x 由定義可以得到F x G x 1 因此1 G x G 1 x F x 即 這同微積分中函數(shù)1 1 x 的冪級(jí)數(shù)展開式是完全一致的 例15設(shè) 則 F x G x 1 3x 2x2 x 這說明 這與把它們看成普通函數(shù)的運(yùn)算是一致的 例16 令k是一個(gè)整數(shù) 并令序列h0 h1 h2 hn 使hn等于e1 e2 ek n的非負(fù)整數(shù)解的個(gè)數(shù) 例17 確定蘋果 香蕉 橘子和梨的n組合的個(gè)數(shù) 其中在每個(gè)n組合中蘋果的個(gè)數(shù)是偶數(shù) 香蕉的個(gè)數(shù)是奇數(shù) 橘子的個(gè)數(shù)在0和4之間 而且至少要有一個(gè)梨 例18 確定可以由蘋果 香蕉 橘子和梨袋裝水果的袋數(shù)hn 其中在每個(gè)袋子中蘋果數(shù)是偶數(shù) 香蕉數(shù)是5的倍數(shù) 橘子數(shù)最多是4個(gè) 梨的個(gè)數(shù)為0或1 例19 確定方程e1 e2 ek n的非負(fù)奇整數(shù)解e1 e2 ek的個(gè)數(shù)hn的母函數(shù) 例20 令hn表示方程3e1 4e2 2e3 5e4 n的非負(fù)整數(shù)解的個(gè)數(shù) 求h0 h1 h2 hn 的母函數(shù)g x 例21 有無限多現(xiàn)成的一分 五分 一角 兩角五分和五角的硬幣 確定用這些硬幣湊成n分錢方法數(shù)hn的母函數(shù)g x 7 5母函數(shù)與遞歸 例22 Hanoi塔問題 hn 2hn 1 1 h1 1 7 4 令H x h1x h2x2 h3x3 H x 是序列h1 h2 h3 的母函數(shù) 給出了序列 就可確定對(duì)應(yīng)的母函數(shù) 反過來也一樣 求得了母函數(shù) 對(duì)應(yīng)得序列也就可得而知 當(dāng)然 利用遞推關(guān)系 7 4 也可迭代求得h2 h3 但現(xiàn)在我們一要尋找明確的公式 二要顯示母函數(shù)的作用 令H x h1x h2x2 h3x3 hnxn 為生成函數(shù) 有以下方程 H x h1x h2x2 h3x3 hnxn 2xH x 2h1x2 2h2x3 2h3x4 2hnxn 1 相加 1 2x H x h1x h2 2h1 x2 h3 2h2 x3 hn 2hn 1 xn x 1 x x2 x3 x 1 x H x x 1 x 1 2x 7 5 這就是轉(zhuǎn)移次數(shù)數(shù)列的母函數(shù) 但是我們希望得到顯式表達(dá)式 這不難做到 可以從母函數(shù)的冪級(jí)數(shù)展開式中求得數(shù)列h1 h2 h3 我們下面所運(yùn)用的方法是處理這種問題的一個(gè)常規(guī)的方法 初看起來可能感覺不太適應(yīng) 用多了就習(xí)以為常了 這就是所謂的部分分?jǐn)?shù)的算法 A B 2A B x x 解得A 1 B 1 其實(shí)一眼就可看出結(jié)果 這里只是想說明方法而已 3 算法評(píng)價(jià) hn是要移動(dòng)圓盤數(shù)n 規(guī)模 的指數(shù)函數(shù) 以n 60為例子 可以計(jì)算出260 1 15292 1018 這個(gè)數(shù)是一個(gè)什么概念 假如你每秒鐘移動(dòng)一個(gè)盤 按照上述算法 你移動(dòng)60個(gè)盤的時(shí)間是 真是不算不知道 一算嚇一跳 n 60 數(shù)不過百 2也是很小的整數(shù) 可是260卻是一個(gè)很大的數(shù) 這就是所謂的 指數(shù)爆炸 現(xiàn)象 一般稱復(fù)雜性為規(guī)模n的指數(shù)函數(shù)的算法為 壞算法 好算法是指多項(xiàng)式算法或者線性算法 例23 確定平方項(xiàng)序列0 1 4 n2 的母函數(shù)例24 求解滿足初始值h0 1和h1 2的遞推關(guān)系hn 5hn 1 6hn 2 n 2 例25 令h0 h1 hn 是滿足遞推關(guān)系hn hn 1 16hn 2 20hn 3 0 n 3 的數(shù)列 其中h0 0 h1 1 h2 1 求hn的一般公式 定理7 5 1令h0 h1 hn 為滿足k階常系數(shù)線性齊次遞推關(guān)系hn c1hn 1 c2hn 2 ckhn k 0 ck 0 n k 的數(shù)列 則它的生成函數(shù)g x 形如g x p x q x 其中 q x 為具有非零常數(shù)項(xiàng)的k次多項(xiàng)式 p x 是小于k次的多項(xiàng)式 反之也成立 7 6一個(gè)幾何的例子 定理7 6 1通過畫出區(qū)域內(nèi)部不相交的對(duì)角線將具有n 1條邊的凸多邊形區(qū)域分割成三角形區(qū)域 令hn表示分成三角形區(qū)域的方法數(shù) 定義h1 1 則hn滿足遞推關(guān)系該遞推關(guān)系的解為 7 7指數(shù)生成函數(shù) 1 x x2 xk 1 x x2 2 xn n 指數(shù)生成函數(shù)例26 令n為一正整數(shù) 確定數(shù)列P n 0 P n 1 P n n 的