遞推關(guān)系和生成函數(shù)

1、1第七章第七章 遞推關(guān)系和生成函數(shù)遞推關(guān)系和生成函數(shù)7.1 某些數(shù)列某些數(shù)列 許多組合學(xué)計數(shù)問題都涉及到一個參數(shù)，許多組合學(xué)計數(shù)問題都涉及到一個參數(shù)，例如例如hn表示表示1,2,.n的排列數(shù)，的排列數(shù)， hn =n!;那么那么hn 就是就是n的函數(shù)形式，的函數(shù)形式，n就是參數(shù)；在本章里，我就是參數(shù)；在本章里，我們將討論涉及一個整數(shù)參數(shù)的某些計數(shù)問題的們將討論涉及一個整數(shù)參數(shù)的某些計數(shù)問題的代數(shù)求解方法。我們或者能得到一個顯式公式，代數(shù)求解方法。我們或者能得到一個顯式公式，或者能得到一個函數(shù)，即或者能得到一個函數(shù)，即生成函數(shù)生成函數(shù)。2 在在高等數(shù)學(xué)高等數(shù)學(xué)“無窮級數(shù)無窮級數(shù)”章節(jié)中，我們知章節(jié)

2、中，我們知 道函數(shù)道函數(shù) f(x)有有n+1階導(dǎo)數(shù)時階導(dǎo)數(shù)時可以轉(zhuǎn)化成冪級數(shù)，可以轉(zhuǎn)化成冪級數(shù)，例如：例如： f(x)在在x0 = 0 處展開成處展開成麥克勞林級數(shù)：麥克勞林級數(shù)：.!)0(.! 2)0(! 1)0()0(!)0()()(210)( nninnxnfxfxffxnfxf3 或者或者在在x0 處展開成處展開成泰勒級數(shù)：泰勒級數(shù)：.)(!)(.)(!2)()(! 1)()()(!)()(00200000000 nnninnxxnxfxxxfxxxfxfxxnxfxf我們在二項式系數(shù)討論中也有：我們在二項式系數(shù)討論中也有：nkknxknxxf0)1()(4 上述由函數(shù)展開成級數(shù)的問題

3、，反過來就上述由函數(shù)展開成級數(shù)的問題，反過來就是由級數(shù)（數(shù)列）生成函數(shù)的問題。是由級數(shù)（數(shù)列）生成函數(shù)的問題。 冪級數(shù)（有限或無限）冪級數(shù)（有限或無限） 是我們經(jīng)常要用到的級數(shù)，也把它稱為數(shù)列是我們經(jīng)常要用到的級數(shù)，也把它稱為數(shù)列ak （k = 1,2,）的）的生成函數(shù)生成函數(shù)或或母函數(shù)母函數(shù)。 實際上決定冪級數(shù)性質(zhì)的因素完全是實際上決定冪級數(shù)性質(zhì)的因素完全是xn的的系數(shù)系數(shù)ak 。0)(kkkxaxf5 7.1 某些數(shù)列某些數(shù)列 本次課首先討論由數(shù)列生成遞歸關(guān)系本次課首先討論由數(shù)列生成遞歸關(guān)系 令令 h0, h1, h2, ,hn, 是一個數(shù)列。其是一個數(shù)列。其中中 hn稱作該數(shù)列的稱作該數(shù)

4、列的通項通項或或生成項生成項。 對于上述數(shù)列，定義其對于上述數(shù)列，定義其部分和部分和如下：如下： s0 = h0 s1 = h0 + h1 niinhS06 則由部分和則由部分和 s0, s1, s2, , sn, 亦然構(gòu)成數(shù)列。亦然構(gòu)成數(shù)列。 我們熟悉的數(shù)列有：我們熟悉的數(shù)列有： 算術(shù)數(shù)列算術(shù)數(shù)列：其中每個后項比前項大一個常數(shù)：其中每個后項比前項大一個常數(shù)q。 幾何數(shù)列幾何數(shù)列：其中每個后項是前項的：其中每個后項是前項的q倍。倍。 一旦我們指定了初始項一旦我們指定了初始項h0和常數(shù)和常數(shù)q，上述兩個數(shù)，上述兩個數(shù)列的序列就唯一確定了：列的序列就唯一確定了： 算術(shù)數(shù)列：算術(shù)數(shù)列： h0, h0

5、+q, h0+hq, h0+nq.7 通項為：通項為： hn= h0+ nq (n1) 相鄰兩項有關(guān)系：相鄰兩項有關(guān)系： hn= hn-1+ q (n1) 前前n項和公式：項和公式： 幾何數(shù)列：幾何數(shù)列： h0, qh0, q2h0, q3h0, qnh0. 通項為：通項為： hn= qnh0 (n1)相鄰兩項有關(guān)系：相鄰兩項有關(guān)系： hn= qhn-1 (n1)前前n項和公式：項和公式：2)1()1()(010nqnhniqhSni)1()1()1(1100101qhnqhqqhqSnnii8 例：算術(shù)序列：例：算術(shù)序列： 正偶數(shù)序列可以表示為：正偶數(shù)序列可以表示為： 2, 4, 6, .

6、2n. (n1) 即：即： h0= 2，q = 2 正奇數(shù)序列可以表示為：正奇數(shù)序列可以表示為： 1, 3, . 2n-1. (n1) 即：即： h0= 1，q = 2 常數(shù)序列可以表示為：常數(shù)序列可以表示為： 5, 5, 5, . 5. 即：即： h0= 5，q = 09例：幾何序列：例：幾何序列： 冪指數(shù)序列可以表示為：冪指數(shù)序列可以表示為： 1, 2, 4, . 2n. (n0) 即：即： h0= 1，q = 2 通項通項 hn= 2n (n0) 一般計數(shù)序列：一般計數(shù)序列： 5, 35, 325,. 3n5,. (n0) h0= 5，q = 3 通項通項 hn= 3n 5 10例：確定

7、平面一般位置上的例：確定平面一般位置上的n個互相交疊的圓所個互相交疊的圓所 形成的區(qū)域數(shù)？形成的區(qū)域數(shù)？分析：設(shè)分析：設(shè)hn是由是由n個互相個互相交疊的圓所形成的區(qū)域數(shù)。交疊的圓所形成的區(qū)域數(shù)。 所謂相交是指兩個圓的所謂相交是指兩個圓的交點必須是交點必須是2個并且僅僅個并且僅僅2個，個，相切和相離都不成立。我們有相切和相離都不成立。我們有 h0 = 1；一個平面；一個平面11 區(qū)域；區(qū)域； h1 = 2，一個圓圍成的圓內(nèi)和圓外平面，一個圓圍成的圓內(nèi)和圓外平面 區(qū)域；區(qū)域； h2 = 4；如果是如果是 h3 ，在，在h2 的基礎(chǔ)上的基礎(chǔ)上增加一個圓，圍成的區(qū)域?qū)⒃黾右粋€圓，圍成的區(qū)域?qū)⒃黾釉黾?

8、個，如圖中紅色的區(qū)域。個，如圖中紅色的區(qū)域。 h3=h2+ x = h3+ 2(3-1)；再加；再加一個蘭色的圓將多一個蘭色的圓將多6個區(qū)域個區(qū)域 h4=h3+ y = h3+ 2(4-1)14233217654812 我們得到遞推關(guān)系如下：設(shè)我們得到遞推關(guān)系如下：設(shè)n2，對于，對于 n 1 個一般位置上互相交替的圓已經(jīng)在平面是畫個一般位置上互相交替的圓已經(jīng)在平面是畫出，它們形成出，它們形成hn1個區(qū)域。再加上第個區(qū)域。再加上第n個圓使得個圓使得在一般位置上放置在一般位置上放置n 個個互相交替的圓?；ハ嘟惶娴膱A。 前前n 1個圓的每一個與第個圓的每一個與第n 個都交于兩點，個都交于兩點，得到得

9、到2(n1)個不同的點：個不同的點：p1, p2,p2(n-1)。他們。他們把第把第n個圓分成個圓分成2(n1)條?。簵l弧：13 p1p2, p2p3, p3p4, . 這這2(n1)條弧的每一條能將前條弧的每一條能將前(n1)個圓形個圓形成的區(qū)域一分為二，得到成的區(qū)域一分為二，得到2(n1)個區(qū)域，就是個區(qū)域，就是說，增加第說，增加第n個圓，就增加個圓，就增加2(n-1) 個區(qū)域。個區(qū)域。 分析分析hn與與hn-1 的關(guān)系，我們能發(fā)現(xiàn)區(qū)域數(shù)的關(guān)系，我們能發(fā)現(xiàn)區(qū)域數(shù)量量hn與畫圓的數(shù)量與畫圓的數(shù)量n的關(guān)系：的關(guān)系：14hn=hn-1+2(n-1) = hn-2 +2(n-2) +2(n-1)

10、=hn-3 +2(n-3) +2(n-2) +2(n-1) . = h1 +2(1)+2(2)+. +2(n-2) +2(n-1) = 2 + 21+22+. +2(n-1)2()(22) 1)(11 (22) 1.21 (222nnhnnnnnhn15FibonacciFibonacci序列序列( (斐波那契序列斐波那契序列) ) 意大利數(shù)學(xué)家意大利數(shù)學(xué)家Fibonacci在在13世紀初提出過世紀初提出過如下一個有趣問題：如下一個有趣問題： 年前養(yǎng)了一對小兔（雌雄各一），這對兔子年前養(yǎng)了一對小兔（雌雄各一），這對兔子中的母兔從中的母兔從2月份開始每月都產(chǎn)下一對雌雄各一月份開始每月都產(chǎn)下一對雌

11、雄各一的小兔。每對新生小兔間隔一月后也開始每個月的小兔。每對新生小兔間隔一月后也開始每個月都產(chǎn)下一對新的小兔（雌雄各一）。如是而下去，都產(chǎn)下一對新的小兔（雌雄各一）。如是而下去，16 假定兔子都不死亡，兔子都不多生小兔，生的假定兔子都不死亡，兔子都不多生小兔，生的 小兔性別比例保持不變，不考慮近親繁殖的小兔性別比例保持不變，不考慮近親繁殖的問題，問一年后共有多少對兔子？問題，問一年后共有多少對兔子？ 假定年初為假定年初為1月份月份,年后為年后為13月，若設(shè)月，若設(shè) fn 為第為第n個月所有的兔子對數(shù)，不難推算各月兔子對數(shù)個月所有的兔子對數(shù)，不難推算各月兔子對數(shù)與月份數(shù)的關(guān)系為與月份數(shù)的關(guān)系為:

12、17 著名的著名的Fibonacci數(shù)列由此而得名。這一數(shù)列數(shù)列由此而得名。這一數(shù)列的增長速度是很快的。其中，第二年年底兔子有的增長速度是很快的。其中，第二年年底兔子有50 000對，第三年年底兔子有對，第三年年底兔子有15 000 000對，第對，第 55 項就超過了項就超過了1萬億對。萬億對。第一列下來單獨定義第一列下來單獨定義。 我們已經(jīng)算出我們已經(jīng)算出 f1 = 1, f2 = 1, f3 = 2, f4 = 3。月份月份012345678兔子對兔子對01123581321 fn f0 f1 f2 f3 f4 f5 f6 f7 f8 18則由各月兔子數(shù)不難證得如下遞推式成立則由各月兔子

13、數(shù)不難證得如下遞推式成立: f n = f n-1 + f n-2 (n 3) 在第在第n月時，圍欄內(nèi)的兔子可以分為兩個部分：月時，圍欄內(nèi)的兔子可以分為兩個部分：一是第一是第n-1月時圍欄已經(jīng)有的兔子數(shù)，二是第月時圍欄已經(jīng)有的兔子數(shù)，二是第n-1月出生的新兔子數(shù)，由于兔子的成熟期是一月出生的新兔子數(shù)，由于兔子的成熟期是一個月，每對兔子只生一對小兔，第個月，每對兔子只生一對小兔，第n-1月出生月出生的新兔子數(shù)就是第的新兔子數(shù)就是第n-2月?lián)碛械睦贤米訉?shù)。月?lián)碛械睦贤米訉?shù)。19 由此我們可以求出下列兔子數(shù)：由此我們可以求出下列兔子數(shù)： f 5 = f 4 + f 3 = 3 + 2 = 5 f

14、 6 = f 5 + f 4 = 5 + 3 = 8 f 7 = f 6 + f 5 = 8 + 5 = 13 f 8 = f 7 + f 6 = 13 +8 =21 f 9 = f 8 + f 7 = 21 +13 = 34 f 10 = f 9 + f 8 = 34 +21 =55 f 11 = f 10 + f 9 = 55 +34= 89 20 如果定義如果定義 f 0 = 0， f 2 = f 1 + f 0 =1+0=1 滿足滿足 關(guān)系和初始條件：關(guān)系和初始條件： f n = f n-1 + f n-2 (n 2) f 0 = 0 ； f 1 = 1 的數(shù)列叫做的數(shù)列叫做斐波那契序

15、列斐波那契序列。序列的項叫做。序列的項叫做斐波斐波那契數(shù)那契數(shù)。公式中的遞推關(guān)系叫做。公式中的遞推關(guān)系叫做斐波那契遞歸斐波那契遞歸。 斐波那契序列有許多的性質(zhì)，通過下面的斐波那契序列有許多的性質(zhì)，通過下面的21 兩個例題給出兩個性質(zhì)：兩個例題給出兩個性質(zhì)：例：例：斐波那契序列的項的部分和為：斐波那契序列的項的部分和為： Sn = f0 + f1 + f2 +.+ +.+ fn = fn+2 1解：用歸納法證明：解：用歸納法證明： 當(dāng)當(dāng)n=0時時 左左 = f0 = f2 1=1 1=0 成立成立 令令n0時對時對Sn成立，證明用成立，證明用n+1取代取代n后公式仍成后公式仍成立。立。22Sn+

16、1 = f0 + f1 + f2 +.+ +.+ fn+1 = fn+2 1 + + fn+1 =fn+2 + + fn+1 1 = = fn+3 1 公式成立公式成立例：斐波那契數(shù)是偶數(shù)當(dāng)且僅當(dāng)例：斐波那契數(shù)是偶數(shù)當(dāng)且僅當(dāng)n能夠被能夠被3整數(shù)整數(shù). 解：由前三個數(shù)解：由前三個數(shù)f 0 ， f 1 ，f 2的值。的值。 f 0 =0， f 1 =1，f 2 =1；由它們?nèi)椙蟮?；由它們?nèi)椙蟮膄 3 ： f 3 =f 2+ f 1=1+1=2 是偶數(shù)，其項數(shù)是偶數(shù)，其項數(shù)n=3能能被被3 3整除整除. . 23 它們的奇偶性有下列特征：它們的奇偶性有下列特征： f3 是：偶是：偶+奇奇+奇奇=

17、偶偶； f4=f3+f2 是：偶是：偶+奇奇=奇奇； f5=f4+f3 是：是：奇奇+偶偶 =奇奇； f6=f5+f4 是：是：奇奇+奇奇=偶；偶； f 6 的項數(shù)的項數(shù)n=6也能也能被被3 3整除。整除。24斐波那契遞推公式斐波那契遞推公式 由斐波那契遞推公式由斐波那契遞推公式 f n = f n-1 + f n-2 得到：得到： f n f n-1 f n-2 = 0 假設(shè)假設(shè)斐波那契數(shù)具有冪函數(shù)形式：斐波那契數(shù)具有冪函數(shù)形式：f n = qn其中其中q是一個非零數(shù)。代入上式是一個非零數(shù)。代入上式:qn qn-1qn-2= 0解這個方程解這個方程 qn-2 (q2 q 1)= 0 只能是只

18、能是 q2 q 1 = 0;251;25121qq25因此因此由于兩個由于兩個解都是斐波那契關(guān)系的特解，由斐波解都是斐波那契關(guān)系的特解，由斐波那契遞推關(guān)系是線性的和齊次的，一般的通解：那契遞推關(guān)系是線性的和齊次的，一般的通解：;251;251nnnnff是常數(shù)2121,;251251CCCCfnnn將將n=0，1時時f n 的初值代入確定系數(shù)的初值代入確定系數(shù)C1,C226 n=0，時，時: n=1 ，時，時: 21020102512510CCCCf5151125125112112111CCCCf；解得：將上述值代入公式得到下列公式：將上述值代入公式得到下列公式：27 定理定理7.1.1 Fi

19、bonacci(斐波那契斐波那契) 數(shù)滿足公式數(shù)滿足公式 雖然雖然斐波那契數(shù)斐波那契數(shù)(兔子數(shù)兔子數(shù))都是整數(shù)，可是在都是整數(shù)，可是在公式中卻包含了無理數(shù)，而求公式中卻包含了無理數(shù)，而求f n 時這些無理時這些無理數(shù)又神奇地消失了，這個表達式也就是斐波那數(shù)又神奇地消失了，這個表達式也就是斐波那契序列的通項公式。契序列的通項公式。)0(2515125151nfnnn28例：令例：令f0, f1, f2, , fn, 滿足下面給出的滿足下面給出的斐波那斐波那 契遞推關(guān)系和契遞推關(guān)系和改變改變的初始條件的初始條件： fn = fn-1 + fn-2 (n 2) f0 = 2 ; f1 = 1 的數(shù)列

20、，試給出的數(shù)列，試給出fn的計算公式。的計算公式。解：將解：將 f0 = 2 ; f1 = 1代入代入斐波那契公式得：斐波那契公式得： f0 = 2 = C1+ C229 解上述方程得：解上述方程得：nnnfCC251525251525525,52521121112512511CCf 如果將如果將斐波那契遞序列的前幾項改變成斐波那契遞序列的前幾項改變成 f0=1，f1=1， f2=2 ，.；即去掉；即去掉0這第一項，這第一項，30 對無窮級數(shù)來說，減少或增加有限項不會對無窮級數(shù)來說，減少或增加有限項不會改變級數(shù)的斂散性，我們以改變級數(shù)的斂散性，我們以1作為作為斐波那契遞斐波那契遞序列的第一、二

21、項，遞推關(guān)系不變，并且序列的第一、二項，遞推關(guān)系不變，并且設(shè)設(shè)斐斐波那契數(shù)列生成的波那契數(shù)列生成的函數(shù)為函數(shù)為f (x)：22222111.)(nnnnnnnnnnxfxxfxfxxfxfxfxfxf31)()()()()()(222222112212212xfxfxxxfxxfxxfxxxfxfxxffxxfxxfnnnnnnnnnnnnnnnnnn32 此此斐波那契數(shù)列斐波那契數(shù)列的又一個的又一個生成函數(shù)生成函數(shù)。設(shè)設(shè)1- x - x2 = 0 的二根為的二根為、，分解多項式，分解多項式:21)(xxxxf解得：1512)51(242511512)51(24251注意區(qū)別于前面方程注意區(qū)別

22、于前面方程：q2 q 1 = 0根的關(guān)系。根的關(guān)系。33,51,511)(250)2511)(2511()(5)(2)(25112511)2511)(2511(1)(2BABABAxxABBAxBAxBxAxxxxxxxf所以34由冪級數(shù)展開公式：當(dāng)由冪級數(shù)展開公式：當(dāng) x 1時時xxxlinxxlinSlinxxxxkkkkkknkk11111)1(1.120我們可以將公式中的兩個分式展開成級數(shù)形式：我們可以將公式中的兩個分式展開成級數(shù)形式：)1111(51)(xxxf3555)(51)()(51)1111(51)(00000nnnnnnnnnnnnnnnnnnfxfxxxxxxxf36)0

23、()251(5155nfnnnnn由于由于0)251(nn那么那么12511251； 與原來的公式比較要少一項，這正是我們與原來的公式比較要少一項，這正是我們省掉了省掉了0這第一項后得到地斐波那契數(shù)列的近這第一項后得到地斐波那契數(shù)列的近似計算公式。似計算公式。37比較這相鄰兩個比較這相鄰兩個斐波那契數(shù)的關(guān)系有：斐波那契數(shù)的關(guān)系有：.618033.012511lim1nnnff 這個數(shù)字正好是建筑、美學(xué)等領(lǐng)域的這個數(shù)字正好是建筑、美學(xué)等領(lǐng)域的黃黃金分割位金分割位。 f nf n-1= 0.618f n38關(guān)于關(guān)于斐波那契數(shù)，我們用豎式加法證明一些關(guān)系斐波那契數(shù)，我們用豎式加法證明一些關(guān)系 1)

24、f 1+ f 2+.+ f n= f n+21; 證明：由證明：由 f n+2= f n+ f n+1 得：得： f 1= f 3 f 2 ; f 2= f 4 f 3 ; . +) f n= f n+2 f n-1 ; f 1+ f 2+.+ f n= f n+2 f 2 = f n+21 證畢證畢39 2) f 1+ f 3+.+ f 2n-1 = f 2n ; 證明：由證明：由 f n+2= f n+ f n+1 得：得： f 1= f 2 = 1 ; f 3= f 4 f 2 ; f 5= f 6 f 4 ; . +) f 2n-1= f 2n f 2n-2 ; f 1+ f 3+.+

25、 f 2n-1 = f 2n 證畢證畢403) f12 + f22 + f32 .+ fn2 = f n f n+1 ; 證明：由證明：由 f n+2= f n+ f n+1 得：得： f12 = f 1 f 1 = f 2 f 1 f22 = f 2 f 2 = f 2(f 3 f 1) = f 2f 3 f 2 f 1 f32 = f 3 f 3 = f 3(f 4 f 2) = f 3f 4 f 3 f 2 . +) fn2= f n f n = f n (fn+1 fn-1) = fnfn+1 f n f n-1 f12 + f22 + f32 .+ fn2 = f n f n+1 ;

26、 證畢證畢41 例：確定例：確定2n棋盤用多米諾骨牌完美覆蓋的棋盤用多米諾骨牌完美覆蓋的 方法數(shù)方法數(shù)hn 解：解： h1=1 ； h2=2 h3=3 ； 將將hn分為兩分為兩 種情況：種情況：A B A是左邊第一個是左邊第一個骨牌必須豎直擺放，其余骨牌必須豎直擺放，其余n-1個個骨牌不限制位置的覆蓋的集合。骨牌不限制位置的覆蓋的集合。B是左邊第一是左邊第一2 n2 n2 (n-1)2 (n-2)1nh2nh42骨牌不豎直擺放，即水平擺放骨牌不豎直擺放，即水平擺放(同時還有一個同時還有一個) 其余其余n-2個骨牌不限制位置的覆蓋的集合。個骨牌不限制位置的覆蓋的集合。 所以所以A中的完美覆蓋數(shù)就

27、等于中的完美覆蓋數(shù)就等于2(n-1)棋棋盤的完美覆蓋數(shù)：盤的完美覆蓋數(shù)： |A| =hn-1 B中的完美覆蓋數(shù)就等于中的完美覆蓋數(shù)就等于2(n-2)棋盤的棋盤的完美覆蓋數(shù)完美覆蓋數(shù),由于由于骨牌是相同的，骨牌是相同的，B中前兩個中前兩個水平放置的水平放置的骨牌沒有上下區(qū)分；骨牌沒有上下區(qū)分； |B| = hn-243 由加法原理由加法原理 故故 hn=|A|+|B|=hn-1+hn-2 (n 2)定義定義n= 1時，即空覆蓋：時，即空覆蓋：h0=1，也是個，也是個斐波那斐波那契序列。契序列。 下面說明下面說明斐波那契數(shù)作為二項式系數(shù)的和斐波那契數(shù)作為二項式系數(shù)的和出現(xiàn)的。出現(xiàn)的。44 定理定理

28、7.1.2沿沿Pascal三角形圖左邊向上對角線上三角形圖左邊向上對角線上的二項式系數(shù)的和是的二項式系數(shù)的和是斐波那契數(shù)，更精確地說，斐波那契數(shù)，更精確地說，第第n個個斐波那契數(shù)是：斐波那契數(shù)是：的弱取整。是其中21211.231201nnkkknnnnfn450123456111111112345613610151410201515161n0n1n2n3n4n5n6nPascal三角形圖三角形圖f1=1f2=1f3=2f4=3f5=5f6=8f7=1346證明：由組合數(shù)的定義可知：當(dāng)證明：由組合數(shù)的定義可知：當(dāng) kn 時時 所以我們可以把原式改寫成：所以我們可以把原式改寫成：1 2 31 2 3(11) (2 2) (3 3)3 1 22 3 1(3 2) (1 3) (2 1)2 3 13 2 1(2 3) (31) (1 2) 并置，