組合數(shù)學課件：第六章 遞推關(guān)系

1、第六章、遞推關(guān)系主要內(nèi)容6.1 遞推關(guān)系的建立6.2 常系數(shù)線性齊次遞推關(guān)系的求解6.3 常系數(shù)線性非齊次遞推關(guān)系的求解6.4 用生成函數(shù)求解遞推關(guān)系6.5 用迭代歸納法求解遞推關(guān)系及其應(yīng)用構(gòu)建求解遞推關(guān)系是組合計數(shù)的重要方法；在第四章討論錯位排列數(shù)Dn時，建立了關(guān)于Dn的遞推關(guān)系： Dn=(n-1)(Dn-1 + Dn-2) n3 D1=0，D2=1并由此推出以下的遞推關(guān)系： Dn=nDn-1 + (-1)n n2 D1=0 6.1 遞推關(guān)系的建立 定義6.1.1 給定一個數(shù)的序列H(0),H(1), H(n),若存在正整數(shù)n0，使得當nn0時，可以用等號(或小于，大于號)把H(n)和前面某

2、些項H(i)，0 i n，聯(lián)系起來，這樣的式子叫做遞推關(guān)系。 遞推關(guān)系也稱遞歸關(guān)系，遞歸方程。從本質(zhì)上講，遞推關(guān)系是研究整變量函數(shù)的或者說是研究數(shù)列的，與此對應(yīng)的是連續(xù)論域中的微分方程。因此，我們可以類似的方法對它們進行研究。 利用遞推關(guān)系和初值在某些情況下可以求出序列的通項表示式H(n)，正如第四章利用迭代法求出Dn的表達式一樣。 但是對于大多數(shù)遞推關(guān)系，目前還解不出H(n)的顯式來， 即使這樣，對于給定的n也可以從初值開始，一步一步地計算出H(n)的值或者范圍，而H(n)一般代表了某個組合計數(shù)問題的解，因此遞推關(guān)系是組合計數(shù)的重要工具。求解遞推關(guān)系的常用方法（1）特征根法；（2）迭代歸納法

3、；（3）生成函數(shù)法；例6.1.1 一個小孩上樓梯，每次可上一階或兩階，問上n階有多少種上法？解： 初始條件：f(1)=1,f(2)=2 要登上n階臺階，應(yīng)該最后邁上一個臺階：f(n-1)或兩個臺階： f(n-2) ，則 f(n)=f(n-1)+f(n-2) (n3, n為整數(shù))例6.1.2 Fibonacci數(shù)列問題是一個古老的數(shù)學問題，是于1202年提出的，問題表述如下: 把一對兔子（雌、雄各一只）在某年的開始放到圍欄中，每個月這對兔子都生出一對新兔，其中雌、雄各一只。由第二個月開始，每對新兔每個月也生出一對新兔，也是雌、雄各一只。問一年后圍欄中有多少對兔子？這是一個數(shù)學模型的形象表示，不能

4、真正用來表示兔子的繁殖規(guī)律。 對于n=1,2,令f(n)表示第n個月開始時圍欄中的兔子對數(shù)，顯然有f(1)=1,f(2)=2, 在第n個月的開始，那些第n-1個月初已經(jīng)在 圍欄中的兔子仍然存在，而且每對在第n-2個月初就存在的兔子將在第n-1個月開始將要生出一對新兔來，所以有： f(n)=f(n-1)+f(n-2) (n3, n為整數(shù)) f(1)=1,f(2)=2 這是一個帶有初值的遞推關(guān)系。如果規(guī)定f(0)=1,則上式變成： f(n)=f(n-1)+f(n-2) (n2, n為整數(shù)) f(0)=1,f(1)=1稱滿足這個式子的數(shù)列就成為Fibonacci數(shù)列，數(shù)列中的項叫做Fibonacci

5、數(shù).多米諾牌（可以看作是2*1大小的方格)完全覆蓋一個n*2的棋盤。覆蓋的方案數(shù)？例6.1.3 （Hanoi塔問題）現(xiàn)有A，B，C三根立柱以及n個大小不等的中空圓盤，這些圓盤自小到大套在A柱上形成塔形，如圖6.1.1所示，要把n個圓盤從A柱上搬到C柱上，并保持原來的順序不變，要求每次只能從一根立柱上拿下一個圓盤放在另一根立柱上，且不允許大盤壓在小盤上，問至少要搬多少次 ？ 解：記f(n)為n個圓盤從A柱搬到C柱所需的最小次數(shù).整個搬運過程可分成三個階段；（1）將套在A柱上面的n-1個圓盤從A柱按要求搬到B柱，搬動 次數(shù)為f(n-1);（2）把A柱上最下面的那個圓盤搬到C柱上，搬動次數(shù)為1;（3

6、）把B柱上的n-1個圓盤按要求搬到C柱上，搬動次數(shù)為f(n-1);由加法原則知， f(n)=2f(n-1)+1又顯然f(1)=1，所以有如下帶有初值的遞推關(guān)系: f(n)=2f(n-1)+1 f(1)=1 例6.1.4 設(shè)P是平面上n個連通區(qū)域D1,D2,Dn的公共交界點，如下圖所示?，F(xiàn)用k種顏色對其著色，要求有公共邊界的相鄰區(qū)域著以不同的顏色，令f(n)表示不同的著色方案數(shù)，求它所滿足的遞推關(guān)系。 有： f(n)= (k-1)f(n-2)+(k-2)f(n-1) （n4） f(2)=k(k-1) ， f(3)=k(k-1)(k-2)D1與Dn-1同色，此時Dn有k-1種方案，可將D1與D n

7、-2看成相鄰區(qū)域，則D1,D2, , Dn-2的著色方案為f(n-2)。D1與Dn-1異色，此時Dn有k-2種方案，可將，則D1,D2, , Dn-1的著色方案為f(n-1)。(k-1)f(n-2)+(k-2)f(n-1)6.2 常系數(shù)線性齊次遞推關(guān)系的求解設(shè)k是給定的正整數(shù)，若數(shù)列的相鄰項間滿足關(guān)系對 成立，其中，則稱該關(guān)系為的k階線性遞推關(guān)系.如果都是常數(shù)，則稱之為k階常系數(shù)線性遞推關(guān)系.如果=0,則稱之為齊次的.定義6.2.1 如果有一個數(shù)列代入上面的遞推關(guān)系，使得對于nk都成立，則稱這個數(shù)列是遞推關(guān)系的解。定義6.2.2 方程 xk-c1xk-1-c2xk-2-ck=0 叫做遞推關(guān)系(

8、1)的特征方程，它的k個根q1，q2qk(可能有重根)叫做該遞推關(guān)系的特征根。其中qi（i=1,2,k）是復(fù)數(shù)。常系數(shù)線性齊次遞推關(guān)系的一般形式為 -(1) 定理 6.2.1 設(shè)q1，q2，qk是遞推關(guān)系的k個互不相等的特征根，則 f(n)b1q1 nb2q2 nbkqk n是遞推關(guān)系的通解 .（b1,b2,bk是任意常數(shù)）例6.2.1 解關(guān)于Fibonacci數(shù)的遞推關(guān)系例6.2.2定理6.2.2設(shè)q1，q2，qt是遞推關(guān)系f(n)=a1f(n-1)+a2f(n-2)+akf(n-k) (nk，ak0),的不相等的特征根，其重數(shù)分別為e1，e2，et( e1+e2+et=k),則這個遞推關(guān)系

9、的通解是：f(n)= f1(n)+ f2(n)+ + ft(n)其中： fi(n)c1qi nc2nqi n例6.2.4 求解遞推關(guān)系一般形式 ： f(n)=c1f(n-1)+c2f(n-2)+ckf(n-k)+g(n) (nk,ck0,g(n)0),其通解是齊次通解與特解之和，即f(n)=f(n)+f(n)其中f(n)是原遞推關(guān)系的特解； f(n)是所對應(yīng)的齊次遞推關(guān)系 f(n)=c1f (n-1)+c2f (n-2)+ckf (n-k)的通解 。下面主要介紹f(n)的求解方法。6.3常系數(shù)線性非齊次遞推關(guān)系的求解 對于一般g(n)沒有普遍的解法，只對一些簡單的情況可以用待定系數(shù)法求f(n)

10、 。比較等式兩邊例6.3.1 求解遞推關(guān)系解： 因為4不是特征方程的根，所以該遞推關(guān)系的非齊次特解為，將其代入遞推關(guān)系，得的系數(shù)，得 從而 a=2.而相應(yīng)齊次遞推關(guān)系的通解為，由定理6.3.1知，非齊次遞推關(guān)系的通解為 由初值得從而 故 例6.3.2 求解遞推關(guān)系解 由于2是特征方程的二重根，所以該遞推關(guān)系的特解為 將它代入遞推關(guān)系，并比較等號兩邊n的系數(shù)及常數(shù)項，得到 而相應(yīng)齊次遞推關(guān)系的通解為從而非齊次遞推關(guān)系的通解為再由初值求得于是根據(jù)前面的分析，可知該遞推關(guān)系的通解為 解 相應(yīng)的特征方程為x=2，故齊次解為2n。設(shè)非齊次特解為b，代入原遞推關(guān)系，得 例6.3.3 求Hanoi塔問題滿足

11、的遞推關(guān)系 所以特解為代入初值得所以 對于有些非線性遞推關(guān)系，我們可以通過變換化為常系數(shù)線性遞推關(guān)系。例6.3.6. 迭代法給定n個實數(shù)a1,a2,an，可以用多少種不同的方法來構(gòu)成它們的乘積？（與順序有關(guān)）例如 (a1*a2)*a3, a1*（a2*a3)H(1)=1;H(n)=(4(n-2)+2) H(n-1)=. =(n-1)!C(2n-2,n-1)D(n)=(n-1)【D(n-1)+D（n-2)】D(n)-nD(n-1)=-D(n-1）+ (n-1) D（n-2） =-（ D(n-1）- (n-1) D（n-2） =（-1）n-2利用生成函數(shù)求解各類遞推關(guān)系有廣泛的適用性，其基本步驟是

12、： （1）令6.4 用生成函數(shù)求解遞推關(guān)系（2）將關(guān)于的遞推關(guān)系式轉(zhuǎn)化成關(guān)于的方程式； ，將展開成x的冪級數(shù)，的系數(shù)即是。（3）解出 例6.4.1 求解遞推關(guān)系 解： 令則有將代入上式并整理，得所以 求解h(n)=5h(n-1)-6h(n-2),h0=1,h1=-2 令g(x)=h0+h1x+ h2x2 +hnxn+ -5xg(x)= -5h0 x-5h1x2-5hn-1xn+ 6x2g(x)= 6h0 x2+6hn-2xn+ (1-5x+6x2)g(x)=h0+(h1-5h0)x+(h2-5h1+6h0)x2+ g(x)=(1-7x)/ (1-5x+6x2) h(n)=5*2n-4*3n其中是給定常系數(shù),那么，定理6.4.1 具有初值條件的的k階常系數(shù)線性遞歸關(guān)系為：有生成函數(shù)其中，是不大于k-1次的多項式。當且僅當關(guān)于遞