3章 遞推關(guān)系

1、第三章 遞推關(guān)系§3.1 基本概念（一） 遞推關(guān)系定義3.1.1 （隱式）對(duì)數(shù)列和任意自然數(shù)n，一個(gè)關(guān)系到和某些個(gè)的方程式，稱為遞推關(guān)系，記作 ()例 定義3.1.1（顯式） 對(duì)數(shù)列，把與其之前若干項(xiàng)聯(lián)系起來(lái)的等式對(duì)所有nk均成立（k為某個(gè)給定的自然數(shù)），稱該等式為的遞推關(guān)系，記為 ()例 （二） 分類（1） 按常量部分： 齊次遞推關(guān)系：指常量0，如； 非齊次遞推關(guān)系，即常量0，如。（2） 按的運(yùn)算關(guān)系： 線性關(guān)系，F(xiàn)是關(guān)于的線性函數(shù)，如（1）中的與均是如此； 非線性關(guān)系，F(xiàn)是的非線性函數(shù)，如。（3） 按的系數(shù)： 常系數(shù)遞推關(guān)系，如（1）中的與； 變系數(shù)遞推關(guān)系，如，之前的系數(shù)是隨著

2、n而變的。（4） 按數(shù)列的多少 一元遞推關(guān)系，其中的方程只涉及一個(gè)數(shù)列，如()和(3.1.1)均為一元的； 多元遞推關(guān)系，方程中涉及多個(gè)數(shù)列，如（5）顯式與隱式以上所給出的例子都是顯式的或者可以化為顯式關(guān)系（如（1）中的hn）。而在求微分方程的數(shù)值解時(shí)，還會(huì)碰到如下的隱式遞推關(guān)系：（三） 定解問題定義3.1.2 （定解問題）稱含有初始條件的遞推關(guān)系為定解問題，其一般形式為 ()所謂解遞推關(guān)系，就是指根據(jù)式(3.1.1)或(3.1.2)求an的與a0、a1、an1無(wú)關(guān)的解析表達(dá)式或數(shù)列an的母函數(shù)。（四） 例例3.1.1 （Hanoi塔問題）這是組合學(xué)中著名的問題。N個(gè)圓盤按從小到大的順序一次套

3、在柱A上，如圖所示。規(guī)定每次只能從一根柱子上搬動(dòng)一個(gè)圓盤到另一根柱子上，且要求在搬動(dòng)過程中不允許大盤放在小盤上，而且只有A、B、C三根柱子可供使用。用an表示將n個(gè)盤從柱A移到柱C上所需搬動(dòng)圓盤的最少次數(shù)，試建立數(shù)列的遞推關(guān)系。 A B C圖 Hanoi塔問題（解）易知，a11，a23，對(duì)于任何n3，現(xiàn)設(shè)計(jì)搬動(dòng)圓盤的算法如下：第一步，將套在柱A的上部的n1個(gè)盤按要求移到柱B上，共搬動(dòng)了次；第二步，將柱A上的最大一個(gè)盤移到柱C上，只要搬動(dòng)一次；第三步，再?gòu)闹鵅將n1個(gè)盤按要求移到柱C上，也要用次。由加法法則，an的定解問題為 ()例3.1.2 （Lancaster戰(zhàn)斗方程）兩軍打仗，每支軍隊(duì)在每

4、天戰(zhàn)斗結(jié)束時(shí)都清點(diǎn)人數(shù)，用a0和b0分別表示在戰(zhàn)斗打響前第一支和第二支軍隊(duì)的人數(shù)，用an和bn分別表示第一支和第二支軍隊(duì)在第n天戰(zhàn)斗結(jié)束時(shí)的人數(shù)，那么，an1an就表示第一支軍隊(duì)在第n天戰(zhàn)斗中損失的人數(shù)，同樣，bn1bn表示第二支軍隊(duì)在第n天戰(zhàn)斗中損失的人數(shù)。假設(shè)一支軍隊(duì)所減少的人數(shù)與另一支軍隊(duì)在每天戰(zhàn)斗開始前的人數(shù)成比例，因而有常數(shù)A和B，使得其中常量A、B是度量每支軍隊(duì)的武器系數(shù)，將上述等式改寫成 ()這是一個(gè)含有兩個(gè)未知量的一階線性遞歸關(guān)系組。例3.1.3 設(shè)，求an所滿足的遞推關(guān)系。（解）分兩種情況：當(dāng)n為偶數(shù)時(shí)，令n2m，則m1于是an可寫成an上式右端前兩項(xiàng)之和為而后兩項(xiàng)之和為于是

5、得當(dāng)n為奇數(shù)時(shí)，同樣可證上述遞推關(guān)系成立。因此，所滿足的遞推關(guān)系是， n2另外，顯然有a0a11。例3.1.4 設(shè)0出現(xiàn)偶數(shù)次的n位八進(jìn)制數(shù)共有個(gè)，0出現(xiàn)奇數(shù)次的數(shù)共有個(gè)。求和滿足的遞推關(guān)系。對(duì)0出現(xiàn)偶數(shù)次的n位八進(jìn)制數(shù)分兩種情況討論：（1）最高位是0，則其余n1位應(yīng)該含有奇數(shù)個(gè)0，這類八進(jìn)制數(shù)共有個(gè)。（2）最高位不是0，則其余n1位還應(yīng)該含有偶數(shù)個(gè)0，這類八進(jìn)制數(shù)共有7個(gè)。因此有7。同理可得7，所以、滿足例 n20出現(xiàn)偶數(shù)次的數(shù) 00，11，12，13，14，15，77，共50個(gè)0出現(xiàn)奇數(shù)次的數(shù) 01，10，02，20，03，30，70，共14個(gè)例3.1.5 用后退的Euler公式求常微分方

6、程的數(shù)值解。（解）函數(shù)y=y(x)在點(diǎn)xn處的真值記為y(xn)，近似值記為yn，求數(shù)值解即利用數(shù)值方法求y(x)在處xn的近似值yn（n=1,2,）。向前的Euler方法：，其中h=稱為步長(zhǎng)。 (xn+1,y(xn+1) (xn+1,yn+1) (xn,y(xn)向后的Euler方法：后退的Euler公式是指對(duì)常微分方程，當(dāng)已知函數(shù)y在處的值時(shí)，可通過解代數(shù)方程求得函數(shù)y在處的數(shù)值解，其中h是自變量x的步長(zhǎng)（n0,1,2,）。 (xn+1,yn+1) (xn+1,y(xn+1) (xn,y(xn)已知原方程為，代入Euler公式可得函數(shù)y的數(shù)值解為§3.2 常系數(shù)線性遞推關(guān)系常系數(shù)

7、的線性遞推關(guān)系總可以化為如下形式 ()或 ()分別稱為k階齊次遞推關(guān)系和k階非齊次遞推關(guān)系。其中f(n)稱為自由項(xiàng)。顯然，式（）至少有一個(gè)平凡解 ，而人們更關(guān)心的是它的非零解。其次，對(duì)于常系數(shù)線性遞推關(guān)系的定解問題，其解必是唯一的。解常系數(shù)遞推關(guān)系比較簡(jiǎn)單且有效的方法當(dāng)首推特征根法。其主要思想來(lái)源于解常系數(shù)線性微分方程，因?yàn)閮烧咴诮Y(jié)構(gòu)上很類似，所以其解的結(jié)構(gòu)和求解的方法也類似。§3.2.1 解的性質(zhì)性質(zhì)1. 設(shè)數(shù)列和是（）的解，則也是（3.2.1）之解。其中為任意常數(shù)。（證）由條件知，、分別滿足方程（），即 令r1×r2×得：（為書寫方便，此處特給定c01，下同）

8、。即也滿足方程（）。性質(zhì)1可以推廣到一般情形：設(shè)均為（）之解，則也是（3.2.1）的解。其中為任意常數(shù)。性質(zhì)2. 設(shè)和是（）的解，則是（3.2.1）的解。性質(zhì)3. 若是（）的解，是（3.2.2）的解，則是（3.2.2）的解。推廣到一般情形：設(shè)是（）的解，分別是（3.2.1）的解，則是（3.2.2）的解。性質(zhì)4. 設(shè)是遞推關(guān)系的解，是遞推關(guān)系的解，則是遞推關(guān)系的解。性質(zhì)24的證明與性質(zhì)1類似，請(qǐng)讀者自己完成。§3.2.2 解的結(jié)構(gòu)（一） 概念定義3.2.1 稱多項(xiàng)式C(x)為齊次遞推關(guān)系（）的特征多項(xiàng)式，相應(yīng)的代數(shù)方程C(x) 0 稱為（）的特征方程，特征方程的解稱為（3.2.1）的特

9、征根。（二） 結(jié)論定理3.2.1 數(shù)列anqn是（）的非零解的充分必要條件是q為（3.2.1）的特征根。（證） anqn是（）的解 q是方程C(x)0的根，即q是（）的特征根。意義：將求解常系數(shù)線性齊次遞推關(guān)系的問題轉(zhuǎn)化為常系數(shù)代數(shù)方程的求根問題，從而給出了一個(gè)實(shí)用且比較簡(jiǎn)單的解此類遞推關(guān)系的方法。（三） 通解定義3.2.2 若是（3.2.1）的不同解，且（3.2.1）的任何解都可以表為，則稱為（3.2.1）的通解。其中為任意常數(shù)。此處所說的不同解是指將每一個(gè)解都視為一個(gè)無(wú)窮維的解向量，而這些向量之間是線性無(wú)關(guān)的。說明 通解的特征： 通解首先是解； 組成通解的所有解向量線性無(wú)關(guān)； 任何一個(gè)具體

10、的解都被包容在通解中。§3.2.3 特征根法該方法的思路就是通過解式（）的特征方程，從而求得其特征根，再利用特征根即可獲得（3.2.1）的通解。根據(jù)特征根的不同分布情況，分為下述三種情形予以討論。（一） 特征根為單根情形設(shè)是（）的互不相同的特征根，則（3.2.1）的通解為 （）其中為任意常數(shù)（待定）。（證）首先由定理3.2.1知是方程（3.2.1）的解。且由性質(zhì)1知也是（3.2.1）的解。再證（）的所有解都可以表為（3.2.3）的形式。設(shè)是（3.2.1）的一個(gè)解，且滿足初始條件。令，代入初始條件，可得關(guān)于的線性方程組 （）其系數(shù)行列式為著名的范德蒙（Vandermonde）行列式：所

11、以式（）有唯一解。即一定可以表示為(3.2.3)的形式。由于的任意性，故知結(jié)論成立。例3.2.1 求遞推關(guān)系的通解。（解）特征方程為，解之得特征根， ， 通解為 其中，A、B、C為任意常數(shù)。若是定解問題，設(shè)初值為：，帶入通解得解得A0，B2，C3，故若初值為4，1，7，則求A、B、C的方程組為（二） 重根情形設(shè)特征方程有重根例3.2.2 求遞推關(guān)系的通解。（解）特征方程為，特征根是二重根，若按單根情形處理，有通解，即一個(gè)待定常數(shù)。要滿足兩個(gè)初始條件，一般是不可能的。其實(shí)質(zhì)在于按特征根確定的兩個(gè)解和是線性相關(guān)的，即?，F(xiàn)在的問題就是要找兩個(gè)線性無(wú)關(guān)的解和，使得.若令，可以驗(yàn)證是（）的解，且與線性無(wú)

12、關(guān)。同時(shí)，仿照單根情形，可以證明通解為一般情況下，設(shè)q是（）的k重根，則（3.2.1）的通解為 ()更一般的情形，若式（）有t個(gè)根，其中為重根，那么，通解應(yīng)為 ()（三） 復(fù)根情形 設(shè)特征方程有一對(duì)共軛（單）復(fù)根：，那么，通解中會(huì)出現(xiàn)這就是說，和也分別是（）的解（此二解與解是線性相關(guān)的，故不能構(gòu)成4個(gè)線性無(wú)關(guān)的解），且易知二者線性無(wú)關(guān)，故通解為 ()當(dāng)然，通解也可表為，但是，后者要涉及到復(fù)數(shù)運(yùn)算，前者卻避免了這一點(diǎn)。一般情形，若q是m重復(fù)根，自然也是m重復(fù)根，從而通解中必含有下面的項(xiàng)上述三種情形可以歸納成表.表特征根通解中對(duì)應(yīng)的項(xiàng)實(shí)根q為單根m重根復(fù) 根一對(duì)單復(fù)根一對(duì)m重復(fù)根例3.2.3 求定

13、解。（解）特征方程為q22q20解得q1±所以，因此，通解是代入初始條件，有解之得 A0，B1，故定解為，m0,1, 寫出解的數(shù)列，就是0，1，2，2，0，4，8，8，0，16，32，32，若用單根的方法：通解為，代入初值，有， 即故 例3.2.4 求定解（解）特征方程為0解之得特征根為q2，2，因此，通解是代入初始條件，有解之得 A3，B0，C1，D0，E1，故定解為=，n0,1, §3.2.4 非齊次方程（一） 結(jié)構(gòu)對(duì)于非齊次方程，比較有規(guī)律的解法主要是針對(duì)f(n)的幾種特殊情形。定理3.2.2 設(shè)是（）的一個(gè)特解，是（3.2.1）的通解，則的通解為 ()（證）首先由解

14、的性質(zhì)知，是()的解。其次，證明是通解。若給定一組初始條件a0 d0，a1d1，ak1dk1 (3.2.9)可以仿照齊次方程通解的證明方法，證得相應(yīng)于條件(3.2.9)的解一定可以表示為(3.2.8)的形式。（二） 待定系數(shù)法關(guān)于的求法已經(jīng)解決，這里的主要問題是求()的特解。遺憾的是尋求特解還沒有一般通用的方法。然而當(dāng)非齊次線性遞推關(guān)系的自由項(xiàng)f(n)比較簡(jiǎn)單時(shí)，采用下面的待定系數(shù)法比較方便。（一）f(n)b（b為常數(shù)）其中m表示1是的m重特征根（0mk）。當(dāng)然，若1不是特征根（即m0），則。（二）（b為常數(shù)）其中m表示b是的m重特征根（0mk）。同樣，若b不是特征根（即m0），則。（三），其

15、中為關(guān)于n的r次多項(xiàng)式，b為常數(shù)。其中是與同次的多項(xiàng)式，m仍然是b為特征根的重?cái)?shù)（0mk）。當(dāng)b不是特征根時(shí)（即m0），。（三） 例例3.2.5 求非齊次方程an13 an212an33的通解。（解）其相應(yīng)齊次方程的特征方程是 q313q120特征根為1，3，4，由于1是特征根，故有m1，其特解形式為AnA稱為待定系數(shù)，將An代入原非齊次方程得An13A(n2)12A(n3)3解之得 A，因此，所求通解為anB1B23 nB3(4) nn其中B1、B2、B3為任意常數(shù)。例3.2.6 求an4 an14an22n 的通解。（解）顯然，對(duì)應(yīng)齊次方程的特征根為q2（二重根），故特解形式為An2 2n

16、代入原非齊次方程求得待定系數(shù)A，因此，通解為anB1n 2nB22nn2 2n其中B1、B2為任意常數(shù)。例3.2.7 求an4 an1an2n(n1) 的通解。（解）此例中，b1，f(n)n2n，求得特征根為q12，q12b1不是特征根，故特解形式為An2 BnC將代入原非齊次方程，整理可得6An2 6(2AB)n2(4A3B3C)n2n比較等式兩邊同類項(xiàng)的系數(shù)，有A，B，C，因此，非齊次方程的通解為anB1B2其中B1、B2為任意常數(shù)。（四） 化非齊次方程為齊次方程例3.2.8 求.（解）（1）滿足的遞推關(guān)系顯然，滿足非齊次定解問題（2）化為齊次遞推關(guān)系改寫遞推關(guān)系為 那么，類似可得 得 同

17、理有 就得關(guān)于的齊次定解問題（3）求解q1是三重根。 （）代入初始條件得A0， ABC1， A2B3C3解之得A0， BC 這就利用遞推關(guān)系證明了求和公式（五） 一般求和公式（1）問題：求（2）化為齊次遞推關(guān)系求解首先，當(dāng)r1時(shí)，由（四）知當(dāng)r2時(shí)，可得 得 得 就得關(guān)于的齊次定解問題特征根仍然是q1（三重），所以再利用初值條件得（3）快速求常數(shù)A、B、C、D等當(dāng)r1時(shí)，令代入初始條件后得A0， AB1， A2B2C3解得 A0，B1，C 此處的方便主要體現(xiàn)在由關(guān)于A、B、C的第一個(gè)方程開始，可以逐步遞推地解出這些常數(shù)，實(shí)質(zhì)上并不需要解線性代數(shù)方程組。當(dāng)然，還可以令使得在利用初值確定A、B、C

18、時(shí)更加方便。因?yàn)檫@樣以來(lái)，下式第1、2、3個(gè)方程中分別關(guān)于A、B、C的系數(shù)恰好是1。A0， AB1， A2BC3從而易得A0， B1， C1當(dāng)r2時(shí)，可令代入初值得方程組A0， AB1， A2BC5， A3B3CD14從而易得A0， B1， C3， D2即對(duì)于較大的r，求部分和時(shí)，利用非齊次遞推關(guān)系求解還是要比將其化為齊次遞推關(guān)系方便得多。此外， （4）一般情形若通解為r階多項(xiàng)式，對(duì)定解問題（），可令使得用初值條件求解常數(shù)非常簡(jiǎn)單。§3.2.5 一般遞推關(guān)系的線性化對(duì)于某些非線性或變系數(shù)的遞推關(guān)系，可以將其化為線性關(guān)系來(lái)求解。例3.2.9 解定解問題 （解）此為線性變系數(shù)齊次關(guān)系。改

19、寫原方程為兩邊取對(duì)數(shù)得令，得關(guān)于的遞推關(guān)系再令，。先用迭代法求定解，易得，再求定解，可得。從而得 例3.2.10 解定解問題 （解）這是線性變系數(shù)非齊次關(guān)系。令得顯然，特征根q1。所以2不是特征根，特解。代入的遞推關(guān)系可得 ，即特解 通解 再由初始條件 知 定解 即例3.2.11 解定解問題 （解）本題的難點(diǎn)在于，不在前邊給出的三種類型之中。令， 則有由于q1為“1”重特征根，故特解。代入的遞推關(guān)系可得，即 特解為 通解為再由初始條件 知，即的通解為，從而的通解為另法：對(duì)于，可以用迭代法或直接觀察出，再用歸納法證明之即可。例3.2.12 解定解問題 （解）這是非線性的遞推關(guān)系，令，將問題變?yōu)椋?/p>

20、解之得，從而（an>0是顯然的）。§3.3 解遞推關(guān)系的其它方法§3.3.1 迭代法與歸納法對(duì)于某些特殊的，尤其是一階的遞推關(guān)系，使用迭代法求解可能更快。而有些遞推關(guān)系則可以通過觀察n比較小時(shí)的表達(dá)式的規(guī)律，總結(jié)或猜出的一般表達(dá)式，然后再用歸納法證明之即可。例3.3.1解 變換原遞推關(guān)系為 （）逐步迭代，得所以顯見當(dāng)n0時(shí)，上式仍成立，即滿足所給的初值，故定解問題的解為本題也可理解為利用式（）先做變量代換，得關(guān)于的遞推關(guān)系用迭代法解之得， 然后反代回去得， 例3.3.2 解遞推關(guān)系解 因，迭代得所以顯見當(dāng)n0時(shí)，上式仍成立，故定解問題的解為例3.3.3 。解 由題設(shè)所

21、以， ，當(dāng)k0時(shí)，上面兩個(gè)式子仍成立。故或，例3.3.4 用歸納法解遞推關(guān)系， 解 計(jì)算較小n時(shí)的，并觀察得由此可猜想=下面用歸納法證之：顯然n0，1，2，3時(shí)結(jié)論為真。假設(shè)n=k時(shí)結(jié)論為真，即=成立。 考慮n=k1時(shí)=結(jié)論成立。故對(duì)一切非負(fù)整數(shù)n，有=。§3.3.2 母函數(shù)方法對(duì)于一些較復(fù)雜的遞推關(guān)系，利用母函數(shù)方法求解是很有效的。當(dāng)用它求解數(shù)列 an的遞推關(guān)系時(shí)，一開始并不企圖直接找出an的解析表達(dá)式，而是首先作出 an的母函數(shù)G(x)并以它為媒介，將給定的遞推關(guān)系轉(zhuǎn)化為關(guān)于G(x)的方程（代數(shù)方程或微分方程等），然后用任何一種方法從中解出G(x)，再將G(x)展開成x的冪級(jí)數(shù)。

22、于是，xn的系數(shù)便是an的解析表達(dá)式（即遞推關(guān)系的解）。例3.3.5 解遞推關(guān)系an5an16an22n， n2(解) 令A(yù)(x)，用xn乘以式上式的兩端并對(duì)n從2到求和得即56亦即56將每個(gè)和式用A(x)代之便有(A(x)a0a1x）5x(A(x)a0)6x2A(x)(12x)解之得A(x)將A(x)分解為部分分式之和，并把每項(xiàng)展開成x的冪級(jí)數(shù)，有A(x)c1 c22 比較等式兩端xn的系數(shù)，便得遞推關(guān)系的通解為anc13 nc22n(n1) 2n+1式中c1、c2為任意常數(shù)，它們由初值a0和a1確定。例如，設(shè)a01，a12，則c1、c2滿足下列方程組解得c10，c23 .因此滿足上述初值條

23、件的遞推關(guān)系的解為an3×2n(n1)2n+1(12n)2n例3.3.6 求定解問題 .(解) 由問題可知 F00，設(shè) Fn的母函數(shù)是G(x)根據(jù)遞推關(guān)系有G(x)0xxxx G(x)x2 G(x)解之得G(x) (3.3.1)反過來(lái)，再將G(x)展開成冪級(jí)數(shù)，以求Fn的解析表達(dá)式。為此，先將G(x)分解G(x)G(x)等式成立，A、B應(yīng)滿足方程解之得A，B G(x)現(xiàn)在可以展開G(x)為冪級(jí)數(shù)，令，于是G(x) Fn這是著名的Fibonacci數(shù)列（見§3.4），它還告訴我們這樣一件事實(shí)，雖然Fn都是正整數(shù)，但它們卻可由一些無(wú)理數(shù)表示出來(lái)。例3.3.7 解定解問題 (解)

24、 這是一個(gè)二階變系數(shù)線性齊次遞推關(guān)系，根據(jù)方程的特點(diǎn)，令A(yù)(x)a1a2xa3x2a4x3anxn1兩邊對(duì)x求導(dǎo)得A'(x)2a3x3a4x2(n1)anxn2（由原問題知a20），計(jì)算A'(x)x A'(x)，得到(1x) A'(x)2a3x(3a42a3)x2(4a53a4)x3(n1)an(n2)an1 xn22a1x2a2 x22a3 x32an2xn22x A(x)即2注意到,兩邊對(duì)x積分2x2ln(1x)即lnA(x)ln(1x)22x A(x)e2x(1x)2展成冪級(jí)數(shù)為A(x) an+1 例3.3.8 (用指母函數(shù)解遞推關(guān)系)：求解(解) 由于D

25、10，故可令D01。可以看出，Dn隨n的增大而急劇增大，有點(diǎn)象n!，因此用指母函數(shù)。為此令D(x) 用乘以遞推關(guān)系式的兩端，然后對(duì)n從1到求和，得即D(x)D0xD(x)ex1亦即D(x) 由§2.2母函數(shù)的性質(zhì)3知于是得到Dn例3.3.9 用母函數(shù)方法求解二元遞推關(guān)系.解 設(shè)數(shù)列的母函數(shù)為，的母函數(shù)為。在第一個(gè)方程的兩邊同乘以得上式兩邊分別對(duì)n1,2,求和，得即32將1代入并整理得(13)21 同理，由第二個(gè)方程和所給初值可得 (1)0 聯(lián)立方程、解之，得再利用待定系數(shù)法將兩個(gè)函數(shù)分別分解為=最后將二者做冪級(jí)數(shù)展開得=所以，原遞推關(guān)系的解為§3.4 三種典型數(shù)列Fibon

26、acci數(shù)列、Stirling數(shù)列和Catalan數(shù)列經(jīng)常出現(xiàn)在組合計(jì)數(shù)問題中，是比較典型的三種數(shù)列。而其典型性還不在于數(shù)列本身，是在于許多實(shí)際計(jì)數(shù)問題的計(jì)算關(guān)系都與這三種數(shù)列是相同或相似的。§3.4.1 Fibonacci數(shù)列（一） 背景序列1，1，2，3，5，8，13，21，34，中，每個(gè)數(shù)都是它前兩者之和，這個(gè)序列稱為Fibonacci數(shù)列。由于它在算法分析和近代優(yōu)化理論中起著重要作用，又具有很奇特的數(shù)學(xué)性質(zhì)，因此，1963年起美國(guó)就專門出版了針對(duì)這一數(shù)列進(jìn)行研究的季刊Fibonacci Quarterly.該數(shù)列來(lái)源于1202年由意大利著名數(shù)學(xué)家Fibonacci提出的一個(gè)有

27、趣的兔子問題：有雌雄一對(duì)小兔，一月后長(zhǎng)大，兩月起往后每月生 (雌雄)一對(duì)小兔。小兔亦同樣如此。設(shè)一月份只有一對(duì)小兔，問一年后共有多少對(duì)兔子？更一般地，此問題可以變?yōu)閚個(gè)月后共有多少對(duì)兔子？月份1234n2n1nn+1小兔子數(shù)111大兔子數(shù)112總數(shù)1123將開始有第一對(duì)小兔的月份視為第一個(gè)月，用表示在第n個(gè)月的兔子數(shù)，顯然1。其次，可以看出前一個(gè)月兔子數(shù)本月新增兔子數(shù)因?yàn)橹挥星岸€(gè)月的兔子到本月恰好能生出一對(duì)小兔。所以，的定解問題為 （）（二） 求解可利用及初值可以求出，再用特征根法解之，得或這是因?yàn)?lt;1，而Fn是正整數(shù)，故當(dāng)n為偶數(shù)時(shí)，F(xiàn)n等于的整數(shù)部分，n為奇數(shù)時(shí)，F(xiàn)n等于的整數(shù)部分

28、加1。換句話說，求Fn時(shí)實(shí)際上并不需要計(jì)算。（三） 應(yīng)用例3.4.1 上樓梯問題：某人欲登上n級(jí)樓梯，若每次只能跨一級(jí)或兩級(jí)，問他從地面上到第n級(jí)樓梯，共有多少種不同的方法？（解）設(shè)上到第n級(jí)樓梯的方法數(shù)為an 那么，第一步無(wú)非有兩種可能：（1） 跨一級(jí)，則余下的n1級(jí)有an1種上法；（2） 跨兩級(jí)，則余下的n2級(jí)有an2種上法。由加法原理 且有，（）。顯然例3.4.2 棋盤染色問題：給一個(gè)具有1行n列的1×n棋盤（見圖3.4.1）的每一個(gè)方塊涂以紅、藍(lán)二色之一，要求相鄰的兩塊不能都染成紅色，設(shè)不同的染法共有an種，試求an.123n1n圖3.4.1 1×n棋盤（解）對(duì)格子

29、1的染色有兩種可能：（1） 染紅色，則2只能染藍(lán)色，余下的部分為1×（n2）棋盤，其滿足條件的染法共有種。由乘法原理，第一種染色方式的總數(shù)為1×1×；123n1n（2） 染藍(lán)色，則余下的1×（n1）棋盤的染法有種。由乘法原理，第二種染色方式的總數(shù)為1×123n1n由加法原理，且，（）F1F2F3F4F5F6112358a1a2a3a4顯然，類似的問題還有：無(wú)兩個(gè)1相連的n位二進(jìn)制數(shù)共有個(gè)。例3.4.3 交替子集問題：有限整數(shù)集合的一個(gè)子集稱為交替的，如果按上升次序列出其元素時(shí)，排列方式為奇、偶、奇、偶、。例如1，4，7，8和3，4，11都是，而

30、2，3，4，5則不是。令表示交替子集的數(shù)目（其中包括空集），證明且有（證）顯然，對(duì)應(yīng)的交替子集為和1。，對(duì)應(yīng)的交替子集為、1、1，2。將的所有子集分為兩部分：（1）的所有子集；（2）的每一個(gè)子集加入元素n后所得子集。例如，n4，的所有子集劃分為兩類即是（1） 、1、2、3、1，2、1，3、2，3、1，2，3（2） 4、1，4、2，4、3，4、1，2，4、1，3，4、2，3，4、1，2，3，4第一部分，即的交替子集數(shù)為。第二部分中的交替子集恰好同的交替子集是一一對(duì)應(yīng)的，故有個(gè)。因?yàn)閚1與n的奇偶性是相反的，故設(shè)的一個(gè)交替子集為，其中，若ak與n的奇偶性相同，則由即構(gòu)成的一個(gè)交替子集。若相反，則可

31、由構(gòu)成的一個(gè)交替子集。反之，對(duì)于中含有n的交替子集D，則（D中不含n1）或（D中含有n1）即是的交替子集。例如，的交替子集與第二部分子集中交替子集的對(duì)應(yīng)關(guān)系如下， ， 的遞推關(guān)系為 同前例一樣 例3.4.4 棋盤的（完全）覆蓋問題：本例的棋盤覆蓋是指用規(guī)格為1×2的骨牌覆蓋p×q的方格棋盤，要求每塊骨牌恰好蓋住盤上的相鄰兩格。所謂完全覆蓋是指對(duì)棋盤的一種滿覆蓋（即盤上所有格子都被覆蓋），而且骨牌不互相重疊。容易看出，一定存在對(duì)2×n棋盤的完全覆蓋?，F(xiàn)在的問題是，究竟有多少種不同的完全覆蓋方案？（解）設(shè)所求方案數(shù)為。那么，對(duì)圖3.4.2最左面的四格有且僅有兩種可能的

32、覆蓋方式：（1） 一塊骨牌豎著放，覆蓋最左面的兩格11和21，則整個(gè)棋盤的這種完全覆蓋方式與2×（n1）棋盤的完全覆蓋一一對(duì)應(yīng)，共有種方案；111213141n212223232n（2） 一塊骨牌橫著放，覆蓋第一行的格子11和12，由于是完全覆蓋，所以第二行最左面的兩格21和22也一定被同一塊骨牌覆蓋。于是整個(gè)棋盤的這種完全覆蓋方式與2×（n2）棋盤的完全覆蓋數(shù)相等，有種方案。111213141n212223232n圖3.4.2 2×n棋盤由加法原理，本例的定解問題為 §3.4.2 Stirling數(shù)列（一） Stirling數(shù)（1） 下階乘函數(shù)在組合分

33、析和有限差分學(xué)中的地位，如同冪函數(shù)在數(shù)學(xué)分析中的地位，二者都具有同樣的重要作用，又都是首項(xiàng)系數(shù)為1的特殊的n次多項(xiàng)式。（2） （下階乘函數(shù)的）遞歸定義，（3） （下階乘函數(shù)）與冪函數(shù)的關(guān)系：互相表示， ， ， ， ， 例 （4） Stirling數(shù)定義3.4.1 設(shè)， ，則稱、分別為第一類和第二類Stirling數(shù)。（5） 說明從母函數(shù)角度而言，數(shù)列的普母函數(shù)即為下階乘函數(shù)這是以為基函數(shù)。若以為基函數(shù)，定義一種母函數(shù)的話，數(shù)列的這種母函數(shù)就是（二） 組合意義（1）分配問題：將n個(gè)有區(qū)別的球放入m個(gè)相同的盒子，要求各盒不空，則不同的放法總數(shù)為；（2）集合的劃分：將含有n個(gè)元素的集合恰好分成m個(gè)無(wú)

34、序非空子集的所有不同劃分的數(shù)目即為。這種劃分也稱為集合的m劃分。上述組合意義也可以視為第二類Stirling數(shù)的等價(jià)定義。（三） 性質(zhì)定理3.4.1 第一類Stirling數(shù)的性質(zhì)：（1）， （2），（3）， （4），（5），（6）滿足遞推關(guān)系（證）由的表達(dá)式即知（1）（5）成立。（6）仍由的定義得 ，左右各自展開得整理上式并比較等式兩端同次冪的系數(shù)即得性質(zhì)（6）。利用的性質(zhì)，可以像楊輝三角形那樣寫出第一類Stirling數(shù)值表（見表）。 表3.4.1 的數(shù)值表kn123451121132314611615245035101定理3.4.2 第二類Stirling數(shù)有如下性質(zhì)：（1），n>

35、0 ； （2）（3）； （4）；（5）；（6）（證）由組合意義可以看出，將n個(gè)球（n>0）放入0個(gè)或1個(gè)盒子的方案數(shù)分別為0或1，放入n個(gè)盒子也只有一種方案，原因在于盒子不空且不加區(qū)別。所以，性質(zhì)（1）（3）成立。（4）n個(gè)球放入n1個(gè)盒，各盒不空，必有一盒有兩個(gè)球。從n個(gè)相異的球中選取2個(gè)，共有C(n,2)種組合方案。（5）n個(gè)球，2個(gè)盒。任取某一球x，其余的n1個(gè)球每個(gè)都有兩種可能的放法，即與x同盒或不同盒。故有種可能。但要排除大家都與x同盒的情形（這時(shí)另一盒將空），所以總的放法有種。（6）從n個(gè)球中任選一個(gè)記為x，根據(jù)n的情況將x個(gè)球放入k個(gè)盒的方案分為兩類：（a）x獨(dú)占一盒，其余

36、n1個(gè)球放入另外k1個(gè)盒，由組合意義知此類放法共有種；（b）x不獨(dú)占一盒，相當(dāng)于先將其余n1個(gè)球放入k個(gè)盒子，且各盒不空，有種放法，然后再將x放入其中某盒，有k種放法。由乘法原理，此類放法共有種。根據(jù)加法法則，即知性質(zhì)（6）成立。利用上述性質(zhì)，可得第二類Stirling數(shù)值表（見表3.4.2）。表 的數(shù)值表kn1234511211313141761511525101下面不加證明地給出Stirling數(shù)的其它結(jié)論：（1），（2）.（四） 應(yīng)用例3.4.5 所有從1,2,n-1中取n-k個(gè)不同數(shù)的積之和是多少？例如，所有從1,2,3,4中取2個(gè)不同整數(shù)的積之和是(n=5，k=3)解 用f(n,k)

37、表示此和數(shù)，和式的各項(xiàng)可分成兩類，一類是含有因子n-1的項(xiàng)，一類是不含n-1的項(xiàng)。前者的和是(n-1)f(n-1,k)，即從所有從1,2,n-2中取(n-k)-1=(n-1)-k個(gè)不同整數(shù)的積之和，再乘以n-1得出。后者之和是f(n-1,k-1)，即所有從1,2,n-2中取n-k=(n-1)-(k-1)個(gè)不同整數(shù)的積之和。于是由加法法則得為使上式對(duì)k=1和k=n-1都成立，規(guī)定，從而有令，可得與的性質(zhì)比較，即知g(n,k)。 例3.4.6 Stirling數(shù)的另一個(gè)重要應(yīng)用就是分配問題：即將n個(gè)球（物體）放入k個(gè)盒子，其放法的總數(shù)可以分成8種情況分別予以討論（見表）。表. 分配問題方案計(jì)數(shù)表n

38、個(gè)球k個(gè)盒是否空盒不同的方案數(shù)有區(qū)別不同是否相同是，rmin(n,k)否無(wú)區(qū)別不同是C(nk1，n)否C(n1,k1)相同是展開式中xn的系數(shù)否展開式中xn的系數(shù)（說明）當(dāng)然，上述8種情形還不能包括所有的分配模型，如情形1是指放入同一盒中的球是無(wú)次序之分的。否則，方案數(shù)應(yīng)為其次，各種分配方案中并未考慮盒子中最多能放幾個(gè)球的問題。否則，對(duì)第一種情形，當(dāng)每個(gè)盒中最大只能放入一個(gè)球時(shí)，其分配方案數(shù)就不是，而應(yīng)為。§3.4.3 Catalan數(shù)列（一） 定義滿足遞推關(guān)系 () 的數(shù)列稱為Catalan數(shù)列。其解為。值 1，1，2，5，14，42，132，429，1430，4862，16796

39、，（二） 求解(解) 設(shè)Catalan數(shù)列的母函數(shù)為A(x)，即，那么，即解之得，.由于，而，所以舍去便得利用泰勒展開式f(x) 得 （三） 應(yīng)用例3.4.7 （凸n邊形的剖分）Euler在精確計(jì)算對(duì)凸n邊形的不同的對(duì)角線三角剖分的個(gè)數(shù)問題時(shí)，最先得到了這個(gè)數(shù)列。其問題是：將凸n邊形用不相交的對(duì)角線分成三角形，有多少種不同的分法？例如，五邊形就有五種剖分方案（見圖）。圖 凸五邊形的剖分方案(解) 所謂凸多邊形是指該多邊形的任意不相鄰兩點(diǎn)的連線都在多邊形內(nèi)部。如圖3.4.4所示。（1）求滿足的遞推關(guān)系設(shè)凸n邊形的對(duì)角三角形剖分的個(gè)數(shù)為顯然，且，。那么，當(dāng)時(shí)，設(shè)凸n1邊形的頂點(diǎn)依次為v1,v2,v

40、n1，固定一條邊，再另取一個(gè)頂點(diǎn)vk（k2,3,n），作三角形，它分多邊形為兩個(gè)較小的凸多邊形。一個(gè)是凸k邊形，其剖分?jǐn)?shù)為，另一個(gè)是nk2邊形，其剖分?jǐn)?shù)為（見圖3.4.4（a），由乘法原理和加法原理知 ()其中規(guī)定 v2 v2 v1 k邊形 v3 k邊形 v1 vn+1 nk+2邊形 vk nk+2邊形 vk vn vn（a） （b）圖 3.4.4 任意凸多邊形的剖分（2）求解令，得的定解問題 與式（）比較即知，所以（3）另法值得指出的是，數(shù)列還滿足某個(gè)一階變系數(shù)的線性遞推關(guān)系。這可以從另一個(gè)角度考察凸n邊形的對(duì)角線三角剖分個(gè)數(shù)。如圖（b）所示，連接凸n邊形的兩點(diǎn)v1、vk，將多邊形一分為二，

41、對(duì)應(yīng)的剖分?jǐn)?shù)為。這時(shí)，k3,4,(n1)。由加法原理得對(duì)應(yīng)于v1的三角剖分?jǐn)?shù)為。由對(duì)稱性，對(duì)應(yīng)于其它任一頂點(diǎn)的剖分?jǐn)?shù)也是如此。故在重復(fù)計(jì)算的情況下得 n()個(gè)三角剖分。這是按頂點(diǎn)統(tǒng)計(jì)的，若按對(duì)角線來(lái)統(tǒng)計(jì)，由于每條對(duì)角線有兩個(gè)頂點(diǎn)，因此應(yīng)除以2，有()。但是，這也不是剖分?jǐn)?shù)，無(wú)疑其中是有重復(fù)的。其重復(fù)度在于一個(gè)凸n邊形的三角形剖分要用n3條對(duì)角線來(lái)形成，一種剖分方案，就對(duì)應(yīng)了該n3條對(duì)角線的一種“布局”。反之，換一種布局，就對(duì)應(yīng)另一種剖分方案。把n3條對(duì)角線中的每一條當(dāng)作分割線來(lái)統(tǒng)計(jì)剖分方案?jìng)€(gè)數(shù)時(shí)，這個(gè)三角剖分都要被計(jì)數(shù)一次，也就是說，同一個(gè)剖分方案，若按對(duì)角線來(lái)統(tǒng)計(jì)，則被計(jì)算了n3次。因此有)

42、 ()由（）得 ，與上式比較得整理得令 ，即 例3.4.8 設(shè)P為n個(gè)數(shù)的連乘積，保持原來(lái)的排列順序，試問有多少種不同的結(jié)合方案(即根據(jù)乘法的結(jié)合律插入n1對(duì)括號(hào)，使得每對(duì)括號(hào)內(nèi)為恰好市兩個(gè)因子的乘積。如n4，P.(解) 設(shè)為插入n1對(duì)括號(hào)的方案數(shù)。對(duì)于的每一種結(jié)合方案，其最后的那次乘法運(yùn)算，必是的相乘結(jié)果P1和的結(jié)果P2兩項(xiàng)相乘()，即最外層括號(hào)所含的兩個(gè)因子P1和P2。對(duì)于固定的k，P1有種不同的結(jié)合方案，P2則有種。例如P，P1，P2，P，P1，P2因此，總的方案數(shù)是顯然，。事實(shí)上，n個(gè)數(shù)連乘積的結(jié)合方案與凸n1邊形的三角形剖分是一一對(duì)應(yīng)的。圖3.4.5給出了n4時(shí)的對(duì)應(yīng)情形類似的問題

43、還有在n項(xiàng)求和式中，不改變各數(shù)的相對(duì)排列次序，只給其插入括號(hào)，改變求和順序，不同的結(jié)合方案數(shù)也是圖3.4.5圖3.4.5 n4時(shí)連乘積與凸5邊形三角剖分的對(duì)應(yīng)關(guān)系例3.4.9 具有n個(gè)結(jié)點(diǎn)的所有不同的二叉樹的個(gè)數(shù)是(解) 二叉樹是一種重要的樹形結(jié)構(gòu)。其特點(diǎn)是每個(gè)結(jié)點(diǎn)都是一棵子樹的根，而且它至多有兩棵子樹。因此可以歸納定義二叉樹為結(jié)點(diǎn)的有限集合，該集合或者是空集，或者是由一個(gè)根(一個(gè)特定結(jié)點(diǎn))及兩個(gè)不相交的被稱作這個(gè)根的左子樹和右子樹所組成。二叉樹與計(jì)算機(jī)算法關(guān)系密切，在算法研究中引出了二叉樹的計(jì)數(shù)問題，即具有n個(gè)結(jié)點(diǎn)的所有結(jié)構(gòu)上不同的二叉樹有多少個(gè)？令表示n個(gè)結(jié)點(diǎn)的二叉樹總數(shù)，容易看出，。圖給

44、出了含有3個(gè)結(jié)點(diǎn)的所有不同的二叉樹。對(duì)于一般情形，二叉樹有一個(gè)根結(jié)點(diǎn)及n1個(gè)非根結(jié)點(diǎn)，后者又可分為兩個(gè)子集，分別構(gòu)成左子樹和右子樹。不失一般性，設(shè)左子樹有k個(gè)結(jié)點(diǎn)，則右子樹有n1k個(gè)結(jié)點(diǎn)。于是作為根的左子樹的所有可能的二叉樹的數(shù)目是，作為根的右子樹的所有可能的二叉樹的數(shù)目是 (k0,1,n1) 。因此，由乘法原理和加法原理便知令，再與（）比較即得，所以有圖 具有3個(gè)結(jié)點(diǎn)的二叉樹例3.4.10 有n個(gè)結(jié)點(diǎn)的所有不同的有序樹的個(gè)數(shù)是(解) 有序樹是實(shí)際應(yīng)用中另一種重要的樹形結(jié)構(gòu)。當(dāng)一棵樹中任何一個(gè)結(jié)點(diǎn)的諸子樹的相對(duì)次序要考慮時(shí)，它就是有序樹。眾所周知，任何一個(gè)有序樹都可用二叉樹表示。同時(shí)注意到，這

45、棵二叉樹的根的右子樹是空二叉樹，故具有n個(gè)結(jié)點(diǎn)的有序樹和具有n1個(gè)結(jié)點(diǎn)的二叉樹之間存在一一對(duì)應(yīng)的關(guān)系。因此，有n個(gè)結(jié)點(diǎn)的有序樹的個(gè)數(shù)為，即。例如，有4個(gè)結(jié)點(diǎn)的結(jié)構(gòu)不同的有序樹共有個(gè)，如圖3.4.7所示，它們分別與圖的有3個(gè)結(jié)點(diǎn)的二叉樹一一對(duì)應(yīng)。圖 3.4.7 具有4個(gè)結(jié)點(diǎn)的有序樹有序樹與二叉樹的對(duì)應(yīng)規(guī)則：有序樹的長(zhǎng)子樹作二叉樹的左子樹，次弟作右子樹。參見圖。圖3.4.8圖 3.4.8 用二叉樹表示有序樹例3.4.11 由n個(gè)1和n個(gè)0組成的2n位的二進(jìn)制數(shù)，要求從左向右掃描，1的累計(jì)數(shù)不小于0的累計(jì)數(shù)，試求這樣的二進(jìn)制數(shù)有多少？解 解法一：設(shè)滿足條件的二進(jìn)制數(shù)有個(gè)。將其視為由字符0和1構(gòu)成的二

46、進(jìn)制串，現(xiàn)分類統(tǒng)計(jì)其個(gè)數(shù)如下：設(shè)從左向右掃描到第2位時(shí)（1），第一次出現(xiàn)了0的個(gè)數(shù)等于1的個(gè)數(shù)。那么在此之前，掃描到任何一位時(shí)，1的個(gè)數(shù)總是大于0的個(gè)數(shù)。例如下面的二進(jìn)制串：1110001100（k=5），1101001100（k=3），1101010010（k=4），1101010100（k=5）設(shè)具有這種性質(zhì)的串有個(gè)，則=這是因?yàn)榭梢詫⒎项}目要求的串分為前后兩個(gè)子串，前子串共2位，后子串有2(n-k)位。首先，由題目的條件知，后子串也是符合題目要求的二進(jìn)制串，只是其長(zhǎng)度為2(n-k)，故有個(gè)。其次，針對(duì)前子串，由其性質(zhì)知，當(dāng)去掉第1位和第2位時(shí)，剩下的2(k1)位串也符合題目條件，故前子串有個(gè)。 由乘法法則，具有此性質(zhì)的串共有個(gè)。而相應(yīng)于不同的值（k=1,2,n），兩類這樣的二進(jìn)制串不可能互相有重復(fù)的情況，故由加法法則，所求的串的個(gè)數(shù)為=+=+且有=1。另外，觀察上式，可知應(yīng)有=1。參照例中關(guān)于數(shù)列所滿足的遞推關(guān)系的解法，可知=解法二：用排列組合的方法求解。詳見本教材的配套資料組合數(shù)學(xué) 學(xué)習(xí)指導(dǎo)書中關(guān)于第一章習(xí)題32的求解過程。§3.5 應(yīng) 用例3.5.1 求下列行列式的值。（解）利用行列式的性質(zhì)，將其按第一行展開得再將第二個(gè)n1階行列式按第一列展開得即故得定解問題其特征根為 x1（二重），所以通解為其中A、B為任意常數(shù)，代如初值得，所以即n1.