組合數(shù)學(xué) 遞推關(guān)系

《組合數(shù)學(xué) 遞推關(guān)系》由會員分享，可在線閱讀，更多相關(guān)《組合數(shù)學(xué) 遞推關(guān)系（68頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第三章 遞推關(guān)系3.1 基本概念（一） 遞推關(guān)系定義3.1.1 （隱式）對數(shù)列和任意自然數(shù)n，一個關(guān)系到和某些個的方程式，稱為遞推關(guān)系，記作 (3.1.1)例 定義3.1.1（顯式） 對數(shù)列，把與其之前若干項聯(lián)系起來的等式對所有nk均成立（k為某個給定的自然數(shù)），稱該等式為的遞推關(guān)系，記為 (3.1.1)例 （二） 分類（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)系，如，之前的系

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

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

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

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

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

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

8、3.2.1），即 令r1r2得：（為書寫方便，此處特給定c01，下同）。即也滿足方程（3.2.1）。性質(zhì)1可以推廣到一般情形：設(shè)均為（3.2.1）之解，則也是（3.2.1）的解。其中為任意常數(shù)。性質(zhì)2. 設(shè)和是（3.2.2）的解，則是（3.2.1）的解。性質(zhì)3. 若是（3.2.1）的解，是（3.2.2）的解，則是（3.2.2）的解。推廣到一般情形：設(shè)是（3.2.2）的解，分別是（3.2.1）的解，則是（3.2.2）的解。性質(zhì)4. 設(shè)是遞推關(guān)系的解，是遞推關(guān)系的解，則是遞推關(guān)系的解。性質(zhì)24的證明與性質(zhì)1類似，請讀者自己完成。3.2.2 解的結(jié)構(gòu)（一） 概念定義3.2.1 稱多項式C(x)為齊次

9、遞推關(guān)系（3.2.1）的特征多項式，相應(yīng)的代數(shù)方程C(x) 0 稱為（3.2.1）的特征方程，特征方程的解稱為（3.2.1）的特征根。（二） 結(jié)論定理3.2.1 數(shù)列anqn是（3.2.1）的非零解的充分必要條件是q為（3.2.1）的特征根。（證） anqn是（3.2.1）的解 q是方程C(x)0的根，即q是（3.2.1）的特征根。意義：將求解常系數(shù)線性齊次遞推關(guān)系的問題轉(zhuǎn)化為常系數(shù)代數(shù)方程的求根問題，從而給出了一個實(shí)用且比較簡單的解此類遞推關(guān)系的方法。（三） 通解定義3.2.2 若是（3.2.1）的不同解，且（3.2.1）的任何解都可以表為，則稱為（3.2.1）的通解。其中為任意常數(shù)。此處所

10、說的不同解是指將每一個解都視為一個無窮維的解向量，而這些向量之間是線性無關(guān)的。說明 通解的特征： 通解首先是解； 組成通解的所有解向量線性無關(guān)； 任何一個具體的解都被包容在通解中。3.2.3 特征根法該方法的思路就是通過解式（3.2.1）的特征方程，從而求得其特征根，再利用特征根即可獲得（3.2.1）的通解。根據(jù)特征根的不同分布情況，分為下述三種情形予以討論。（一） 特征根為單根情形設(shè)是（3.2.1）的互不相同的特征根，則（3.2.1）的通解為 （3.2.3）其中為任意常數(shù)（待定）。（證）首先由定理3.2.1知是方程（3.2.1）的解。且由性質(zhì)1知也是（3.2.1）的解。再證（3.2.1）的所

11、有解都可以表為（3.2.3）的形式。設(shè)是（3.2.1）的一個解，且滿足初始條件。令，代入初始條件，可得關(guān)于的線性方程組 （3.2.4）其系數(shù)行列式為著名的范德蒙（Vandermonde）行列式：所以式（3.2.4）有唯一解。即一定可以表示為(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)系的通解。（解）特征方程為，特征根是二重根，若

12、按單根情形處理，有通解，即一個待定常數(shù)。要滿足兩個初始條件，一般是不可能的。其實(shí)質(zhì)在于按特征根確定的兩個解和是線性相關(guān)的，即。現(xiàn)在的問題就是要找兩個線性無關(guān)的解和，使得.若令，可以驗(yàn)證是（3.2.1）的解，且與線性無關(guān)。同時，仿照單根情形，可以證明通解為一般情況下，設(shè)q是（3.2.1）的k重根，則（3.2.1）的通解為 (3.2.5)更一般的情形，若式（3.2.1）有t個根，其中為重根，那么，通解應(yīng)為 (3.2.6)（三） 復(fù)根情形 設(shè)特征方程有一對共軛（單）復(fù)根：，那么，通解中會出現(xiàn)這就是說，和也分別是（3.2.1）的解（此二解與解是線性相關(guān)的，故不能構(gòu)成4個線性無關(guān)的解），且易知二者線性無

13、關(guān)，故通解為 (3.2.7)當(dāng)然，通解也可表為，但是，后者要涉及到復(fù)數(shù)運(yùn)算，前者卻避免了這一點(diǎn)。一般情形，若q是m重復(fù)根，自然也是m重復(fù)根，從而通解中必含有下面的項上述三種情形可以歸納成表3.2.1.表3.2.1特征根通解中對應(yīng)的項實(shí)根q為單根m重根復(fù) 根一對單復(fù)根一對m重復(fù)根例3.2.3 求定解。（解）特征方程為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，因此，通

14、解是代入初始條件，有解之得 A3，B0，C1，D0，E1，故定解為=，n0,1, 3.2.4 非齊次方程（一） 結(jié)構(gòu)對于非齊次方程，比較有規(guī)律的解法主要是針對f(n)的幾種特殊情形。定理3.2.2 設(shè)是（3.2.2）的一個特解，是（3.2.1）的通解，則的通解為 (3.2.8)（證）首先由解的性質(zhì)知，是(3.2.2)的解。其次，證明是通解。若給定一組初始條件a0 d0，a1d1，ak1dk1 (3.2.9)可以仿照齊次方程通解的證明方法，證得相應(yīng)于條件(3.2.9)的解一定可以表示為(3.2.8)的形式。（二） 待定系數(shù)法關(guān)于的求法已經(jīng)解決，這里的主要問題是求(3.2.2)的特解。遺憾的是尋求

15、特解還沒有一般通用的方法。然而當(dāng)非齊次線性遞推關(guān)系的自由項f(n)比較簡單時，采用下面的待定系數(shù)法比較方便。（一）f(n)b（b為常數(shù)）其中m表示1是的m重特征根（0mk）。當(dāng)然，若1不是特征根（即m0），則。（二）（b為常數(shù)）其中m表示b是的m重特征根（0mk）。同樣，若b不是特征根（即m0），則。（三），其中為關(guān)于n的r次多項式，b為常數(shù)。其中是與同次的多項式，m仍然是b為特征根的重數(shù)（0mk）。當(dāng)b不是特征根時（即m0），。（三） 例例3.2.5 求非齊次方程an13 an212an33的通解。（解）其相應(yīng)齊次方程的特征方程是 q313q120特征根為1，3，4，由于1是特征根，故有m1

16、，其特解形式為AnA稱為待定系數(shù)，將An代入原非齊次方程得An13A(n2)12A(n3)3解之得 A，因此，所求通解為anB1B23 nB3(4) nn其中B1、B2、B3為任意常數(shù)。例3.2.6 求an4 an14an22n 的通解。（解）顯然，對應(yīng)齊次方程的特征根為q2（二重根），故特解形式為An2 2n代入原非齊次方程求得待定系數(shù)A，因此，通解為anB1n 2nB22nn2 2n其中B1、B2為任意常數(shù)。例3.2.7 求an4 an1an2n(n1) 的通解。（解）此例中，b1，f(n)n2n，求得特征根為q12，q12b1不是特征根，故特解形式為An2 BnC將代入原非齊次方程，整理

17、可得6An2 6(2AB)n2(4A3B3C)n2n比較等式兩邊同類項的系數(shù)，有A，B，C，因此，非齊次方程的通解為anB1B2其中B1、B2為任意常數(shù)。（四） 化非齊次方程為齊次方程例3.2.8 求.（解）（1）滿足的遞推關(guān)系顯然，滿足非齊次定解問題（2）化為齊次遞推關(guān)系改寫遞推關(guān)系為 那么，類似可得 得 同理有 就得關(guān)于的齊次定解問題（3）求解q1是三重根。 （3.2.10）代入初始條件得A0， ABC1， A2B3C3解之得A0， BC 這就利用遞推關(guān)系證明了求和公式（五） 一般求和公式（1）問題：求（2）化為齊次遞推關(guān)系求解首先，當(dāng)r1時，由（四）知當(dāng)r2時，可得 得 得 就得關(guān)于的齊

18、次定解問題特征根仍然是q1（三重），所以再利用初值條件得（3）快速求常數(shù)A、B、C、D等當(dāng)r1時，令代入初始條件后得A0， AB1， A2B2C3解得 A0，B1，C 此處的方便主要體現(xiàn)在由關(guān)于A、B、C的第一個方程開始，可以逐步遞推地解出這些常數(shù)，實(shí)質(zhì)上并不需要解線性代數(shù)方程組。當(dāng)然，還可以令使得在利用初值確定A、B、C時更加方便。因?yàn)檫@樣以來，下式第1、2、3個方程中分別關(guān)于A、B、C的系數(shù)恰好是1。A0， AB1， A2BC3從而易得A0， B1， C1當(dāng)r2時，可令代入初值得方程組A0， AB1， A2BC5， A3B3CD14從而易得A0， B1， C3， D2即對于較大的r，求部分

19、和時，利用非齊次遞推關(guān)系求解還是要比將其化為齊次遞推關(guān)系方便得多。此外， （4）一般情形若通解為r階多項式，對定解問題（3.1.2），可令使得用初值條件求解常數(shù)非常簡單。3.2.5 一般遞推關(guān)系的線性化對于某些非線性或變系數(shù)的遞推關(guān)系，可以將其化為線性關(guān)系來求解。例3.2.9 解定解問題 （解）此為線性變系數(shù)齊次關(guān)系。改寫原方程為兩邊取對數(shù)得令，得關(guān)于的遞推關(guān)系再令，。先用迭代法求定解，易得，再求定解，可得。從而得 例3.2.10 解定解問題 （解）這是線性變系數(shù)非齊次關(guān)系。令得顯然，特征根q1。所以2不是特征根，特解。代入的遞推關(guān)系可得 ，即特解 通解 再由初始條件 知 定解 即例3.2.1

20、1 解定解問題 （解）本題的難點(diǎn)在于，不在前邊給出的三種類型之中。令， 則有由于q1為“1”重特征根，故特解。代入的遞推關(guān)系可得，即 特解為 通解為再由初始條件 知，即的通解為，從而的通解為另法：對于，可以用迭代法或直接觀察出，再用歸納法證明之即可。例3.2.12 解定解問題 （解）這是非線性的遞推關(guān)系，令，將問題變?yōu)?，解之得，從而（an0是顯然的）。3.3 解遞推關(guān)系的其它方法3.3.1 迭代法與歸納法對于某些特殊的，尤其是一階的遞推關(guān)系，使用迭代法求解可能更快。而有些遞推關(guān)系則可以通過觀察n比較小時的表達(dá)式的規(guī)律，總結(jié)或猜出的一般表達(dá)式，然后再用歸納法證明之即可。例3.3.1解 變換原遞推

21、關(guān)系為 （3.3.1）逐步迭代，得所以顯見當(dāng)n0時，上式仍成立，即滿足所給的初值，故定解問題的解為本題也可理解為利用式（3.3.1）先做變量代換，得關(guān)于的遞推關(guān)系用迭代法解之得， 然后反代回去得， 例3.3.2 解遞推關(guān)系解 因，迭代得所以顯見當(dāng)n0時，上式仍成立，故定解問題的解為例3.3.3 。解 由題設(shè)所以， ，當(dāng)k0時，上面兩個式子仍成立。故或，例3.3.4 用歸納法解遞推關(guān)系， 解 計算較小n時的，并觀察得由此可猜想=下面用歸納法證之：顯然n0，1，2，3時結(jié)論為真。假設(shè)n=k時結(jié)論為真，即=成立。 考慮n=k1時=結(jié)論成立。故對一切非負(fù)整數(shù)n，有=。3.3.2 母函數(shù)方法對于一些較復(fù)

22、雜的遞推關(guān)系，利用母函數(shù)方法求解是很有效的。當(dāng)用它求解數(shù)列 an的遞推關(guān)系時，一開始并不企圖直接找出an的解析表達(dá)式，而是首先作出 an的母函數(shù)G(x)并以它為媒介，將給定的遞推關(guān)系轉(zhuǎn)化為關(guān)于G(x)的方程（代數(shù)方程或微分方程等），然后用任何一種方法從中解出G(x)，再將G(x)展開成x的冪級數(shù)。于是，xn的系數(shù)便是an的解析表達(dá)式（即遞推關(guān)系的解）。例3.3.5 解遞推關(guān)系an5an16an22n， n2(解) 令A(yù)(x)，用xn乘以式上式的兩端并對n從2到求和得即56亦即56將每個和式用A(x)代之便有(A(x)a0a1x）5x(A(x)a0)6x2A(x)(12x)解之得A(x)將A(x

23、)分解為部分分式之和，并把每項展開成x的冪級數(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 .因此滿足上述初值條件的遞推關(guān)系的解為an32n(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)反過來，再將G(x)展開成冪級數(shù)，以求Fn的解析表達(dá)式。為此，先將G(x)分

24、解G(x)G(x)等式成立，A、B應(yīng)滿足方程解之得A，B G(x)現(xiàn)在可以展開G(x)為冪級數(shù)，令，于是G(x) Fn這是著名的Fibonacci數(shù)列（見3.4），它還告訴我們這樣一件事實(shí)，雖然Fn都是正整數(shù)，但它們卻可由一些無理數(shù)表示出來。例3.3.7 解定解問題 (解) 這是一個二階變系數(shù)線性齊次遞推關(guān)系，根據(jù)方程的特點(diǎn)，令A(yù)(x)a1a2xa3x2a4x3anxn1兩邊對x求導(dǎo)得A(x)2a3x3a4x2(n1)anxn2（由原問題知a20），計算A(x)x A(x)，得到(1x) A(x)2a3x(3a42a3)x2(4a53a4)x3(n1)an(n2)an1 xn22a1x2a2

25、x22a3 x32an2xn22x A(x)即2注意到,兩邊對x積分2x2ln(1x)即lnA(x)ln(1x)22x A(x)e2x(1x)2展成冪級數(shù)為A(x) an+1 例3.3.8 (用指母函數(shù)解遞推關(guān)系)：求解(解) 由于D10，故可令D01。可以看出，Dn隨n的增大而急劇增大，有點(diǎn)象n!，因此用指母函數(shù)。為此令D(x) 用乘以遞推關(guān)系式的兩端，然后對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ù)為。在第一個方程的兩邊同乘以得上式兩邊分別對n1,2,求和，得即3

26、2將1代入并整理得(13)21 同理，由第二個方程和所給初值可得 (1)0 聯(lián)立方程、解之，得再利用待定系數(shù)法將兩個函數(shù)分別分解為=最后將二者做冪級數(shù)展開得=所以，原遞推關(guān)系的解為3.4 三種典型數(shù)列Fibonacci數(shù)列、Stirling數(shù)列和Catalan數(shù)列經(jīng)常出現(xiàn)在組合計數(shù)問題中，是比較典型的三種數(shù)列。而其典型性還不在于數(shù)列本身，是在于許多實(shí)際計數(shù)問題的計算關(guān)系都與這三種數(shù)列是相同或相似的。3.4.1 Fibonacci數(shù)列（一） 背景序列1，1，2，3，5，8，13，21，34，中，每個數(shù)都是它前兩者之和，這個序列稱為Fibonacci數(shù)列。由于它在算法分析和近代優(yōu)化理論中起著重要作

27、用，又具有很奇特的數(shù)學(xué)性質(zhì)，因此，1963年起美國就專門出版了針對這一數(shù)列進(jìn)行研究的季刊Fibonacci Quarterly.該數(shù)列來源于1202年由意大利著名數(shù)學(xué)家Fibonacci提出的一個有趣的兔子問題：有雌雄一對小兔，一月后長大，兩月起往后每月生 (雌雄)一對小兔。小兔亦同樣如此。設(shè)一月份只有一對小兔，問一年后共有多少對兔子？更一般地，此問題可以變?yōu)閚個月后共有多少對兔子？月份1234n2n1nn+1小兔子數(shù)111大兔子數(shù)112總數(shù)1123將開始有第一對小兔的月份視為第一個月，用表示在第n個月的兔子數(shù)，顯然1。其次，可以看出前一個月兔子數(shù)本月新增兔子數(shù)因?yàn)橹挥星岸€月的兔子到本月恰好

28、能生出一對小兔。所以，的定解問題為 （3.4.1）（二） 求解可利用及初值可以求出，再用特征根法解之，得或這是因?yàn)? ； （2）（3）； （4）；（5）；（6）（證）由組合意義可以看出，將n個球（n0）放入0個或1個盒子的方案數(shù)分別為0或1，放入n個盒子也只有一種方案，原因在于盒子不空且不加區(qū)別。所以，性質(zhì)（1）（3）成立。（4）n個球放入n1個盒，各盒不空，必有一盒有兩個球。從n個相異的球中選取2個，共有C(n,2)種組合方案。（5）n個球，2個盒。任取某一球x，其余的n1個球每個都有兩種可能的放法，即與x同盒或不同盒。故有種可能。但要排除大家都與x同盒的情形（這時另一盒將空），所以總的放法

29、有種。（6）從n個球中任選一個記為x，根據(jù)n的情況將x個球放入k個盒的方案分為兩類：（a）x獨(dú)占一盒，其余n1個球放入另外k1個盒，由組合意義知此類放法共有種；（b）x不獨(dú)占一盒，相當(dāng)于先將其余n1個球放入k個盒子，且各盒不空，有種放法，然后再將x放入其中某盒，有k種放法。由乘法原理，此類放法共有種。根據(jù)加法法則，即知性質(zhì)（6）成立。利用上述性質(zhì)，可得第二類Stirling數(shù)值表（見表3.4.2）。表3.4.2 的數(shù)值表kn1234511211313141761511525101下面不加證明地給出Stirling數(shù)的其它結(jié)論：（1），（2）.（四） 應(yīng)用例3.4.5 所有從1,2,n-1中取n

30、-k個不同數(shù)的積之和是多少？例如，所有從1,2,3,4中取2個不同整數(shù)的積之和是(n=5，k=3)解 用f(n,k)表示此和數(shù)，和式的各項可分成兩類，一類是含有因子n-1的項，一類是不含n-1的項。前者的和是(n-1)f(n-1,k)，即從所有從1,2,n-2中取(n-k)-1=(n-1)-k個不同整數(shù)的積之和，再乘以n-1得出。后者之和是f(n-1,k-1)，即所有從1,2,n-2中取n-k=(n-1)-(k-1)個不同整數(shù)的積之和。于是由加法法則得為使上式對k=1和k=n-1都成立，規(guī)定，從而有令，可得與的性質(zhì)比較，即知g(n,k)。 例3.4.6 Stirling數(shù)的另一個重要應(yīng)用就是分

31、配問題：即將n個球（物體）放入k個盒子，其放法的總數(shù)可以分成8種情況分別予以討論（見表3.4.3）。表3.4.3. 分配問題方案計數(shù)表n個球k個盒是否空盒不同的方案數(shù)有區(qū)別不同是否相同是，rmin(n,k)否無區(qū)別不同是C(nk1，n)否C(n1,k1)相同是展開式中xn的系數(shù)否展開式中xn的系數(shù)（說明）當(dāng)然，上述8種情形還不能包括所有的分配模型，如情形1是指放入同一盒中的球是無次序之分的。否則，方案數(shù)應(yīng)為其次，各種分配方案中并未考慮盒子中最多能放幾個球的問題。否則，對第一種情形，當(dāng)每個盒中最大只能放入一個球時，其分配方案數(shù)就不是，而應(yīng)為。3.4.3 Catalan數(shù)列（一） 定義滿足遞推關(guān)系

32、 (3.4.2) 的數(shù)列稱為Catalan數(shù)列。其解為。值 1，1，2，5，14，42，132，429，1430，4862，16796，（二） 求解(解) 設(shè)Catalan數(shù)列的母函數(shù)為A(x)，即，那么，即解之得，.由于，而，所以舍去便得利用泰勒展開式f(x) 得 （三） 應(yīng)用例3.4.7 （凸n邊形的剖分）Euler在精確計算對凸n邊形的不同的對角線三角剖分的個數(shù)問題時，最先得到了這個數(shù)列。其問題是：將凸n邊形用不相交的對角線分成三角形，有多少種不同的分法？例如，五邊形就有五種剖分方案（見圖3.4.3）。圖 3.4.3 凸五邊形的剖分方案(解) 所謂凸多邊形是指該多邊形的任意不相鄰兩點(diǎn)的連

33、線都在多邊形內(nèi)部。如圖3.4.4所示。（1）求滿足的遞推關(guān)系設(shè)凸n邊形的對角三角形剖分的個數(shù)為顯然，且，。那么，當(dāng)時，設(shè)凸n1邊形的頂點(diǎn)依次為v1,v2,vn1，固定一條邊，再另取一個頂點(diǎn)vk（k2,3,n），作三角形，它分多邊形為兩個較小的凸多邊形。一個是凸k邊形，其剖分?jǐn)?shù)為，另一個是nk2邊形，其剖分?jǐn)?shù)為（見圖3.4.4（a），由乘法原理和加法原理知 (3.4.3)其中規(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.4.2）比較即知，所以（3

34、）另法值得指出的是，數(shù)列還滿足某個一階變系數(shù)的線性遞推關(guān)系。這可以從另一個角度考察凸n邊形的對角線三角剖分個數(shù)。如圖3.4.4（b）所示，連接凸n邊形的兩點(diǎn)v1、vk，將多邊形一分為二，對應(yīng)的剖分?jǐn)?shù)為。這時，k3,4,(n1)。由加法原理得對應(yīng)于v1的三角剖分?jǐn)?shù)為。由對稱性，對應(yīng)于其它任一頂點(diǎn)的剖分?jǐn)?shù)也是如此。故在重復(fù)計算的情況下得 n()個三角剖分。這是按頂點(diǎn)統(tǒng)計的，若按對角線來統(tǒng)計，由于每條對角線有兩個頂點(diǎn)，因此應(yīng)除以2，有()。但是，這也不是剖分?jǐn)?shù)，無疑其中是有重復(fù)的。其重復(fù)度在于一個凸n邊形的三角形剖分要用n3條對角線來形成，一種剖分方案，就對應(yīng)了該n3條對角線的一種“布局”。反之，換

35、一種布局，就對應(yīng)另一種剖分方案。把n3條對角線中的每一條當(dāng)作分割線來統(tǒng)計剖分方案個數(shù)時，這個三角剖分都要被計數(shù)一次，也就是說，同一個剖分方案，若按對角線來統(tǒng)計，則被計算了n3次。因此有) (3.4.4)由（3.4.3）得 ，與上式比較得整理得令 ，即 例3.4.8 設(shè)P為n個數(shù)的連乘積，保持原來的排列順序，試問有多少種不同的結(jié)合方案(即根據(jù)乘法的結(jié)合律插入n1對括號，使得每對括號內(nèi)為恰好市兩個因子的乘積。如n4，P.(解) 設(shè)為插入n1對括號的方案數(shù)。對于的每一種結(jié)合方案，其最后的那次乘法運(yùn)算，必是的相乘結(jié)果P1和的結(jié)果P2兩項相乘()，即最外層括號所含的兩個因子P1和P2。對于固定的k，P1

36、有種不同的結(jié)合方案，P2則有種。例如P，P1，P2，P，P1，P2因此，總的方案數(shù)是顯然，。事實(shí)上，n個數(shù)連乘積的結(jié)合方案與凸n1邊形的三角形剖分是一一對應(yīng)的。圖3.4.5給出了n4時的對應(yīng)情形類似的問題 還有在n項求和式中，不改變各數(shù)的相對排列次序，只給其插入括號，改變求和順序，不同的結(jié)合方案數(shù)也是圖3.4.5圖3.4.5 n4時連乘積與凸5邊形三角剖分的對應(yīng)關(guān)系例3.4.9 具有n個結(jié)點(diǎn)的所有不同的二叉樹的個數(shù)是(解) 二叉樹是一種重要的樹形結(jié)構(gòu)。其特點(diǎn)是每個結(jié)點(diǎn)都是一棵子樹的根，而且它至多有兩棵子樹。因此可以歸納定義二叉樹為結(jié)點(diǎn)的有限集合，該集合或者是空集，或者是由一個根(一個特定結(jié)點(diǎn))

37、及兩個不相交的被稱作這個根的左子樹和右子樹所組成。二叉樹與計算機(jī)算法關(guān)系密切，在算法研究中引出了二叉樹的計數(shù)問題，即具有n個結(jié)點(diǎn)的所有結(jié)構(gòu)上不同的二叉樹有多少個？令表示n個結(jié)點(diǎn)的二叉樹總數(shù)，容易看出，。圖3.4.6給出了含有3個結(jié)點(diǎn)的所有不同的二叉樹。對于一般情形，二叉樹有一個根結(jié)點(diǎn)及n1個非根結(jié)點(diǎn)，后者又可分為兩個子集，分別構(gòu)成左子樹和右子樹。不失一般性，設(shè)左子樹有k個結(jié)點(diǎn)，則右子樹有n1k個結(jié)點(diǎn)。于是作為根的左子樹的所有可能的二叉樹的數(shù)目是，作為根的右子樹的所有可能的二叉樹的數(shù)目是 (k0,1,n1) 。因此，由乘法原理和加法原理便知令，再與（3.4.2）比較即得，所以有圖3.4.6 具有

38、3個結(jié)點(diǎn)的二叉樹例3.4.10 有n個結(jié)點(diǎn)的所有不同的有序樹的個數(shù)是(解) 有序樹是實(shí)際應(yīng)用中另一種重要的樹形結(jié)構(gòu)。當(dāng)一棵樹中任何一個結(jié)點(diǎn)的諸子樹的相對次序要考慮時，它就是有序樹。眾所周知，任何一個有序樹都可用二叉樹表示。同時注意到，這棵二叉樹的根的右子樹是空二叉樹，故具有n個結(jié)點(diǎn)的有序樹和具有n1個結(jié)點(diǎn)的二叉樹之間存在一一對應(yīng)的關(guān)系。因此，有n個結(jié)點(diǎn)的有序樹的個數(shù)為，即。例如，有4個結(jié)點(diǎn)的結(jié)構(gòu)不同的有序樹共有個，如圖3.4.7所示，它們分別與圖3.4.6的有3個結(jié)點(diǎn)的二叉樹一一對應(yīng)。圖 3.4.7 具有4個結(jié)點(diǎn)的有序樹有序樹與二叉樹的對應(yīng)規(guī)則：有序樹的長子樹作二叉樹的左子樹，次弟作右子樹。參

39、見圖3.4.8。圖3.4.8圖 3.4.8 用二叉樹表示有序樹例3.4.11 由n個1和n個0組成的2n位的二進(jìn)制數(shù)，要求從左向右掃描，1的累計數(shù)不小于0的累計數(shù)，試求這樣的二進(jìn)制數(shù)有多少？解 解法一：設(shè)滿足條件的二進(jìn)制數(shù)有個。將其視為由字符0和1構(gòu)成的二進(jìn)制串，現(xiàn)分類統(tǒng)計其個數(shù)如下：設(shè)從左向右掃描到第2位時（1），第一次出現(xiàn)了0的個數(shù)等于1的個數(shù)。那么在此之前，掃描到任何一位時，1的個數(shù)總是大于0的個數(shù)。例如下面的二進(jìn)制串：1110001100（k=5），1101001100（k=3），1101010010（k=4），1101010100（k=5）設(shè)具有這種性質(zhì)的串有個，則=這是因?yàn)榭梢詫⒎?/p>

40、合題目要求的串分為前后兩個子串，前子串共2位，后子串有2(n-k)位。首先，由題目的條件知，后子串也是符合題目要求的二進(jìn)制串，只是其長度為2(n-k)，故有個。其次，針對前子串，由其性質(zhì)知，當(dāng)去掉第1位和第2位時，剩下的2(k1)位串也符合題目條件，故前子串有個。 由乘法法則，具有此性質(zhì)的串共有個。而相應(yīng)于不同的值（k=1,2,n），兩類這樣的二進(jìn)制串不可能互相有重復(fù)的情況，故由加法法則，所求的串的個數(shù)為=+=+且有=1。另外，觀察上式，可知應(yīng)有=1。參照例3.4.9中關(guān)于數(shù)列所滿足的遞推關(guān)系的解法，可知=解法二：用排列組合的方法求解。詳見本教材的配套資料組合數(shù)學(xué) 學(xué)習(xí)指導(dǎo)書中關(guān)于第一章習(xí)題3

41、2的求解過程。3.5 應(yīng) 用例3.5.1 求下列行列式的值。（解）利用行列式的性質(zhì)，將其按第一行展開得再將第二個n1階行列式按第一列展開得即故得定解問題其特征根為 x1（二重），所以通解為其中A、B為任意常數(shù)，代如初值得，所以即n1.例3.5.2 （錯排問題）n個有序元素的一個排列，若每個元素都不在其原來應(yīng)在的位置，則稱該排列為錯位排列，簡稱錯排。具體地說，如自然數(shù)1，2，n本身就是一個由小到大的有序排列，現(xiàn)在打亂順序重排，要求數(shù)不在第個位置，就是錯位排列。求所有錯位排列的數(shù)目Dn，就是錯排問題。（1）n較小時的Dnn1，1的錯排數(shù)為D10.n2，12的錯排為 21，錯排數(shù)D21.n3，123

42、的錯排為： 312和231，錯排數(shù)D3兩個錯排可以理解為在自然排列123中先將12錯排后得213，再在213中將3分別與1或2互換位置而得。n4，錯排情形分為三種(共兩類)（1）4321，3412，2143：4分別與1，2，3中某一個互換位置，其余兩元素錯排；（2.1）4123，3421，3142： 4與123的一個錯排312構(gòu)成3124，再將4分別與各數(shù)互換；（2.2）4312，2413，2341：針對123的錯排231，方法同(2.1)。（2）一般規(guī)律由此可以看出產(chǎn)生錯排的一種方法：針對n個數(shù)1n的自然順序排列12n ，任取其中一數(shù)（ n），將所有錯排分為兩類：（1）與其它某數(shù)互換位置后，

43、其余的n2個數(shù)錯排，共得(n1) Dn2個錯排；（2）在原位置不動，其它n1個數(shù)先錯排，然后再與其中每一個數(shù)互換位置可得(n1) Dn1個錯排。（3）Dn的遞推關(guān)系反推可知，D0 1。（4）Dn的不同表示可以證明Dn與滿足遞推關(guān)系的數(shù)列是同一數(shù)列。即T1，T2（4）求解解之得（見；例3.3.4） Dn n! 當(dāng)n充分大時，可得Dn的非常簡單的近似公式Dn （n1） 且這是因?yàn)閚!n! Dn， 即Dn 例3.5.3 (經(jīng)濟(jì)模型) 由諾貝爾獎獲得者Paul Samuelson于1939年提出。用an表示第n年國民總收入，g(n)表示政府支出，cn表示私人消費(fèi)支出，表示私人的投資，需要知道的是一個基

44、本的假設(shè)是： cn與an1成正比，即按照經(jīng)濟(jì)學(xué)的說法，常數(shù)稱為消費(fèi)的臨界傾向。再設(shè) 式中是非負(fù)常數(shù)，稱為加速系數(shù)。所以從而對一切n2，有即例3.5.4 某粒子反應(yīng)器內(nèi)有高能自由粒子，低能自由粒子和核子3種，假設(shè)一個高能粒子撞擊一個核子且被吸收引起它放射出3個高能粒子和一個低能粒子，一個低能粒子撞擊核子且被吸收并引起它放出兩個高能粒子和一個低能粒子。設(shè)開始n0微妙時，在具有核子的系統(tǒng)里放入一個高能粒子，問第n微妙時系統(tǒng)中高能、低能粒子各有多少？（解）設(shè)第n微妙時，系統(tǒng)里有高能自由粒子an個，低能自由粒子bn個，由條件知a0 1， b0 0并有遞推關(guān)系解之得例3.5.5 核反應(yīng)堆中有，兩種粒子，每單位時間，一個粒子分裂為3個粒子，1個粒子分裂為2個粒子和一個粒子，假設(shè)t0時刻，反應(yīng)堆中只有1個粒子，那么，在t 100時刻，該反應(yīng)堆中、粒子各有多少，總數(shù)為何?（解）設(shè)tn時刻，粒子有an個，粒子有bn個，由題意可得定解問題由上可得an bn1 3 an2 2 bn23 an2 2 an1b0 a1 0，于是， an 的定解問題為