《組合數(shù)學(xué)課件--第二章第三節(jié)關(guān)于線性常系數(shù)非齊次遞推關(guān)系.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《組合數(shù)學(xué)課件--第二章第三節(jié)關(guān)于線性常系數(shù)非齊次遞推關(guān)系.ppt（36頁珍藏版）》請(qǐng)?jiān)趨R文網(wǎng)上搜索。

1、第第2章章 遞推關(guān)系與母函數(shù)遞推關(guān)系與母函數(shù) 2.1 2.1 遞推關(guān)系遞推關(guān)系 2.2 2.2 母函數(shù)母函數(shù)(生成函數(shù)生成函數(shù))2.3 Fibonacci 2.3 Fibonacci數(shù)列數(shù)列 2.4 2.4 優(yōu)選法與優(yōu)選法與FibonacciFibonacci序列的應(yīng)用序列的應(yīng)用 2.5 2.5 母函數(shù)的性質(zhì)母函數(shù)的性質(zhì) 2.6 2.6 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系 2.7 2.7 關(guān)于常系數(shù)非齊次遞推關(guān)系關(guān)于常系數(shù)非齊次遞推關(guān)系 2.8 2.8 整數(shù)的拆分整數(shù)的拆分 2.9 2.9 ferrersferrers圖像圖像 2.10 2.10 拆分?jǐn)?shù)估計(jì)拆分?jǐn)?shù)估計(jì) 2.11 2.

2、11 指數(shù)型母函數(shù)指數(shù)型母函數(shù) 2.12 2.12 廣義二項(xiàng)式定理廣義二項(xiàng)式定理 2.13 2.13 應(yīng)用舉例應(yīng)用舉例 2.14 2.14 非線性遞推關(guān)系舉例非線性遞推關(guān)系舉例 2.15 2.15 遞推關(guān)系解法的補(bǔ)充遞推關(guān)系解法的補(bǔ)充12.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系如下面的遞推關(guān)系：如下面的遞推關(guān)系：稱為稱為k階線性遞推關(guān)系，其中若階線性遞推關(guān)系，其中若c1,c2,ck都是常數(shù)，則稱為常系數(shù)線性都是常數(shù)，則稱為常系數(shù)線性遞推關(guān)系，若遞推關(guān)系，若bn=0，則則稱為是齊次的，否稱為是齊次的，否則為非齊次的。則為非齊次的。22.10任意階齊次遞推關(guān)系任意階齊次遞推關(guān)

3、系設(shè)設(shè)r1,r2,rs是線性常系數(shù)齊次遞推關(guān)系是線性常系數(shù)齊次遞推關(guān)系的不同的特征根，并設(shè)的不同的特征根，并設(shè)hi是是ri的重根的重根數(shù)，數(shù)，i=1,2,3,s。則。則3Fibonacci遞歸算法遞歸算法:int fibonacci(int n)if(n=1|n=2)return(1);else return(fibonacci(n-1)+fibonacci(n-2);2.1 遞推關(guān)系遞推關(guān)系時(shí)間復(fù)雜性：時(shí)間復(fù)雜性：f(n)=f(n-1)+f(n-2)+142.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系如果序列如果序列xn和和yn滿足滿足非齊次遞推關(guān)系，非齊次遞推關(guān)系，對(duì)應(yīng)的

4、齊次遞推關(guān)系。對(duì)應(yīng)的齊次遞推關(guān)系。則序列則序列zn=xn-yn滿足其對(duì)應(yīng)的齊次遞推關(guān)系。滿足其對(duì)應(yīng)的齊次遞推關(guān)系。證明：略證明：略52.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系特解與一般解特解與一般解:例例2：某人有：某人有n元錢，一次可買元錢，一次可買1元的礦泉水，也元的礦泉水，也可以買可以買2元的（啤酒、方便面）的一種，直到所元的（啤酒、方便面）的一種，直到所有的錢花完為止有的錢花完為止(買東西的順序不同，也算不同買東西的順序不同，也算不同方案方案)，求，求n元錢正好花完的買法方案數(shù)。元錢正好花完的買法方案數(shù)。解：遞推關(guān)系：解：遞推關(guān)系：an=an-1+2an-2 a1

5、=1,a2=3 特征方程特征方程x2-x-2=0的根的根r1=-1，r2=26 定理定理1 若若fn 是線性常系數(shù)非齊次遞推關(guān)系的特是線性常系數(shù)非齊次遞推關(guān)系的特解，則這個(gè)線性常系數(shù)非齊次遞推關(guān)系的解有如下解，則這個(gè)線性常系數(shù)非齊次遞推關(guān)系的解有如下形式形式：an=fn+對(duì)應(yīng)的線性常系數(shù)齊次遞推關(guān)系的解。對(duì)應(yīng)的線性常系數(shù)齊次遞推關(guān)系的解。證明：證明：fn是特解，設(shè)是特解，設(shè)sn 是一個(gè)解是一個(gè)解 令令tn=sn-fn 2.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系 則序列則序列ti是線性常系數(shù)齊次遞推關(guān)系的解是線性常系數(shù)齊次遞推關(guān)系的解 sn=tn+fn 證畢證畢72.7 關(guān)

6、于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系一階、二階線性常系數(shù)非齊次遞推關(guān)系一階、二階線性常系數(shù)非齊次遞推關(guān)系(1)右端項(xiàng)為常數(shù)右端項(xiàng)為常數(shù)han+ban-1=c(n)(2)右端項(xiàng)為右端項(xiàng)為hmn,h為為常數(shù)，常數(shù)，m為已知整數(shù)。為已知整數(shù)。an+ban-1+can-2=c(n)8下面討論若干特殊右端項(xiàng)的找特解的辦法。下面討論若干特殊右端項(xiàng)的找特解的辦法。(1)猜解法猜解法:猜猜an解的可能情況解的可能情況?2.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系an+ban-1=hmn,h為常數(shù)，為常數(shù)，m為已知整數(shù)。為已知整數(shù)。9下面討論若干特殊右端項(xiàng)的找特解的辦法。下

7、面討論若干特殊右端項(xiàng)的找特解的辦法。(1)猜解法猜解法:設(shè)設(shè)an=kmn2.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系an+ban-1=hmn,h為常數(shù)，為常數(shù)，m為已知整數(shù)。為已知整數(shù)。kmn+bkmn-1=hmn,km+bk=hm,m等于等于-b時(shí)無效時(shí)無效m是特征方程的根時(shí)無效是特征方程的根時(shí)無效10設(shè)設(shè)an=kmn2.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系an+ban-1+can-2=hmn,h為常數(shù)，為常數(shù)，m為已知整數(shù)。為已知整數(shù)。kmn+bkmn-1+ckmn-2=hmn,km2+bkm+ck=hm2,分母為零時(shí)無效分母為零時(shí)無效m是特征方

8、程的根時(shí)無效是特征方程的根時(shí)無效11例例1 假定特解為：假定特解為：兩邊同除兩邊同除以以4n-2：2.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系12特征方程特征方程2.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系13例例2 假定特解為：假定特解為：c3n,代入遞推關(guān)系。代入遞推關(guān)系。無解！對(duì)于無解！對(duì)于這種情況怎這種情況怎么處理么處理?2.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系14故導(dǎo)致二階齊次遞推關(guān)系，（故導(dǎo)致二階齊次遞推關(guān)系，（1）式的解必然）式的解必然是（是（2）式的解，但（）式的解，但（2）式解不一定是（）式解不一定是（1）式的解

9、。式的解。(2)劃為高階齊次遞推關(guān)系，通過比較推測(cè)遞劃為高階齊次遞推關(guān)系，通過比較推測(cè)遞推關(guān)系的特解推關(guān)系的特解 an-ban-1=hmn,an-1-ban-2=hmn-1,an-ban-1=hmn,(1)man-1-mban-2=hmn,an-(b+m)an-1+bman-2=0 （2）2.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系15若若b=m,則解為則解為:（2）式的特征方程是：）式的特征方程是：x2-(b+m)x+bm=0,它有兩個(gè)特征根它有兩個(gè)特征根b和和m。若若bm,則解為則解為:2.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系an=k1bn+k2

10、mn,an=(k1+k2n)mn,16分別討論如下：分別討論如下：(a)若若bm,則則an-ban-1=hmn 的解必可寫成如下形的解必可寫成如下形式式。an=k1bn+k2mn,定理定理1可知，非齊次遞推關(guān)系的解可表示為齊次遞可知，非齊次遞推關(guān)系的解可表示為齊次遞推關(guān)系的解加上特解推關(guān)系的解加上特解fn。比較可得：比較可得：fn=k2mn,k2是待定系數(shù)，是待定系數(shù)，代入遞推關(guān)系代入遞推關(guān)系an-ban-1=hmn，k2mn-bk2mn-1=hmnk2=hm/(m-b),因此因此fn=hm/(m-b)mn是特解是特解2.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系17解解:2

11、.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系例例3:18(b)(b)若若b=m,b=m,即即a an n-ba-ban-1n-1=hbhbn n其中其中b b和和h h都是已知常數(shù)。都是已知常數(shù)。但當(dāng)?shù)?dāng)b=m時(shí)，對(duì)應(yīng)的二階齊次遞時(shí)，對(duì)應(yīng)的二階齊次遞推關(guān)系推關(guān)系an-(b+m)an-1+bman-2=0的解為：的解為：an=(l+kn)bn2.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系所以所以fn=knbn令令an=knbn，an-1=k(n-1)bn-1代入遞推關(guān)系。代入遞推關(guān)系。knbn-k(n-1)bn=hbn,則則kn-k(n-1)=h,k=h,19

12、2.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系例例4:20因此：因此：那么特解為：那么特解為：例例5：特征方程為：特征方程為：與所對(duì)應(yīng)的二階齊次遞推關(guān)系的解比較與所對(duì)應(yīng)的二階齊次遞推關(guān)系的解比較:2.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系21將其代入非齊次遞推關(guān)系，得將其代入非齊次遞推關(guān)系，得可得可得k=3/5,因此特解為：因此特解為：2.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系22例例6：2.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系假設(shè)特解假設(shè)特解無解無解23例例6：2.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常

13、系數(shù)非齊次遞推關(guān)系假設(shè)特解假設(shè)特解24定理定理2 對(duì)于如下非齊次遞推關(guān)系。對(duì)于如下非齊次遞推關(guān)系。的特征方程：的特征方程：的的m重根，則遞推關(guān)系的特解有以下形式：重根，則遞推關(guān)系的特解有以下形式：若若b(n)是是p次多項(xiàng)式，如果次多項(xiàng)式，如果r是線性齊次遞推關(guān)系，是線性齊次遞推關(guān)系，2.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系 若若r不是不是K(x)=0的根，則特解是的根，則特解是m=0時(shí)的形式。時(shí)的形式。25例例7 an+3an-1-10an-2=(-7)nn 對(duì)應(yīng)的特征方程對(duì)應(yīng)的特征方程 有兩個(gè)特征根：有兩個(gè)特征根：2和和-5，-7不是特征根，故不是特征根，故m=0，按

14、定理，他的特解可寫為：，按定理，他的特解可寫為：代入遞推關(guān)系式：代入遞推關(guān)系式：2.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系26特解特解:因此一般解為：因此一般解為：2.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系27例例2.43 an-3an-1+2an-2=6n2，a0=6,a1=7 右端項(xiàng)右端項(xiàng)6n2可以看作是可以看作是(1)n 6n2,有兩個(gè)特征根：有兩個(gè)特征根：1和和2。m=1,p=2,代入遞推關(guān)系求出系數(shù)：代入遞推關(guān)系求出系數(shù)：2.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系*28 例題例題1:求長度為求長度為n的的0,1符號(hào)串，

15、不出現(xiàn)符號(hào)串，不出現(xiàn)00的符號(hào)串總數(shù)。的符號(hào)串總數(shù)。考慮一行考慮一行n列方格，用紅藍(lán)兩種顏色染色，列方格，用紅藍(lán)兩種顏色染色，不允許兩紅色方格相鄰。不允許兩紅色方格相鄰。2.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系2966.求矩陣求矩陣設(shè)第設(shè)第n-1項(xiàng)的乘積為項(xiàng)的乘積為解：解：2.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系30只要求出只要求出K即可即可2.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系31bmbm時(shí)時(shí)代入初值得代入初值得k=1k=12.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系32 64.64.從從n n個(gè)文

16、字中取個(gè)文字中取k k個(gè)文字作允許重復(fù)個(gè)文字作允許重復(fù)的排列，但不允許一個(gè)文字連續(xù)出現(xiàn)的排列，但不允許一個(gè)文字連續(xù)出現(xiàn)3 3次，求次，求這樣的排列的數(shù)目。這樣的排列的數(shù)目。2.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系 64.64.從從k k個(gè)文字中取個(gè)文字中取n n個(gè)文字作允許重復(fù)個(gè)文字作允許重復(fù)的排列，但不允許一個(gè)文字連續(xù)出現(xiàn)的排列，但不允許一個(gè)文字連續(xù)出現(xiàn)3 3次，求次，求這樣的排列的數(shù)目。這樣的排列的數(shù)目。33 首先，假設(shè)取首先，假設(shè)取n n個(gè)文字作允許重復(fù)的排列，個(gè)文字作允許重復(fù)的排列，不允許一個(gè)字連續(xù)出現(xiàn)不允許一個(gè)字連續(xù)出現(xiàn)3 3次的排列數(shù)為次的排列數(shù)為an,假設(shè)

17、取假設(shè)取n-1n-1個(gè)文字最后一位為個(gè)文字最后一位為x x，最后一，最后一位與位與x x不同的取法有不同的取法有(k-1)(k-1)種，種，(k-1)(k-1)an-1種。種。少算了最后一位也取少算了最后一位也取x x的情況，就是最的情況，就是最后兩位都是后兩位都是x x的情況，也就是最后兩位與倒的情況，也就是最后兩位與倒數(shù)第三位不同的情況，有數(shù)第三位不同的情況，有(k-1)(k-1)an-2種。種。2.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系342.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系35可求出可求出k1,k22.7 關(guān)于線性常系數(shù)非齊次遞推關(guān)系關(guān)于線性常系數(shù)非齊次遞推關(guān)系36