組合數(shù)學課件(第六章_遞推關系)

1、目錄（目錄（1）第第1章章 什么是組合數(shù)學什么是組合數(shù)學1.1引例引例1.2組合數(shù)學研究對象、內容和方法組合數(shù)學研究對象、內容和方法第第2章章 鴿巢原理鴿巢原理2.1 鴿巢原理：簡單形式鴿巢原理：簡單形式2.2 鴿巢原理：加強形式鴿巢原理：加強形式2.3 Ramsey定理定理2.4 鴿巢原理與鴿巢原理與Ramsey定理的應用定理的應用本章小結 習題第第3章章 排列與組合排列與組合3.1 兩個基本的計數(shù)原理兩個基本的計數(shù)原理3.2 集合的排列與組合集合的排列與組合3.3 多重集的排列與組合多重集的排列與組合本章小結 習題第四章第四章 二項式系數(shù)二項式系數(shù)4.1 二項式定理二項式定理4.2組合恒等

2、式組合恒等式4.3非降路徑問題非降路徑問題4.4牛頓二項式定理牛頓二項式定理4.5多項式定理多項式定理4.6 基本組合計數(shù)的應用基本組合計數(shù)的應用本章小結 習題第五章第五章 包含排斥原理包含排斥原理5.1 包含排斥原理包含排斥原理5.2 多重集的多重集的r-組合數(shù)組合數(shù)5.3錯位排列錯位排列5.4 有限制條件的排列問題有限制條件的排列問題5.5有禁區(qū)的排列問題有禁區(qū)的排列問題本章小結 習題目目 錄錄目錄（目錄（2） 第六章第六章 遞推關系遞推關系6.1 Fibonacci數(shù)列6.2 常系數(shù)線性齊次遞推關系的求解6.3 常系數(shù)線性非齊次遞推關系的求解6.4 用迭代和歸納法求解遞推關系本章小結 習

3、題第七章第七章 生成函數(shù)生成函數(shù)7.1生成函數(shù)的定義和性質7.2多重集的r-組合數(shù)7.3正整數(shù)的劃分7.4指數(shù)生成函數(shù)與多重集的排列問題7.5 Catalan數(shù)和Stiring數(shù)本章小結 習題 第八章第八章 Polya定理定理8.1置換群中的共軛類與軌道8.2 Polya定理的特殊形式及其應用本章小結 習題*課程總結課程總結第第6章章 遞推關系遞推關系 本章本章主要介紹遞推關系的主要介紹遞推關系的建立建立及幾種及幾種常見的求解方法：常見的求解方法：6.1 Fibonacci數(shù)列數(shù)列6.2 常系數(shù)線性齊次遞推關系的求解常系數(shù)線性齊次遞推關系的求解6.3 常系數(shù)線性非齊次遞推關系的求解常系數(shù)線性非

4、齊次遞推關系的求解6.4 用迭代和歸納法求解遞推關系用迭代和歸納法求解遞推關系 第第6章章 遞推關系遞推關系教學目標：1掌握幾種遞推關系的建立方法；2理解并掌握常系數(shù)線性齊次及非齊次遞推關系的求解方法；3能運用迭代歸納法求解遞推關系；4記住并理解Fibonacci數(shù)的定義及遞推公式，會推導Fibonacci數(shù)的一些性質，能運用它們解決一些組合計數(shù)問題。重點：遞推關系的建立方法、常系數(shù)線性齊次及非齊次遞推關系的求解方法、Fibonacci數(shù)和Catalan數(shù)的定義、遞推公式及性質 難點：Catalan數(shù)的定義、遞推公式及性質 第第6章章 遞推關系遞推關系6.1 遞推關系定義6.1 遞推關系的建立

5、遞推關系的建立定義定義 6.1設設H(n)為一序列，把該序列中為一序列，把該序列中H(n)和它前面幾和它前面幾個個H(i)(0in-1)用等號（或大于、小于號）關用等號（或大于、小于號）關聯(lián)起來的方程稱做一個聯(lián)起來的方程稱做一個遞推關系遞推關系（遞歸關系）。（遞歸關系）。 如第如第3章的錯排數(shù)章的錯排數(shù)Dn=(n-1)(Dn-1+Dn-2)，(n3) 和關系式和關系式an=3an-1，(n1)都是遞推關系。都是遞推關系。 如如a0=d0 , a1=d1, ak=dk，di為常數(shù)為常數(shù)(i=0,1,k)，稱為遞推，稱為遞推關系的關系的初值初值。 如如D1=0, D2=1作為初值即可惟一的確定序列

6、作為初值即可惟一的確定序列(D0,D1, Dn,)，a0=1作為初值即可惟一的確定序列作為初值即可惟一的確定序列(1,3,32,3n,)。將遞推關系和初值結合起來稱為將遞推關系和初值結合起來稱為帶初值的遞推關系帶初值的遞推關系。如。如1120123(1)(1)()(3),10,1nnnnnaanDnDDnaDD6.1 遞推關系建立例1-16.1 遞推關系的建立（遞推關系的建立（Fibonacci數(shù)列）數(shù)列）例例 題題例例1、在一個平面上有一個圓和在一個平面上有一個圓和n條直線，條直線，這些直線中的每一條在圓內都同其他的直這些直線中的每一條在圓內都同其他的直線相交。如果沒有多于三條的直線相交于線

7、相交。如果沒有多于三條的直線相交于一點，試問這些直線將圓分成多少個不同一點，試問這些直線將圓分成多少個不同區(qū)域？區(qū)域？ 6.1 遞推關系建立例1-26.1 遞推關系的建立遞推關系的建立例例 題題解：解：要求解這個問題，首先必須建立遞推關系，然后求解遞推要求解這個問題，首先必須建立遞推關系，然后求解遞推關系即可。關系即可。設這設這n條直線將圓分成的區(qū)域數(shù)為條直線將圓分成的區(qū)域數(shù)為an，如果有，如果有n-1條直線將圓分條直線將圓分成成an-1個區(qū)域，那么再加入第個區(qū)域，那么再加入第n條直線與在圓內的其他條直線與在圓內的其他n-1條直線條直線相交。顯然，這條直線在圓內被分成相交。顯然，這條直線在圓內

8、被分成n條線段，而每條線段又將條線段，而每條線段又將第第n條直線在圓內經過的區(qū)域分成兩個區(qū)域。這樣，加入第條直線在圓內經過的區(qū)域分成兩個區(qū)域。這樣，加入第n條條直線后，圓內就增加了直線后，圓內就增加了n個區(qū)域。而對于個區(qū)域。而對于n=0，顯然有，顯然有a0=1，于，于是對于每個整數(shù)是對于每個整數(shù) n，可以建立如下帶初值的遞推關系，可以建立如下帶初值的遞推關系 （求解方法以后幾節(jié)再介紹）這就是問題的解答。（求解方法以后幾節(jié)再介紹）這就是問題的解答。nnnaannanna102(1)122求求解解遞遞推推關關系系得得6.1 遞推關系建立例26.1 遞推關系的建立遞推關系的建立例例 題題例例2、在一

9、個平面中，有在一個平面中，有n個圓兩兩相交，個圓兩兩相交，但任二個圓不相切，任三個圓無公共點，但任二個圓不相切，任三個圓無公共點，求這求這n個圓把平面分成多個區(qū)域？個圓把平面分成多個區(qū)域？ 解：解：設這設這n個圓將平面分成個圓將平面分成an個區(qū)域。個區(qū)域。如圖。易見如圖。易見 ，a1=2, a2=4。現(xiàn)在假設前現(xiàn)在假設前n-1個圓將平面分成了個圓將平面分成了an-1個區(qū)域，當加入第個區(qū)域，當加入第n個圓時，由題設個圓時，由題設這個圓與前面的這個圓與前面的n-1個圓一定交于個圓一定交于2(n-1)個點，這個點，這2(n-1)個點把第個點把第n個圓個圓分成分成2(n-1)條弧，而每條弧正好將前條弧

10、，而每條弧正好將前面的面的 n-1個圓分成的區(qū)域中的其經過個圓分成的區(qū)域中的其經過的每個區(qū)域分成的每個區(qū)域分成2個區(qū)域，故新加入的第個區(qū)域，故新加入的第n個圓使所成的區(qū)域數(shù)個圓使所成的區(qū)域數(shù)增加了增加了2(n-1) 。因此可以。因此可以建立如下帶初值的遞推關系：建立如下帶初值的遞推關系： 求解這個遞推關系可以得到問題的解答。求解這個遞推關系可以得到問題的解答。nnaanna112(1)(2)26.1 遞推關系建立例3-16.1 遞推關系的建立遞推關系的建立例例 題題例例3、“Fibonacci兔子問題兔子問題”也是組合數(shù)學也是組合數(shù)學中的著名問題之一。這個問題是指：從某中的著名問題之一。這個問

11、題是指：從某一年某一月開始，把雌雄各一的一對兔子一年某一月開始，把雌雄各一的一對兔子放入養(yǎng)殖場中，從第二個月雌兔每月產雌放入養(yǎng)殖場中，從第二個月雌兔每月產雌雄各一的一對新兔。每對新兔也是從第二雄各一的一對新兔。每對新兔也是從第二個月起每月產一對兔子。試問第個月起每月產一對兔子。試問第n個月后養(yǎng)個月后養(yǎng)殖場中共有多少對兔子？殖場中共有多少對兔子？ 6.1 遞推關系建立例3-1表示幼兔表示幼兔表示成兔表示成兔實線表示成長實線表示成長虛線表示生殖虛線表示生殖1: 12: 13: 24: 35: 56: 87: 136.1 遞推關系的建立遞推關系的建立6.1 遞推關系建立例3-26.1 遞推關系的建立

12、遞推關系的建立例例 題題解：解：設第設第n個月時養(yǎng)殖場中兔子的對數(shù)為個月時養(yǎng)殖場中兔子的對數(shù)為Fn。并定義。并定義F0=1，顯然有，顯然有，F(xiàn)1=1。由于在第由于在第n個月時，除了有第個月時，除了有第n-1個月時養(yǎng)殖場中的全部兔子個月時養(yǎng)殖場中的全部兔子Fn-1外，還應該有外，還應該有Fn-2對新兔子，這是因為在第對新兔子，這是因為在第n-2個月就已個月就已經有的每對兔子，在第經有的每對兔子，在第n個月里都應生一對新的兔子。因此個月里都應生一對新的兔子。因此可以可以建立如下帶初值的遞推關系建立如下帶初值的遞推關系 求解上式可以得到我們所需的答案。求解上式可以得到我們所需的答案。注：注：利用該式

13、我們可以推得利用該式我們可以推得(F0,F1,Fn,)=(1,1,2,3,5,8,13,21,34,55,)常稱常稱Fn為為Fibonacci數(shù)數(shù)， (F0,F1,Fn,)為為Fibonacci數(shù)列數(shù)列。Fibonacci數(shù)列在數(shù)學中是一個奇特而又常見的序列，它在算數(shù)列在數(shù)學中是一個奇特而又常見的序列，它在算法分析中起著重要的作用。法分析中起著重要的作用。nnnFFFnFF1201(2)1,1注：以上各例均為經典組合數(shù)學問題，在算法分析中常用；注：以上各例均為經典組合數(shù)學問題，在算法分析中常用； 對普通的遞推關系無一般規(guī)則可解。對普通的遞推關系無一般規(guī)則可解。 6.1 Fibonacci數(shù)列應

14、用及性質6.1 遞推關系的建立遞推關系的建立Fibonacci數(shù)列在組合計數(shù)中的應用數(shù)列在組合計數(shù)中的應用例：確定2n棋盤用多米諾牌完美覆蓋的方法數(shù)hn。 規(guī)定h0=1. 容易看到h1=1， h2=2， h3=3。 hn= hn1 滿足斐波那契遞推關系。hn是斐波那契數(shù)。 + hn2 再如，一個人站在再如，一個人站在“梯子格梯子格”的起點處向上跳，的起點處向上跳，從格外只能進入第從格外只能進入第1 1格，從格中，每次可向上跳一格，從格中，每次可向上跳一格或兩格，問：格或兩格，問：可以用多少種方法，跳到第可以用多少種方法，跳到第n格？格？nt121tt6.1 遞推關系的建立遞推關系的建立Fibo

15、nacci數(shù)列在組合計數(shù)中的應用數(shù)列在組合計數(shù)中的應用解：設跳到第解：設跳到第n格的方法有格的方法有 種。種。 由于他跳入第由于他跳入第1格，只有一格，只有一種方法；跳入第種方法；跳入第2格，必須先跳格，必須先跳入第入第1格，所以也只有一種方法，格，所以也只有一種方法，從而從而 而能一次跳入第而能一次跳入第n格的，只有第格的，只有第 和第和第 兩格，因此，跳入第兩格，因此，跳入第 格的方法格的方法 數(shù)，是跳入第數(shù)，是跳入第 格的方法數(shù)格的方法數(shù) ，加上跳入，加上跳入 第第 格的方法數(shù)格的方法數(shù) 之和。之和。 即即 。綜合得遞推公式。綜合得遞推公式 容易算出，跳格數(shù)列容易算出，跳格數(shù)列 就是斐波

16、那契數(shù)列就是斐波那契數(shù)列 1，1，2，3，5，8，13，21，34，1n2n1nt2n2nt12nnnttt12121(3,4,5,)nnntttttnn nt1n6.1 遞推關系的建立遞推關系的建立Fibonacci數(shù)列在組合計數(shù)中的應用數(shù)列在組合計數(shù)中的應用6.1 Fibonacci數(shù)列應用及性質6.1 遞推關系的建立遞推關系的建立類似的例子類似的例子奇妙的斐波那契序列 斐波那契螺旋線數(shù)6.1 Fibonacci數(shù)列應用及性質 樹杈樹杈的的數(shù)數(shù)目目138532116.1 遞推關系的建立遞推關系的建立類似的例子類似的例子6.1 Fibonacci數(shù)列應用及性質（1）)(nf6.1 遞推關系的

17、建立遞推關系的建立Fibonacci數(shù)列性質數(shù)列性質1. Fibonacci數(shù) 可以表示為二項式系數(shù)之和，即0,1,n1( ),.012nnnknf nkk 證明 當 時，有 ，即 ，所以只要證明下面的等式成立，即證用歸納法。當 時，有 成立。假設對 等式都成立，則有0(0)10f nkk0n 2nk 10( ).01nnnkf nkn 0nkk6.1 Fibonacci數(shù)列應用及性質由歸納法，命題成立。6.1 遞推關系的建立遞推關系的建立Fibonacci數(shù)列性質數(shù)列性質(1)( )(1)100112001111000101110011f nf nf nnnnnnnnnnnnnnnn .6.

18、1 Fibonacci數(shù)列應用及性質（2）6.1 遞推關系的建立遞推關系的建立Fibonacci數(shù)列性質數(shù)列性質2. Fibonacci數(shù)(0)(2)(1),fff證明把以上各式的左邊和右邊分別相加，得(1)(3)(2),fff( )(2)(1).f nf nf n(0)(1)( )(2)(1)(2) 1.fff nf nff n(0)(1)( )(2) 1.fff nf n6.1 Fibonacci數(shù)列應用及性質（3-4）6.1 遞推關系的建立遞推關系的建立Fibonacci數(shù)列性質數(shù)列性質3. Fibonacci數(shù)(0)(1),ff證明把以上各式的左邊和右邊分別相加，得(2)(3)(1),

19、fff(2 )(21)(21).fnfnfn(0)(2)(2 )(21).fffnfn(0)(2)(2 )(21).fffnfn4. Fibonacci數(shù)(1)(3)(21)(2 ) 1.fffnfn證明 由性質2和3即得.6.1 Fibonacci數(shù)列應用及性質（5）6.1 遞推關系的建立遞推關系的建立Fibonacci數(shù)列性質數(shù)列性質5. 2(0)(1)(0),fff證明把以上各式的左邊和右邊分別相加，得2(1)(1) (2)(0)(2)(1)(1)(0),ffffffff2( )( ) (1)(1)(1)( )( )(1).fnf nf nf nf nf nf nf n222(0)(1)

20、( )( )(1).fffnf nf n222(0)(1)( )( )(1).fffnf nf n6.1 Fibonacci數(shù)列應用及性質（6）6.1 遞推關系的建立遞推關系的建立Fibonacci數(shù)列性質數(shù)列性質6. 證明由歸納法，等式成立。(2)(1)( )(1)(1)(0)( )f nf nf nff nff n()(1)(1)(2)( )(2).f nmf mf nf mf nmmk對 進行歸納.m當 時，有2m 成立，假設對一切 有等式成立，則(1)()(1) (1)(1)(2)( ) (2)(1)(3)( ) (1)(2)(1) (2)(3)( )( )(1)(1)( )f nkf

21、 nkf nkf kf nf kf nf kf nf kf nf kf kf nf kf kf nf kf nf kf n6.1 Fibonacci數(shù)列應用及性質6.1 遞推關系的建立遞推關系的建立Fibonacci數(shù)列性質數(shù)列性質 關于Fibonacci數(shù)列數(shù)列的性質還有許多，習題上也列出了一部分，這里就不一一介紹。 利用這些性質，我們可以將比較大的n的Fibonacci數(shù)化成較小的 的Fibonacci數(shù)，從而使計算更為方便。n6.2 常系數(shù)線遞推關系次遞推關系6.2 常系數(shù)線性齊次遞推關系常系數(shù)線性齊次遞推關系定義定義 6.2 若若H(n)中相鄰中相鄰k+1項滿足項滿足H(n)=a1H(

22、n-1)+a2H(n-2)+ akH(n-k)，(nk)稱之為稱之為H(n)的的k階常系數(shù)線性齊次遞推關系階常系數(shù)線性齊次遞推關系。其中其中ai(i=1,2,k)是常數(shù)，且是常數(shù)，且ak0。 該遞推關系還可以寫作該遞推關系還可以寫作 H(n) -a1H(n-1)-a2H(n-2)- akH(n-k) =0. H(0)=d0 , H(1)=d1 , , H(k-1)=dk-1稱為稱為初始條件初始條件，其中其中di(i=0,2,k-1)是常數(shù)；是常數(shù)；定義定義 6.3 C(x)=xk-a1xk-1-a2xk-2-ak稱為上述遞推關系的稱為上述遞推關系的特特征多項式征多項式； C(x)=0稱為上述遞

23、推關系的稱為上述遞推關系的特征方程特征方程；該方程的該方程的k個根個根q1,q2,qk稱為上述遞推關系的稱為上述遞推關系的特征根特征根. 其中其中qi(i=1,2,k)是復數(shù)是復數(shù).6.2 常系數(shù)線遞推關系次遞推關系定理6.1對此，有下面的定理定理定理6.112( )(1)(2)()0kH na H na H na H nk6.2 常系數(shù)線性齊次遞推關系常系數(shù)線性齊次遞推關系設設k階常系數(shù)線性齊次遞推關系階常系數(shù)線性齊次遞推關系H(n)為為若若q0, H(n)=qn是上述遞推關系的解，當且僅當是上述遞推關系的解，當且僅當q是上述特征方程的解。是上述特征方程的解。 證明：證明：若若q 0, H(

24、n)=qn是遞推關系是遞推關系的解的解 qn =a1 qn-1 +a2 qn-2 + ak qn-k (nk ) qk =a1 qk-1 +a2 qk-2 + ak q是特征方程是特征方程xk-a1xk-1-a2xk-2-ak=0的根。的根。證畢。證畢。12( )(1)(2)()0kH na H na H na H nk定理定理6.2 若 都是齊次遞推關系的解，那么 也是齊次遞推關系的解。 證: 由 是齊次遞推關系的解知6.2 常系數(shù)線遞推關系次遞推關系定理6.2 ,nnba21nnbAaA ,nnba02211 knknnnacacaca02211 knknnnbcbcbcb01212111

25、1 knknnnaAcaAcaAcaA022221212 knknnnbAcbAcbAcbA0)()()(211211121 knknknnnnbAaAcbAaAcbAaA6.2 常系數(shù)線性齊次遞推關系常系數(shù)線性齊次遞推關系6.2 常系數(shù)線性齊次相異特征根定理6.36.2 常系數(shù)線性齊次遞推關系常系數(shù)線性齊次遞推關系6.2.1 相異特征根的解法相異特征根的解法 定理定理 6.3若若q1,q2,qk,為上述遞推關系的特征根（相異），為上述遞推關系的特征根（相異），c1, c2,ck為任意常數(shù)，則為任意常數(shù)，則an=c1q1n+c2q2n+ckqkn為上述遞推關系的解。為上述遞推關系的解。 證明：

26、證明：由于由于qi(i=1,2,k)是特征方程是特征方程xk-b1xk-1-b2xk-2-bk=0的根，的根，由定理由定理6.1有有qin =b1 qin-1 +b2 qin-2 + bk qin-k，i=1,2,k將上式兩邊同乘以將上式兩邊同乘以ci ，然后從，然后從1到到k求和有求和有因此因此an=c1q1n+c2q2n+ckqkn是遞推關系是遞推關系an=b1an-1+b2an-2+ bkan-k的解。的解。kknnnn kiiiiikiiikkknnn kiiiikiiiiic qc b qb qb qbc qbc qbc q1212111212111(.).6.2 常系數(shù)線性齊次相異

27、特征根定義6.4kccc,.,216.2 常系數(shù)線性齊次遞推關系常系數(shù)線性齊次遞推關系6.2.1 相異特征根的解法相異特征根的解法 定義定義6.4如果對于遞推關系如果對于遞推關系H(n)=b1H(n-1)+b2H(n-2)+ bkH(n-k)的每個解的每個解h(n)都可以選擇一組常數(shù)都可以選擇一組常數(shù) 使得使得成立，則稱成立，則稱是遞推關系的通解，其中是遞推關系的通解，其中 為任意常數(shù)。為任意常數(shù)。nkknnqcqcqcnh2211)(nkknnqcqcqcnh2211)(12,kc cc6.2 常系數(shù)線性齊次相異特征根定理6.46.2 常系數(shù)線性齊次遞推關系常系數(shù)線性齊次遞推關系6.2.1

28、相異特征根的解法相異特征根的解法 定理定理 6.4若若q1,q2,qk為上述遞推關系的特征根（相異），為上述遞推關系的特征根（相異），則則an=c1q1n+c2q2n+ckqkn為上述遞推關系的通解，為上述遞推關系的通解，其中其中ci由初始條件確定。由初始條件確定。證明：證明：由定理由定理6.2知，知， an=c1q1n+c2q2n+ckqkn是遞推關系是遞推關系an= b1an-1+b2an-2+ bkan-k的的解解。只需證明，若該式滿足遞推關系。只需證明，若該式滿足遞推關系式式an=b1an-1+b2an-2+ bkan-k的任意初值條件式的任意初值條件式a0=d0,a1=d1, , a

29、k-1=dk-1所得到的關于所得到的關于c1,c2,ck的線性方程組有惟一解即可。的線性方程組有惟一解即可。由初值條件式由初值條件式a0=d0,a1=d1,ak-1=dk-1，我們得到，我們得到因此，上述線性方程組關于因此，上述線性方程組關于c1,c2,ck有惟一的解。從而證明了有惟一的解。從而證明了an=c1q1n+c2q2n+ckqkn 是遞推關系的是遞推關系的 an=b1an-1+b2an-2+ bkan-k 的的通解通解。kkkkkkkkkkkkkkcccdq cq cq cdqcqcqcdqqqAqqq1201 1221111112211211112.11.1. 該該方方程程組組的的

30、系系數(shù)數(shù)矩矩陣陣是是jiij kVandermondeAqq1()0 顯顯然然這這是是一一個個矩矩陣陣，故故有有例例1、求遞歸關系求遞歸關系 nnnFFFnFF1201(2)1,16.2 常系數(shù)線性齊次例16.2 常系數(shù)線性齊次遞推關系常系數(shù)線性齊次遞推關系5.2.1 相異特征根的解法相異特征根的解法 例例 題題 1201212112212011 12212(2)1,1101515,226.411,111515,2 52 515 1515 15222 52 5nnnnnnnnFFFnFFxxqqFc qc qccF Fq cq cccF遞推關系式的特征方程為特征根為由定理，其通解為 由初值條件

31、可得方程組解之得故該遞推關解系的解為：111151525nnnn6.2 常系數(shù)線性齊次例26.2 常系數(shù)線性齊次遞推關系常系數(shù)線性齊次遞推關系6.2.1 相異特征根的解法相異特征根的解法 例例 題題例例2、求遞歸關系求遞歸關系 12301222(3)1,2,0nnnnaaaanaaa 12332123112233123012123123123222201,1,26.411,2,022402,2 3,1 32(2 3)(nnnnnnnnnaaaaxxxqqqac qc qc qccca a accccccccca由遞推關系的特征方程為特征根為由定理，其通解為 由初值條件可得方程組解之得故該遞推關

32、系的解為解：1)(1 3) 2nn6.2 常系數(shù)線性齊次例3-16.2 常系數(shù)線性齊次遞推關系常系數(shù)線性齊次遞推關系6.2.1 相異特征根的解法相異特征根的解法 例例 題題例例3、用字母用字母a,b和和c組成長度是組成長度是n的字，如果要求的字，如果要求沒有兩個沒有兩個a相鄰，問這樣的字有多少個？相鄰，問這樣的字有多少個？解解 設設h(n)是所求的字的個數(shù)，是所求的字的個數(shù)，n1. 易見，長為易見，長為1的且沒有兩個的且沒有兩個a相鄰的字有相鄰的字有a,b和和c，所以，所以h(1)=3. 長為長為2的沒有的沒有 兩個兩個a相鄰的字相鄰的字有有ab,ac,ba,bb,bc,ca,cb,cc.所以

33、所以h(2)=8. 設設n 3,如果字中的第一個字母是如果字中的第一個字母是a，那么第二個字母只能是，那么第二個字母只能是b或或c, 其余的字母可以有其余的字母可以有h(n-2)種方式來選擇，因此以種方式來選擇，因此以a開頭的開頭的字有字有2h(n-2)個個.如果字中的第一個字母是如果字中的第一個字母是b, 那么這樣的字有那么這樣的字有h(n-1)個，同理以個，同理以c開頭的字也有開頭的字也有h(n-1)個，由加法法則得個，由加法法則得. 8)2(, 3) 1 ().3()2(2) 1(2)(hhnnhnhnh6.2 常系數(shù)線性齊次例3-26.2 常系數(shù)線性齊次遞推關系常系數(shù)線性齊次遞推關系6

34、.2.1 相異特征根的解法相異特征根的解法 例例 題題 212121222121222013,13( )(13)(13)(13)(13)3,(1)3, (2)8(13)(13)8.2323,.2 32 32323( )(13)(13)1,2,.2 32 3nnnnxx-q+q-h ncccchhcccch nn這個遞推關系的特征方程為特征根為所以其通解為由初值條件可得方程組解之得故該遞解：推關系的解為例例3、用字母用字母 a,b和和c組成長度是組成長度是n的字，如果要求的字，如果要求沒有兩個沒有兩個a相鄰，問這樣的字有多少個？相鄰，問這樣的字有多少個？. 8)2(, 3) 1 ().3()2(

35、2) 1(2)(hhnnhnhnh6.2 常系數(shù)線性齊次相同特征根定理6.56.2 常系數(shù)線性齊次遞推關系常系數(shù)線性齊次遞推關系6.2.2 相同特征根的解法相同特征根的解法 定理定理 6.5若若q為上述遞推關系的特征方程為上述遞推關系的特征方程C(x)=0的一個的一個m重重特征根，則特征根，則qn,nqn,nm-1qn為該遞推關系的解。為該遞推關系的解。 證明：證明：令令P(x)=xk-b1xk-1-b2xk-2-bk， Pn(x)= xn-k P(x) =xn-b1xn-1-b2xn-2-bkxn-k 。由于由于q是是P(x)=0的的m重根，故重根，故q也是也是Pn(x)=0的的m重根，由高

36、等代重根，由高等代數(shù)的知識知，數(shù)的知識知，q也是也是Pn(x) =0的的(m-1)重根，那么重根，那么q也是也是xPn(x)=0的的(m-1)重根，即重根，即q是方程是方程nxn-b1(n-1)xn-1-b2(n-2) xn-2-bk(n-k) xn-k =0的的(m-1)重根。類似地，重根。類似地，q是方程是方程n2xn-b1(n-1)2xn-1-b2(n-2)2 xn-2-bk(n-k)2xn-k=0的的(m-2)重根。重根。一般地，對任意的一般地，對任意的i, im, q是是方程方程nixn-b1(n-1)ixn-1-b2(n-2)ixn-2-bk(n-k)i xn-k=0的的(m-i)

37、重根。重根。即有即有niqn-b1(n-1)iqn-1-b2(n-2)iqn-2-bk (n-k)iqn-k=0。分別令分別令i=1,2,m-1，知，知nqn,n2qn,nm-1qn都是遞推關系都是遞推關系an=b1an-1+b2an-2+bkan-k的解，而的解，而qn是遞推關系是遞推關系an=b1an-1+b2an-2+bkan-k的解在定理的解在定理6.1中已經證明。中已經證明。故定理得證。故定理得證。6.2 常系數(shù)線性齊次相同特征根定理6.6-16.2 常系數(shù)線性齊次遞推關系常系數(shù)線性齊次遞推關系6.2.2 相同特征根的解法相同特征根的解法 定理定理 6.6若若q1,q2,qt分別為上

38、述遞推關系的特征方程分別為上述遞推關系的特征方程C(x)=0相異的相異的m1,m2,mt重特征根，重特征根， 為該遞推關系的通解，其中為該遞推關系的通解，其中cij由初始條件確定。由初始條件確定。tttiimnnmmmnnmtttmtmkacc ncnqcc ncnqcc ncnq1122121-11112112122-1-112(.)(.).(.)且且，則則 6.2 常系數(shù)線性齊次相同特征根定理6.6-26.2 常系數(shù)線性齊次遞推關系常系數(shù)線性齊次遞推關系5.2.2 相同特征根的解法相同特征根的解法 證明：證明：由定理由定理6.4知，知， 表達式表達式的右端每一項都是遞推關系的右端每一項都是

39、遞推關系an=b1an-1+b2an-2+bkan-k的解。故的解。故an也是該遞推關系的解?，F(xiàn)只需證明該式滿足遞推關系式也是該遞推關系的解?，F(xiàn)只需證明該式滿足遞推關系式an=b1an-1+b2an-2+bkan-k的任意初值條件式的任意初值條件式a0=d0,a1=d1, ak-1 =dk-1所得的線性方程組有惟一解即可。所得的線性方程組有惟一解即可。 將初值條件式將初值條件式a0=d0,a1=d1,ak-1=dk-1代入式代入式(A)得到下列方程組：得到下列方程組：這個方程組的系數(shù)行列式是這個方程組的系數(shù)行列式是Vandermonde行列式的一個推廣。行列式的一個推廣。其行列式之值為其行列式

40、之值為故方程組有惟一解。故方程組有惟一解。即即cij(i=1,2,t; j=1,2,mi)是由初值惟一確定，定理得證。是由初值惟一確定，定理得證。itmtjnijisijcccdc sqdsk112110111.(1,2,.,1)ttmnnmmmnnmtttmtacc ncnqcc ncnqcc ncAnq112212-1111211-1-1212212(.)(.).(.).() ijimtm mijiiij tAqqq211()()0 例例4、求遞歸關系求遞歸關系 nnnaaanaa12122(3)2,36.2 常系數(shù)線性齊次例46.2 常系數(shù)線性齊次遞推關系常系數(shù)線性齊次遞推關系6.2.2

41、 相同特征根的解法相同特征根的解法 例例 題題 122121212121212221016.622, 32311nnnnnaaaxxqqacc nccaaccccan遞推關系的特征方程為特征根為二重根由定理，其通解為 由初值條件可得方程組解之得故該遞推關解系解為：的例例5、求遞歸關系求遞歸關系 nnnnnaaaaanaaaa12340123352(4)1,0,1,2 6.2 常系數(shù)線性齊次例56.2 常系數(shù)線性齊次遞推關系常系數(shù)線性齊次遞推關系6.2.2 相同特征根的解法相同特征根的解法 例例 題題 12344321234212340123141234135235201,26.6( 1)( 1

42、)( 1)21,0,1,2120nnnnnnnnnnaaaaaxxxxqqqqacc nc ncaaaaccccccc遞推關系的特征方程為特征根為由定理，其通解為由初值條件可得方程組 解： 234123412342244139824229710,525252524229710( 1)( 1)( 1)252525252nnnnncccccccccccann解之得故該遞推關系的解為6.2 常系數(shù)線性齊次例66.2 常系數(shù)線性齊次遞推關系常系數(shù)線性齊次遞推關系6.2.2 相同特征根的解法相同特征根的解法 例例 題題例例6、求遞歸關系求遞歸關系nnnnaaaanaaa1230126128(3)1,2,

43、8 1233212321230121123123212361286128026.6( 2)1,2,8111( 2)21,2224( 2)812nnnnnnnaaaaxxxqqqacc nc naaaccccccccccnna遞推關系的特征方程為特征根為三重根由定理，其通解為由初值條件可得方程組解之得故該遞推關系的解為解：2( 2)2n6.2 常系數(shù)線性齊次例76.2 常系數(shù)線性齊次遞推關系常系數(shù)線性齊次遞推關系5.2.2 相同特征根的解法相同特征根的解法 例例 題題例例7、計算計算n階行列式的值：階行列式的值：2100.0001210.0000121.000.0000.2120000.1210

44、000.012解：解：設具有以上形式的設具有以上形式的n階行列式的值為階行列式的值為an，按第一列展開有，按第一列展開有 顯然顯然a1=2， a2=3，于是可建立遞推關系如下，于是可建立遞推關系如下這個遞推關系就是例這個遞推關系就是例3所求解的遞推關系，故由例所求解的遞推關系，故由例3的結果可知的結果可知( )(1)2100.0001210.0000121.000.0000.2120000.1210000.0122100.0001210.0000121.0002 .0000.2120000.1210000.012nn (1)(1)1000.0001210.0000121.000.0000.21

45、20000.1210000.0122100.0001210.0000121.0002 .0000.2120000.1210000.012nn(2)2100.0001210.0000121.000.0000.2120000.1210000.012n nnnaaanaa12122(3)2,31nan 6.2 常系數(shù)線性齊次注意事項6.2 常系數(shù)線性齊次遞推關系常系數(shù)線性齊次遞推關系6.2.2 相同特征根的解法相同特征根的解法 注意：注意： 建立遞推關系關系時可考慮某個特定數(shù)值，建立遞推關系關系時可考慮某個特定數(shù)值，如第一個、最后一個等；如第一個、最后一個等； k次遞推關系需要次遞推關系需要k個初值

46、，一般從個初值，一般從a0開始開始（不妨假設）；（不妨假設）； 結果需要驗證（結果需要驗證（n=k+1,k+2,） 。 6.3 常系數(shù)線性非齊次定義6.3 常系數(shù)線性非齊次遞推關系常系數(shù)線性非齊次遞推關系定義定義 6.4 若若H(n)中相鄰中相鄰k+1項滿足項滿足: H(n)=b1H(n-1)+b2H(n-2)+ bkH(n-k)+f(n)，(nk)稱之為稱之為H(n)的的k階常系數(shù)線性非齊次遞推關系階常系數(shù)線性非齊次遞推關系。其中。其中bi(i=1,2,k)是常數(shù)，且是常數(shù)，且bk0，f(n)0 。 若若f(n)=0，稱，稱 = b1H(n-1)+b2H(n-2)+ bkH(n-k)為上述遞

47、推關系為上述遞推關系導出導出的常系數(shù)線性的常系數(shù)線性齊次齊次遞推關系。遞推關系。( )H n6.3 常系數(shù)線性非齊次定理6.7-16.3 常系數(shù)線性非齊次遞推關系常系數(shù)線性非齊次遞推關系定理定理 6.7若若 為為an=b1an-1+b2an-2+bkan-k+f(n) 的一個的一個特解特解， 為為 =b1an-1+b2an-2+bkan-k 的一個的一個通解通解，則，則an= + 為原非齊次為原非齊次遞推關系的遞推關系的通解通解。 nana*nanana*證明：證明：由于由于 是非齊次是非齊次遞推關系式導出的齊次線性遞推關系式遞推關系式導出的齊次線性遞推關系式即即 的通解，故有的通解，故有又由

48、于又由于 是是非齊次非齊次遞推關系遞推關系的一個特解，故有的一個特解，故有將以上兩式的兩邊分別相加得將以上兩式的兩邊分別相加得由上式可見由上式可見 是式是式的解。的解。nnnkn kab ab ab a1122. nnnkn kab ab ab a1122.nnnkn kab ab ab af n1122.( )nnnkn kab ab ab af n1122.( )nnnnnnkn kn kaab aabaabaaf n111222.( )nnnnnniiiaaaac q1nnnkn kab ab ab af n1122.( )na*na設非線性齊次遞推關系為：an=b1an-1+b2an-

49、2+bkan-k+f(n)6.3 常系數(shù)線性非齊次定理6.7-26.3 常系數(shù)線性非齊次遞推關系常系數(shù)線性非齊次遞推關系定理定理 6.7若若 為為an=b1an-1+b2an-2+bkan-k+f(n) 的一個的一個特特解解， 為為 =b1an-1+b2an-2+bkan-k 的一個的一個通解通解，則則an= + 為原非齊次遞推關系的為原非齊次遞推關系的通解通解。 nana*nanana*現(xiàn)只需證明現(xiàn)只需證明 能滿足式能滿足式 的任意初值條件的任意初值條件式式 所導出的關于所導出的關于c1, c2,ck為未知為未知數(shù)的線性方程組數(shù)的線性方程組有惟一解即可。式中有惟一解即可。式中 。而這是顯然。

50、而這是顯然的。因為該方程組的系數(shù)矩陣是一個的。因為該方程組的系數(shù)矩陣是一個Verdermonde矩陣，其行矩陣，其行列式的值不為列式的值不為0。故定理得證。故定理得證。nnnnnniiiaaaac q1nnnkn kab ab ab af n1122.( )kkadadad001111,.,1201 122111111221.kkkkkkkkkcccdq cq cq cdqcqcqcd (0,1,.,1)iiidda ik6.3 常系數(shù)線性非齊次定理6.7-36.3 常系數(shù)線性非齊次遞推關系常系數(shù)線性非齊次遞推關系定理定理 6.7若若 為為an=b1an-1+b2an-2+bkan-k+f(n

51、) 的一個的一個特特解解， 為為 =b1an-1+b2an-2+bkan-k 的一個的一個通解通解，則則an= + 為原非齊次遞推關系的為原非齊次遞推關系的通解通解。 nana*nanana*v 注：注：定理定理6.7指出，若要求一個常系數(shù)線性非齊次遞推指出，若要求一個常系數(shù)線性非齊次遞推關系式的通解，必須先求出這個遞推關系所導出的常系數(shù)關系式的通解，必須先求出這個遞推關系所導出的常系數(shù)線性齊次遞推關系的通解，然后再求這個遞推關系式的一線性齊次遞推關系的通解，然后再求這個遞推關系式的一個特解，將其相加即可。個特解，將其相加即可。v 然而，求一個非齊次線性遞推關系的特解，通常沒有然而，求一個非齊

52、次線性遞推關系的特解，通常沒有系統(tǒng)的方法，但當函數(shù)系統(tǒng)的方法，但當函數(shù)f(n)是某些特殊形式時，才有一些是某些特殊形式時，才有一些規(guī)范的求法。規(guī)范的求法。v 若若f(n)為為n的的k次多項式，則次多項式，則 =A0nk+A1nk-1+Ak，其，其中中A0, A1,Ak為待定系數(shù)；若導出的常系數(shù)線性為待定系數(shù)；若導出的常系數(shù)線性齊次齊次遞推遞推關系特征根為關系特征根為1的的m重根，則重根，則 =(A0nk+A1nk-1 + +Ak )nm 。nana6.3 常系數(shù)線性非齊次特殊形式6.3 常系數(shù)線性非齊次遞推關系常系數(shù)線性非齊次遞推關系v 可針對可針對f(n)的某些特定形式，轉化為齊次性。的某些

53、特定形式，轉化為齊次性。v 若若f(n)為為 n的形式，如的形式，如不是導出的常系數(shù)線性不是導出的常系數(shù)線性齊次齊次遞遞推關系特征根，則推關系特征根，則 =A n，其中，其中A為待定系數(shù)；若為待定系數(shù)；若是導出是導出的常系數(shù)線性的常系數(shù)線性齊次齊次遞推關系的遞推關系的k重特征根根，則重特征根根，則 =(A0nk+A1nk-1+Ak) n 。nana6.3 常系數(shù)線性非齊次例16.3 常系數(shù)線性非齊次遞推關系常系數(shù)線性非齊次遞推關系例例 題題例例1、求遞歸關系求遞歸關系 nnaanna1023(1)3 11*0101010100100202026.4( 2)( )32(1)3332331, 32

54、31,3nnnnnaaxxacf nnaA nAA nAA nAnA nAAnnAAAAA由上述遞推關系式導出的齊次遞推關系為其特征方程為，故其特征根為由定理知所導出的齊次遞推關系的通解為由于，故其特解為將其代入上述遞推關系式得化簡得比較上式 和常數(shù)項的系數(shù)得解之得解：1*01111939116.7( 2)39111633991116( 2)399nnnnnnnnanaaacaccna，故由定理知上述遞推關系式的通解為又由初值條件得故有6.3常系數(shù)線性非齊次例2-16.3 常系數(shù)線性非齊次遞推關系常系數(shù)線性非齊次遞推關系例例 題題例例2、“Hanoi塔塔”問題：問題：n個大小不一的圓個大小不一

55、的圓盤依半徑的大小，從下而上的套在柱子盤依半徑的大小，從下而上的套在柱子A上。上。如圖所示?，F(xiàn)要求將所有的圓盤從柱子如圖所示?，F(xiàn)要求將所有的圓盤從柱子A上上全部移到柱子全部移到柱子C上，每次只允許從一根柱子上，每次只允許從一根柱子上轉移一個圓盤到另一根柱子上，且在轉移上轉移一個圓盤到另一根柱子上，且在轉移過程中不允許出現(xiàn)大圓盤放到小圓盤上。試過程中不允許出現(xiàn)大圓盤放到小圓盤上。試問至少要轉移多少次才能將柱子上的問至少要轉移多少次才能將柱子上的n個圓個圓盤全部轉移到柱子盤全部轉移到柱子C上去？上去？ 6.3常系數(shù)線性非齊次例2-26.3 常系數(shù)線性非齊次遞推關系常系數(shù)線性非齊次遞推關系例例 題題

56、解：解：用用an表示從一根柱子上的表示從一根柱子上的n個圓盤全部轉移到另一根柱子個圓盤全部轉移到另一根柱子上的轉移次數(shù)。顯然，上的轉移次數(shù)。顯然，a1=1, a2=3。當。當n3時，要將柱子時，要將柱子A上的上的n個圓盤轉移到柱子個圓盤轉移到柱子C上，可以這樣設想。上，可以這樣設想。先先把柱子把柱子A上的上的n-1個個圓盤轉移到柱子圓盤轉移到柱子B上，這需要轉移上，這需要轉移an-1次；次；然后然后把柱子把柱子A上最后上最后一個圓盤轉移到柱子一個圓盤轉移到柱子C上，顯然這需要轉移一次；上，顯然這需要轉移一次；最后最后再把柱再把柱子子B上的上的n-1個圓盤轉移到柱子個圓盤轉移到柱子C上，這也需要

57、轉移上，這也需要轉移an-1次。經過次。經過這些步驟后，所有這些步驟后，所有A上的上的n個圓盤就全部轉移到柱子個圓盤就全部轉移到柱子C上。由加上。由加法法則，這一共轉移了法法則，這一共轉移了2an-1+1次。于是可以次。于是可以建立如下帶初值的建立如下帶初值的遞推關系遞推關系 這就是我們這就是我們需要的結果。需要的結果。nnnnaanaa1121(2)121求求解解遞遞推推關關系系得得6.3 常系數(shù)線性非齊次例2-36.3 常系數(shù)線性非齊次遞推關系常系數(shù)線性非齊次遞推關系例例 題題例例2、求遞歸關系（求遞歸關系（Hanoi塔）塔） 1121(2)1nnaana 11*11202026.42(

58、)1210116.7121121121nnnnnnnnnnnnaaxxacf naAAAAaaaacacca由上述遞推關系式導出的齊次遞推關系為其特征方程為，故其特征根為由定理知所導出的齊次遞推關系的通解為由于，故其特解為將其代入上述遞推關系式得故，由定理知上述遞推關系式的通解為又由初值條件得故有解：6.3 常系數(shù)線性非齊次例36.3 常系數(shù)線性非齊次遞推關系常系數(shù)線性非齊次遞推關系例例 題題例例3、求遞歸關系求遞歸關系 112(1)(2)2nnaanna 11*010122010101016.41( )2(1)()(11)(nnnnnnaaxxacf nnaA nAaA nA nA nA n

59、A nA n由上述遞推關系式導出的齊次遞推關系為其特征方程為，故其特征根為由定理知所導出的齊次遞推關系的通解為由于，如設其特解為則待定系數(shù)求不出來，原因是其導出的齊次遞推關系的特征根為因此，這種情況下必須設其特解的形式為將其代入遞推關系式得解： 01001012*2121)2(1)2221,216.7222nnnnnnnAAAnnAAAAannaaanncacann化簡得比較上式 和常數(shù)項的系數(shù)得故由定理知上述遞推關系式的通解為又由初值條件得故有6.3 常系數(shù)線性非齊次例46.3 常系數(shù)線性非齊次遞推關系常系數(shù)線性非齊次遞推關系例例 題題例例4、求遞歸關系求遞歸關系 an+2an-1+an-2

60、=2n的通解。的通解。12212*1212202106.6()( 1)( )22222 2224941nnnnnnnnnnnnnnaaaxxxxacc nf naAAAAAa由上述遞推關系式導出的齊次遞推關系為其特征方程為，故其特征根為由定理知所導出的齊次遞推關系的通解為由于是的形式，且不是上述遞推關系式所導出的齊次遞推關系的特征根，故設其特解為將其代入遞推關系式得解之得故解：*12296.742()19nnnnnnaaacc n由定理知上述遞推關系式的通解為（）6.3 常系數(shù)線性非齊次例56.3 常系數(shù)線性非齊次遞推關系常系數(shù)線性非齊次遞推關系例例 題題例例5、求遞歸關系求遞歸關系 an-4