7.1一些數(shù)列算術(shù)序列（等差數(shù)列）幾何序列（等比數(shù)列）例1：確定平面一般位置上的n個互相交疊的圓所形成的區(qū)域數(shù)。7.1一些數(shù)列算術(shù)序列（等差數(shù)列）1例2

(Fibonacci問題):Fibonacci數(shù)列是遞推關(guān)系的又一典型問題,數(shù)列的本身有著許多應(yīng)用.(1)

問題的提出：假定初生的一對雌雄兔子,從出生的第2個月之后每個月都可以生出另外一對雌雄兔.如果第1個月只有一對初生的雌雄兔子,問n個月之后共有多少對兔子？例2(Fibonacci問題):21月2月3月4月1月2月3月4月35月6月5月6月4(2)

求遞推關(guān)系:設(shè)滿n個月時兔子對數(shù)為Fn,則第n-1個月留下的兔子數(shù)目為Fn-1對;當月新生兔數(shù)目為Fn-2對,即第n-2個月的所有兔子到第n個月都有繁殖能力

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,前幾項為：0，1，1，2，3，5，8，13，21，34，55，89，144，233，…(2)求遞推關(guān)系:設(shè)滿n個月時兔子對數(shù)為Fn,則第n-15(3)

Fibonacci數(shù)列的性質(zhì)部分和Sn=f0+f1+f2+…+fn=fn+2-1Fibonacci數(shù)列是偶數(shù)當且僅當n能被3整除Fibonacci數(shù)列滿足公式(3)Fibonacci數(shù)列的性質(zhì)6例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：確定用單牌和多米諾骨牌對1Xn棋盤完美覆蓋的方法數(shù)bn。例3：令g0,g1,g2,…,gn,…是滿足下面給出的Fib7定理7.1.2沿Pascal三角形左下到右上對角線上的二項式系數(shù)的和是Fibonacci數(shù)定理7.1.2沿Pascal三角形左下到右上對角線上的二項87.2線性齊次遞推關(guān)系數(shù)列h0,h1,h2,…,hn,…h(huán)n=a1hn-1+a2hn-2+…+akhn-k+bn(n≥k)錯排數(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)7.2線性齊次遞推關(guān)系數(shù)列h0,h1,h2,…,hn,…9hn=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)的解，當且僅當q是多項式方程xk-a1xk-1-a2xk-2-…-ak=0的一個根。如果多項式方程有k個不同的根q1,q2,…,qk，則hn=c1q1n+c2q2n+…+ckqknhn=a1hn-1+a2hn-2+…+akhn-k(n≥k10例6：求滿足初始值h0=1,h1=2,h2=0的遞推關(guān)系hn=2hn-1+hn-2-2hn-3(n≥3)的解例7：只由三個字母a,b,c組成的長度為n的一些單詞將在通信信道上傳輸，滿足條件：傳輸中不得有兩個a連續(xù)出現(xiàn)在任一單詞中。確定通信信道允許傳輸?shù)膯卧~個數(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)的特征方程的互異的根。此時，如果qi是si重根，則對qi部分一般解為Hn(i)=(c1+c2n+…+csinsi-1)qin例6：求滿足初始值h0=1,h1=2,h2=0的遞推關(guān)系hn117.3非齊次遞推關(guān)系例9(Hanoi塔問題)：n個圓盤依其半徑大小,從下而上套在柱A上,如圖3.1所示.每次只允許取一個轉(zhuǎn)移到柱B或C上,而且不允許大盤放在小盤上方.若要求把A上的n個盤轉(zhuǎn)移到C柱上.請設(shè)計一種方法,并估計要移動幾個盤次.現(xiàn)在只有A,B,C三根柱子可供使用.

7.3非齊次遞推關(guān)系例9(Hanoi塔問題)：n個圓盤依12圖ABC4132Hanoi塔是個經(jīng)典問題.對于這個問題,我們先要設(shè)計算法,進而估計算法的計算復(fù)雜性,這里就是移動的總次數(shù).圖ABC4132Hanoi塔是個經(jīng)典問題.對于這個問題,13(1)算法設(shè)計：n=2時,圓盤1從A套在B上；把圓盤2從A轉(zhuǎn)移到C上；把圓盤1從B上轉(zhuǎn)移到C上.完畢.n=3時,把圓盤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的演示過程.(1)算法設(shè)計：14ABCABC15假定n-1個盤子的轉(zhuǎn)移算法已經(jīng)確定.對n個圓盤問題,先把上面的圓盤1,2,…,

n-1轉(zhuǎn)移到B上,再把最后一個盤子轉(zhuǎn)移到C上,然后把B上的n-1個圓盤轉(zhuǎn)移到柱C上.轉(zhuǎn)移完畢.這運用的是遞歸算法n=2時給出了算法;n=3時先利用n=2時的算法把圓盤1,2移B上;再把圓盤3轉(zhuǎn)移到柱C上;再利用n=2時的算法把B上兩個圓盤轉(zhuǎn)移到柱C上.n=4,5,以此類推.

假定n-1個盤子的轉(zhuǎn)移算法已經(jīng)確定.16(2)

算法分析：令hn表示n個圓盤所需要的轉(zhuǎn)移次數(shù).根據(jù)算法先把前面n-1個盤子轉(zhuǎn)移到B上;然后把第n個盤子轉(zhuǎn)移到C上;最后再一次將B上的n-1個盤子轉(zhuǎn)到C上.算法可實現(xiàn)性可用歸納法得到.因n=2時對,假定n-1對,那么n自然也對.關(guān)于轉(zhuǎn)移次數(shù)容易得到一個遞歸關(guān)系:hn=2hn-1+1,h1=1.

(2)算法分析：令hn表示n個圓盤所需要的轉(zhuǎn)移次數(shù).根據(jù)17例10：解hn=3hn-1-4n(n≥1)h0=2步驟總結(jié)求齊次關(guān)系的一般解求非齊次關(guān)系的一個特解將一般解和特解聯(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例10：解hn=3hn-1-4n(n≥1)h0=2187.4生成函數(shù)（母函數(shù)）母函數(shù)就象一根曬衣繩,我們把需要得到的一列數(shù)就掛在它上面.假定我們的問題的解是一列數(shù):a0,a1,a2,,an,.我們想知道這個數(shù)列是什么,我們期望得到怎樣的答案?當然,最好的答案就是關(guān)于an的一個簡單的公式.比如諸如an=n2+3之類的表達式.即,通項公式.7.4生成函數(shù)（母函數(shù)）母函數(shù)就象一根曬衣繩,我們把需要19但是,如果一個未知數(shù)列沒有簡單公式,或者即便存在,但是很復(fù)雜,很不容易得到,我們也不知道,該怎么辦?如果我們還希望研究這個數(shù)列,討論它的性質(zhì),該如何下手?舉一個極端的例子,假定這個數(shù)列是2,

3,5,7,11,13,17,19,23,….,此處an是第n個素數(shù).這樣的情況,期望任何簡單的公式都是不合理的.

但是,如果一個未知數(shù)列沒有簡單公式,或者即便存在,但是20母函數(shù)把數(shù)列的所有成員用一種非常巧妙的方法聯(lián)系在一起,雖然這樣做并不一定能得到數(shù)列的簡單公式,可是也許能夠給出一個冪級數(shù)和的簡單公式,展開這個和函數(shù),所得到的冪級數(shù)的系數(shù)就是我們所要找的數(shù)列.比如后面我們將會學(xué)習(xí)到的Fibonacci數(shù)列,它滿足一個遞歸關(guān)系

Fn+1=Fn+Fn-1(n2;F1=F2=1).母函數(shù)把數(shù)列的所有成員用一種非常巧妙的方法聯(lián)系在一起,雖然211.

母函數(shù)概念

設(shè)有a,b,c三個不同的球,從中選取一個,或選a,或選b,或選c,把這些可能的選取形象地表示為a+b+c.類似地,從中選取二個,或選a和b,或選a和c,或選b和c.可形象地表示為ab+ac+bc,同樣,從中選取三個,只有一種方法,也可形象地表示為abc.1.母函數(shù)概念22從多項式

(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ù)是從三個球中選取i個的方法之形象表示.因子(1+ax)形象地指出,對球a,有兩種選取方法:不選a,或選a.因子(1+ax)中的1表示不選a,而x的系數(shù)a表示選a.從多項式23既然在上述多項式中,xi的系數(shù)表明選取i個球的方法,那么(1+ax)(1+bx)(1+cx)所表明的是:對a,b,c三球,選取的方法是,“選a或不選a”和“選b或不選b”以及“選c或不選c”.多項式中x的冪次表示選取球的個數(shù),而其相應(yīng)系數(shù)表示一切可能的選取方法.

既然在上述多項式中,xi的系數(shù)表明選取i個球的方法,那么24如果我們只關(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.

如果我們只關(guān)心不同組合方案的數(shù)目,不關(guān)心各種方案的羅列.25(7.3)就是一個關(guān)于形式變量x的冪函數(shù),這個冪函數(shù)中不同冪次的系數(shù)都是一個組合數(shù).這可以推廣到任意n個不同球所有可能組合的方案數(shù)情況.這其實就是我們大家熟悉的二項式系數(shù).不過現(xiàn)在我們是用形式級數(shù)的觀點來看問題.利用這種形式級數(shù)不僅僅是一種不同的表達形式,還非常有用.(7.3)就是一個關(guān)于形式變量x的冪函數(shù),這個冪函數(shù)中不同262.

母函數(shù)定義定義7.1利用給定序列a0,a1,a2,所構(gòu)造的函數(shù)

F(x)=a0+a1x+a2x2+

稱為序列a0,a1,a2,的母函數(shù).

母函數(shù)定義中的級數(shù)是形式冪級數(shù),不必關(guān)心收斂性,x只是一個形式變量.有限序列a0,a1,,an也可以定義它的母函數(shù).(后面添加0)2.母函數(shù)定義273.母函數(shù)的運算設(shè)序列{ai}的母函數(shù)A(x)=aixi,{bi}的母函數(shù)為B(x)=bixi.運算定義如下:(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

3.母函數(shù)的運算28(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).(顯然兩者互為逆.)(5)相乘:A(x)B(x)=cixi,其中29例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)的冪級數(shù)展開式是完全一致的.例14設(shè)F(x)=1+x+x2+,G(x)=1-x,30例15設(shè)則(F(x)-G(x))(1-3x+2x2)=x.這說明這與把它們看成普通函數(shù)的運算是一致的.例15設(shè)則(F(x)-G(x))(1-3x+2x2)=x.31例16：令k是一個整數(shù)，并令序列h0,h1,h2,…,hn,…使hn等于e1+e2+…+ek=n的非負整數(shù)解的個數(shù)。例17：確定蘋果、香蕉、橘子和梨的n組合的個數(shù)，其中在每個n組合中蘋果的個數(shù)是偶數(shù)，香蕉的個數(shù)是奇數(shù)，橘子的個數(shù)在0和4之間，而且至少要有一個梨。例18：確定可以由蘋果、香蕉、橘子和梨袋裝水果的袋數(shù)hn，其中在每個袋子中蘋果數(shù)是偶數(shù)，香蕉數(shù)是5的倍數(shù)，橘子數(shù)最多是4個，梨的個數(shù)為0或1。例16：令k是一個整數(shù)，并令序列h0,h1,h2,…,hn,32例19：確定方程e1+e2+…+ek=n的非負奇整數(shù)解e1,e2,…,ek的個數(shù)hn的母函數(shù)。例20：令hn表示方程3e1+4e2+2e3+5e4=n的非負整數(shù)解的個數(shù)。求h0,h1,h2,…,hn,…的母函數(shù)g(x)。例21：有無限多現(xiàn)成的一分、五分、一角、兩角五分和五角的硬幣。確定用這些硬幣湊成n分錢方法數(shù)hn的母函數(shù)g(x)。例19：確定方程e1+e2+…+ek=n的非負奇整數(shù)解e1,337.5母函數(shù)與遞歸例22(Hanoi塔問題)：hn=2hn-1+1,h1=1.

(7.4)令H(x)=h1x+h2x2+h3x3+H(x)是序列h1,h2,h3,的母函數(shù).給出了序列,就可確定對應(yīng)的母函數(shù).反過來也一樣,求得了母函數(shù),對應(yīng)得序列也就可得而知.當然,利用遞推關(guān)系(7.4)也可迭代求得h2,h3,.但現(xiàn)在我們一要尋找明確的公式,二要顯示母函數(shù)的作用.7.5母函數(shù)與遞歸例22(Hanoi塔問題)：hn=2h34令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)令H(x)=h1x+h2x2+h3x3++hnxn+35這就是轉(zhuǎn)移次數(shù)數(shù)列的母函數(shù).但是我們希望得到顯式表達式.這不難做到.可以從母函數(shù)的冪級數(shù)展開式中求得數(shù)列h1,h2,h3,.我們下面所運用的方法是處理這種問題的一個常規(guī)的方法,初看起來可能感覺不太適應(yīng),用多了就習(xí)以為常了.這就是所謂的部分分數(shù)的算法.

這就是轉(zhuǎn)移次數(shù)數(shù)列的母函數(shù).36(A+B)-(2A+B)x=x.解得A=-1,B=1.其實一眼就可看出結(jié)果.這里只是想說明方法而已.(A+B)-(2A+B)x=x.解得A=-1,B=1.37第7章-遞推關(guān)系和生成函數(shù)課件38(3)

算法評價:

hn是要移動圓盤數(shù)n(規(guī)模)的指數(shù)函數(shù),以n=60為例子.可以計算出260

1.152921018.這個數(shù)是一個什么概念?假如你每秒鐘移動一個盤,按照上述算法,你移動60個盤的時間是:(3)算法評價:hn是要移動圓盤數(shù)n(規(guī)模)的指數(shù)函數(shù)39真是不算不知道,一算嚇一跳.n=60,數(shù)不過百,2也是很小的整數(shù),可是260卻是一個很大的數(shù).這就是所謂的“指數(shù)爆炸”現(xiàn)象.一般稱復(fù)雜性為規(guī)模n的指數(shù)函數(shù)的算法為“壞算法”.好算法是指多項式算法或者線性算法.真是不算不知道,一算嚇一跳.n=60,數(shù)不過百,2也40例23：確定平方項序列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的一般公式。例23：確定平方項序列0,1,4,…,n2,…的母函數(shù)41定理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ù)項的k次多項式，p(x)是小于k次的多項式。反之也成立。定理7.5.1令h0,h1,…,hn,…為滿足k階常系數(shù)線42一般母函數(shù)是用基函數(shù){1,x,x2,…}來定義的.這種母函數(shù)對于組合類型的數(shù)列的研究很有用.但是,對研究排列類型的數(shù)列用起來很不方便.排列類型數(shù)列是用基函數(shù){1,x,x2/2!,…}來定義,這樣使用起來更方便一些.基本思想并沒有變,只是選擇了新的基.7.6指數(shù)生成函數(shù)一般母函數(shù)是用基函數(shù){1,x,x2,…}來定義的.7.643基函數(shù)正好是出現(xiàn)在函數(shù)ex的冪級數(shù)展開式中的函數(shù):設(shè)有數(shù)列a0,a1,a2,…，則稱下列函數(shù)為該數(shù)列的指數(shù)型母函數(shù):基函數(shù)正好是出現(xiàn)在函數(shù)ex的冪級數(shù)展開式中的函數(shù):設(shè)有數(shù)列a44構(gòu)造指數(shù)型母函數(shù)的目的是為了使得母函數(shù)形式更簡單,尤其對排列類型的遞歸數(shù)列更是如此.看幾個簡單例子.例26設(shè)n為正整數(shù),則數(shù)列P(n,0),P(n,1),P(n,2),…,P(n,n)的指數(shù)型母函數(shù)為:其普通型母函數(shù)如何?構(gòu)造指數(shù)型母函數(shù)的目的是為了使得母函數(shù)形式更簡單,尤其對排45例27數(shù)列1,1,1,…的指數(shù)型母函數(shù)為更一般的,設(shè)a為任意實數(shù),數(shù)列a0=1,a1,a2,a3,…的指數(shù)型母函數(shù)為例27數(shù)列1,1,1,…的指數(shù)型母函數(shù)為更一般的,設(shè)a為46(a)設(shè)n=n1+n2+…+nk.若元素a1有n1個,元素a2有n2個,…,元素ak有nk個,則由這n個元素組成的不同的排列總數(shù)為(b)設(shè)n=n1+n2+…+nk.若元素a1有n1個,元素a2有n2個,…,元素ak有nk個,由這n個元素中取r個排列數(shù)為pr,則序列p0,

p1,…,pn的指數(shù)型母函數(shù)為:(a)設(shè)n=n1+n2+…+nk.若元素a1有n1個,47xr項的系數(shù)為ar=pr/r!.

pr=ar·r!xr項的系數(shù)48定理令S為多重集{n1.a1,n2.a2,…,nk.ak},其中n1,n2,…,nk均為非負整數(shù)。令hn是S的n排列數(shù)，則序列h1,h2,…,hn…的指數(shù)生成函數(shù)由 給定，其中，定理令S為多重集{n1.a1,n2.a2,…,nk.ak}49例28若有8個元素,其中設(shè)a1重復(fù)3次，a2重復(fù)2次,a3重復(fù)3次.從中取r個元素的排列數(shù)pr,則序列p0,p1,p2,…,p8的指數(shù)型母函數(shù)為:如何得出pr?例如：p4=4!(35/12)=70.例28若有8個元素,其中設(shè)a1重復(fù)3次，a2重復(fù)2次,50例29確定用紅、綠、藍三色對1n棋盤的方格進行染色的方案數(shù)an,并且使得綠色的方格數(shù)為偶數(shù).

解約定a0=1.顯然

an為三種顏色組成的n階排列,每種顏色的重復(fù)數(shù)沒有限制,但是綠色在排列中必須出現(xiàn)偶數(shù)次.這樣{an}的指數(shù)型母函數(shù)為例29確定用紅、綠、藍三色對1n棋盤的方格進行染色的方51例30：令hn表示數(shù)字1，2或3組成的n位數(shù)字數(shù)的個數(shù)，其中1的個數(shù)為偶數(shù)，2的個數(shù)至少是3，3的個數(shù)最多是4。確定結(jié)果數(shù)列h1,h2,…,hn…的指數(shù)生成函數(shù)。例31：確定每位數(shù)字都是奇數(shù)的n位數(shù)的個數(shù)hn

，其中1和3出現(xiàn)偶數(shù)次。例32：確定用紅色、白色和藍色對1行n列棋盤的方格涂色的方法數(shù)hn，其中紅方格的個數(shù)是偶數(shù)并且至少有一個藍方格。例30：令hn表示數(shù)字1，2或3組成的n位數(shù)字數(shù)的個數(shù)，其中52例33一個凸n邊形,通過不相交于n邊形內(nèi)部的對角線,把n邊形拆分成若干三角形,不同拆分的數(shù)目用hn表之.五邊形有如下五種拆分方案,故h5=5.7.7一個幾何的例子例33一個凸n邊形,通過不相交于n邊形內(nèi)部的對角線,把53精品課件！精品課件！54精品課件！精品課件！55定理通過畫出區(qū)域內(nèi)部不相交的對角線將具有n+1條邊的凸多邊形區(qū)域分割成三角形區(qū)域，令hn表示分成三角形區(qū)域的方法數(shù)。定義h1=1。則hn滿足遞推關(guān)系該遞推關(guān)系的解為定理通過畫出區(qū)域內(nèi)部不相交的對角線將具有n+1條邊的凸多邊567.1一些數(shù)列算術(shù)序列（等差數(shù)列）幾何序列（等比數(shù)列）例1：確定平面一般位置上的n個互相交疊的圓所形成的區(qū)域數(shù)。7.1一些數(shù)列算術(shù)序列（等差數(shù)列）57例2

(Fibonacci問題):Fibonacci數(shù)列是遞推關(guān)系的又一典型問題,數(shù)列的本身有著許多應(yīng)用.(1)

問題的提出：假定初生的一對雌雄兔子,從出生的第2個月之后每個月都可以生出另外一對雌雄兔.如果第1個月只有一對初生的雌雄兔子,問n個月之后共有多少對兔子？例2(Fibonacci問題):581月2月3月4月1月2月3月4月595月6月5月6月60(2)

求遞推關(guān)系:設(shè)滿n個月時兔子對數(shù)為Fn,則第n-1個月留下的兔子數(shù)目為Fn-1對;當月新生兔數(shù)目為Fn-2對,即第n-2個月的所有兔子到第n個月都有繁殖能力

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,前幾項為：0，1，1，2，3，5，8，13，21，34，55，89，144，233，…(2)求遞推關(guān)系:設(shè)滿n個月時兔子對數(shù)為Fn,則第n-161(3)

Fibonacci數(shù)列的性質(zhì)部分和Sn=f0+f1+f2+…+fn=fn+2-1Fibonacci數(shù)列是偶數(shù)當且僅當n能被3整除Fibonacci數(shù)列滿足公式(3)Fibonacci數(shù)列的性質(zhì)62例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：確定用單牌和多米諾骨牌對1Xn棋盤完美覆蓋的方法數(shù)bn。例3：令g0,g1,g2,…,gn,…是滿足下面給出的Fib63定理7.1.2沿Pascal三角形左下到右上對角線上的二項式系數(shù)的和是Fibonacci數(shù)定理7.1.2沿Pascal三角形左下到右上對角線上的二項647.2線性齊次遞推關(guān)系數(shù)列h0,h1,h2,…,hn,…h(huán)n=a1hn-1+a2hn-2+…+akhn-k+bn(n≥k)錯排數(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)7.2線性齊次遞推關(guān)系數(shù)列h0,h1,h2,…,hn,…65hn=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)的解，當且僅當q是多項式方程xk-a1xk-1-a2xk-2-…-ak=0的一個根。如果多項式方程有k個不同的根q1,q2,…,qk，則hn=c1q1n+c2q2n+…+ckqknhn=a1hn-1+a2hn-2+…+akhn-k(n≥k66例6：求滿足初始值h0=1,h1=2,h2=0的遞推關(guān)系hn=2hn-1+hn-2-2hn-3(n≥3)的解例7：只由三個字母a,b,c組成的長度為n的一些單詞將在通信信道上傳輸，滿足條件：傳輸中不得有兩個a連續(xù)出現(xiàn)在任一單詞中。確定通信信道允許傳輸?shù)膯卧~個數(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)的特征方程的互異的根。此時，如果qi是si重根，則對qi部分一般解為Hn(i)=(c1+c2n+…+csinsi-1)qin例6：求滿足初始值h0=1,h1=2,h2=0的遞推關(guān)系hn677.3非齊次遞推關(guān)系例9(Hanoi塔問題)：n個圓盤依其半徑大小,從下而上套在柱A上,如圖3.1所示.每次只允許取一個轉(zhuǎn)移到柱B或C上,而且不允許大盤放在小盤上方.若要求把A上的n個盤轉(zhuǎn)移到C柱上.請設(shè)計一種方法,并估計要移動幾個盤次.現(xiàn)在只有A,B,C三根柱子可供使用.

7.3非齊次遞推關(guān)系例9(Hanoi塔問題)：n個圓盤依68圖ABC4132Hanoi塔是個經(jīng)典問題.對于這個問題,我們先要設(shè)計算法,進而估計算法的計算復(fù)雜性,這里就是移動的總次數(shù).圖ABC4132Hanoi塔是個經(jīng)典問題.對于這個問題,69(1)算法設(shè)計：n=2時,圓盤1從A套在B上；把圓盤2從A轉(zhuǎn)移到C上；把圓盤1從B上轉(zhuǎn)移到C上.完畢.n=3時,把圓盤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的演示過程.(1)算法設(shè)計：70ABCABC71假定n-1個盤子的轉(zhuǎn)移算法已經(jīng)確定.對n個圓盤問題,先把上面的圓盤1,2,…,

n-1轉(zhuǎn)移到B上,再把最后一個盤子轉(zhuǎn)移到C上,然后把B上的n-1個圓盤轉(zhuǎn)移到柱C上.轉(zhuǎn)移完畢.這運用的是遞歸算法n=2時給出了算法;n=3時先利用n=2時的算法把圓盤1,2移B上;再把圓盤3轉(zhuǎn)移到柱C上;再利用n=2時的算法把B上兩個圓盤轉(zhuǎn)移到柱C上.n=4,5,以此類推.

假定n-1個盤子的轉(zhuǎn)移算法已經(jīng)確定.72(2)

算法分析：令hn表示n個圓盤所需要的轉(zhuǎn)移次數(shù).根據(jù)算法先把前面n-1個盤子轉(zhuǎn)移到B上;然后把第n個盤子轉(zhuǎn)移到C上;最后再一次將B上的n-1個盤子轉(zhuǎn)到C上.算法可實現(xiàn)性可用歸納法得到.因n=2時對,假定n-1對,那么n自然也對.關(guān)于轉(zhuǎn)移次數(shù)容易得到一個遞歸關(guān)系:hn=2hn-1+1,h1=1.

(2)算法分析：令hn表示n個圓盤所需要的轉(zhuǎn)移次數(shù).根據(jù)73例10：解hn=3hn-1-4n(n≥1)h0=2步驟總結(jié)求齊次關(guān)系的一般解求非齊次關(guān)系的一個特解將一般解和特解聯(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例10：解hn=3hn-1-4n(n≥1)h0=2747.4生成函數(shù)（母函數(shù)）母函數(shù)就象一根曬衣繩,我們把需要得到的一列數(shù)就掛在它上面.假定我們的問題的解是一列數(shù):a0,a1,a2,,an,.我們想知道這個數(shù)列是什么,我們期望得到怎樣的答案?當然,最好的答案就是關(guān)于an的一個簡單的公式.比如諸如an=n2+3之類的表達式.即,通項公式.7.4生成函數(shù)（母函數(shù)）母函數(shù)就象一根曬衣繩,我們把需要75但是,如果一個未知數(shù)列沒有簡單公式,或者即便存在,但是很復(fù)雜,很不容易得到,我們也不知道,該怎么辦?如果我們還希望研究這個數(shù)列,討論它的性質(zhì),該如何下手?舉一個極端的例子,假定這個數(shù)列是2,

3,5,7,11,13,17,19,23,….,此處an是第n個素數(shù).這樣的情況,期望任何簡單的公式都是不合理的.

但是,如果一個未知數(shù)列沒有簡單公式,或者即便存在,但是76母函數(shù)把數(shù)列的所有成員用一種非常巧妙的方法聯(lián)系在一起,雖然這樣做并不一定能得到數(shù)列的簡單公式,可是也許能夠給出一個冪級數(shù)和的簡單公式,展開這個和函數(shù),所得到的冪級數(shù)的系數(shù)就是我們所要找的數(shù)列.比如后面我們將會學(xué)習(xí)到的Fibonacci數(shù)列,它滿足一個遞歸關(guān)系

Fn+1=Fn+Fn-1(n2;F1=F2=1).母函數(shù)把數(shù)列的所有成員用一種非常巧妙的方法聯(lián)系在一起,雖然771.

母函數(shù)概念

設(shè)有a,b,c三個不同的球,從中選取一個,或選a,或選b,或選c,把這些可能的選取形象地表示為a+b+c.類似地,從中選取二個,或選a和b,或選a和c,或選b和c.可形象地表示為ab+ac+bc,同樣,從中選取三個,只有一種方法,也可形象地表示為abc.1.母函數(shù)概念78從多項式

(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ù)是從三個球中選取i個的方法之形象表示.因子(1+ax)形象地指出,對球a,有兩種選取方法:不選a,或選a.因子(1+ax)中的1表示不選a,而x的系數(shù)a表示選a.從多項式79既然在上述多項式中,xi的系數(shù)表明選取i個球的方法,那么(1+ax)(1+bx)(1+cx)所表明的是:對a,b,c三球,選取的方法是,“選a或不選a”和“選b或不選b”以及“選c或不選c”.多項式中x的冪次表示選取球的個數(shù),而其相應(yīng)系數(shù)表示一切可能的選取方法.

既然在上述多項式中,xi的系數(shù)表明選取i個球的方法,那么80如果我們只關(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.

如果我們只關(guān)心不同組合方案的數(shù)目,不關(guān)心各種方案的羅列.81(7.3)就是一個關(guān)于形式變量x的冪函數(shù),這個冪函數(shù)中不同冪次的系數(shù)都是一個組合數(shù).這可以推廣到任意n個不同球所有可能組合的方案數(shù)情況.這其實就是我們大家熟悉的二項式系數(shù).不過現(xiàn)在我們是用形式級數(shù)的觀點來看問題.利用這種形式級數(shù)不僅僅是一種不同的表達形式,還非常有用.(7.3)就是一個關(guān)于形式變量x的冪函數(shù),這個冪函數(shù)中不同822.

母函數(shù)定義定義7.1利用給定序列a0,a1,a2,所構(gòu)造的函數(shù)

F(x)=a0+a1x+a2x2+

稱為序列a0,a1,a2,的母函數(shù).

母函數(shù)定義中的級數(shù)是形式冪級數(shù),不必關(guān)心收斂性,x只是一個形式變量.有限序列a0,a1,,an也可以定義它的母函數(shù).(后面添加0)2.母函數(shù)定義833.母函數(shù)的運算設(shè)序列{ai}的母函數(shù)A(x)=aixi,{bi}的母函數(shù)為B(x)=bixi.運算定義如下:(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

3.母函數(shù)的運算84(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).(顯然兩者互為逆.)(5)相乘:A(x)B(x)=cixi,其中85例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)的冪級數(shù)展開式是完全一致的.例14設(shè)F(x)=1+x+x2+,G(x)=1-x,86例15設(shè)則(F(x)-G(x))(1-3x+2x2)=x.這說明這與把它們看成普通函數(shù)的運算是一致的.例15設(shè)則(F(x)-G(x))(1-3x+2x2)=x.87例16：令k是一個整數(shù)，并令序列h0,h1,h2,…,hn,…使hn等于e1+e2+…+ek=n的非負整數(shù)解的個數(shù)。例17：確定蘋果、香蕉、橘子和梨的n組合的個數(shù)，其中在每個n組合中蘋果的個數(shù)是偶數(shù)，香蕉的個數(shù)是奇數(shù)，橘子的個數(shù)在0和4之間，而且至少要有一個梨。例18：確定可以由蘋果、香蕉、橘子和梨袋裝水果的袋數(shù)hn，其中在每個袋子中蘋果數(shù)是偶數(shù)，香蕉數(shù)是5的倍數(shù)，橘子數(shù)最多是4個，梨的個數(shù)為0或1。例16：令k是一個整數(shù)，并令序列h0,h1,h2,…,hn,88例19：確定方程e1+e2+…+ek=n的非負奇整數(shù)解e1,e2,…,ek的個數(shù)hn的母函數(shù)。例20：令hn表示方程3e1+4e2+2e3+5e4=n的非負整數(shù)解的個數(shù)。求h0,h1,h2,…,hn,…的母函數(shù)g(x)。例21：有無限多現(xiàn)成的一分、五分、一角、兩角五分和五角的硬幣。確定用這些硬幣湊成n分錢方法數(shù)hn的母函數(shù)g(x)。例19：確定方程e1+e2+…+ek=n的非負奇整數(shù)解e1,897.5母函數(shù)與遞歸例22(Hanoi塔問題)：hn=2hn-1+1,h1=1.

(7.4)令H(x)=h1x+h2x2+h3x3+H(x)是序列h1,h2,h3,的母函數(shù).給出了序列,就可確定對應(yīng)的母函數(shù).反過來也一樣,求得了母函數(shù),對應(yīng)得序列也就可得而知.當然,利用遞推關(guān)系(7.4)也可迭代求得h2,h3,.但現(xiàn)在我們一要尋找明確的公式,二要顯示母函數(shù)的作用.7.5母函數(shù)與遞歸例22(Hanoi塔問題)：hn=2h90令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)令H(x)=h1x+h2x2+h3x3++hnxn+91這就是轉(zhuǎn)移次數(shù)數(shù)列的母函數(shù).但是我們希望得到顯式表達式.這不難做到.可以從母函數(shù)的冪級數(shù)展開式中求得數(shù)列h1,h2,h3,.我們下面所運用的方法是處理這種問題的一個常規(guī)的方法,初看起來可能感覺不太適應(yīng),用多了就習(xí)以為常了.這就是所謂的部分分數(shù)的算法.

這就是轉(zhuǎn)移次數(shù)數(shù)列的母函數(shù).92(A+B)-(2A+B)x=x.解得A=-1,B=1.其實一眼就可看出結(jié)果.這里只是想說明方法而已.(A+B)-(2A+B)x=x.解得A=-1,B=1.93第7章-遞推關(guān)系和生成函數(shù)課件94(3)

算法評價:

hn是要移動圓盤數(shù)n(規(guī)模)的指數(shù)函數(shù),以n=60為例子.可以計算出260

1.152921018.這個數(shù)是一個什么概念?假如你每秒鐘移動一個盤,按照上述算法,你移動60個盤的時間是:(3)算法評價:hn是要移動圓盤數(shù)n(規(guī)模)的指數(shù)函數(shù)95真是不算不知道,一算嚇一跳.n=60,數(shù)不過百,2也是很小的整數(shù),可是260卻是一個很大的數(shù).這就是所謂的“指數(shù)爆炸”現(xiàn)象.一般稱復(fù)雜性為規(guī)模n的指數(shù)函數(shù)的算法為“壞算法”.好算法是指多項式算法或者線性算法.真是不算不知道,一算嚇一跳.n=60,數(shù)不過百,2也96例23：確定平方項序列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的一般公式。例23：確定平方項序列0,1,4,…,n2,…的母函數(shù)97定理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)