組合數(shù)學(xué)-第4章-遞推關(guān)系與母函數(shù)

1、 主講人：蘇建忠地址：系統(tǒng)生物學(xué)教研室組合數(shù)學(xué)第4章 遞推關(guān)系與母函數(shù) 本章主要介紹遞推關(guān)系的建立及幾種常見的求解方法： 母函數(shù)法 常系數(shù)齊次遞推關(guān)系 常系數(shù)非齊次遞推關(guān)系4.1 遞推關(guān)系建立例1-14.1 遞推關(guān)系的建立例 題例1、在一個(gè)平面上有一個(gè)圓和n條直線，這些直線中的每一條在圓內(nèi)都同其他的直線相交。如果沒有多于三條的直線相交于一點(diǎn)，試問這些直線將圓分成多少個(gè)不同區(qū)域？ 4.1 遞推關(guān)系建立例1-24.1 遞推關(guān)系的建立例 題解：要求解這個(gè)問題，首先必須建立遞推關(guān)系，然后求解遞推關(guān)系即可。設(shè)這n條直線將圓分成的區(qū)域數(shù)為an，如果有n-1條直線將圓分成an-1個(gè)區(qū)域，那么再加入第n條直線

2、與在圓內(nèi)的其他n-1條直線相交。顯然，這條直線在圓內(nèi)被分成n條線段，而每條線段又將第n條直線在圓內(nèi)經(jīng)過的區(qū)域分成兩個(gè)區(qū)域。這樣，加入第n條直線后，圓內(nèi)就增加了n個(gè)區(qū)域。而對于n=0，顯然有a0=1，于是對于每個(gè)整數(shù) n，可以建立如下帶初值的遞推關(guān)系 4.1 遞推關(guān)系的建立例 題例2、在一個(gè)平面中，有n個(gè)圓兩兩相交，但任二個(gè)圓不相切，任三個(gè)圓無公共點(diǎn)，求這n個(gè)圓把平面分成多個(gè)區(qū)域？ 解：設(shè)這n個(gè)圓將平面分成an個(gè)區(qū)域。如圖。易見 ，a1=2, a2=4?，F(xiàn)在假設(shè)前n-1個(gè)圓將平面分成了an-1個(gè)區(qū)域，當(dāng)加入第n個(gè)圓時(shí)，由題設(shè)這個(gè)圓與前面的n-1個(gè)圓一定交于2(n-1)個(gè)點(diǎn)，這2(n-1)個(gè)點(diǎn)把第

3、n個(gè)圓分成2(n-1)條弧，而每條弧正好將前面的 n-1個(gè)圓分成的區(qū)域中的其經(jīng)過的每個(gè)區(qū)域分成2個(gè)區(qū)域，故新加入的第n個(gè)圓使所成的區(qū)域數(shù)增加了2(n-1) 。因此可以建立如下帶初值的遞推關(guān)系： 求解這個(gè)遞推關(guān)系可以得到問題的解答。4.1 遞推關(guān)系建立例2-14.1 遞推關(guān)系的建立例 題例3、“Hanoi塔”問題：n個(gè)大小不一的圓盤依半徑的大小，從下而上的套在柱子A上。如圖所示?，F(xiàn)要求將所有的圓盤從柱子A上全部移到柱子C上，每次只允許從一根柱子上轉(zhuǎn)移一個(gè)圓盤到另一根柱子上，且在轉(zhuǎn)移過程中不允許出現(xiàn)大圓盤放到小圓盤上。試問至少要轉(zhuǎn)移多少次才能將柱子上的n個(gè)圓盤全部轉(zhuǎn)移到柱子C上去？ 4.1 遞推關(guān)

4、系建立例2-24.1 遞推關(guān)系的建立例 題解：用Hn表示從一根柱子上的n個(gè)圓盤全部轉(zhuǎn)移到另一根柱子上的轉(zhuǎn)移次數(shù)。顯然，H1=1, H2=3。當(dāng)n3時(shí)，要將柱子A上的n個(gè)圓盤轉(zhuǎn)移到柱子C上，可以這樣設(shè)想。先把柱子A上的n-1個(gè)圓盤轉(zhuǎn)移到柱子B上，這需要轉(zhuǎn)移Hn-1次；然后把柱子A上最后一個(gè)圓盤轉(zhuǎn)移到柱子C上，顯然這需要轉(zhuǎn)移一次；最后再把柱子B上的n-1個(gè)圓盤轉(zhuǎn)移到柱子C上，這也需要轉(zhuǎn)移Hn-1次。經(jīng)過這些步驟后，所有A上的n個(gè)圓盤就全部轉(zhuǎn)移到柱子C上。由加法法則，這一共轉(zhuǎn)移了2Hn-1+1次。于是可以建立如下帶初值的遞推關(guān)系 4.1 遞推關(guān)系建立例3-14.1 遞推關(guān)系的建立例 題例4、“Fib

5、onacci兔子問題”也是組合數(shù)學(xué)中的著名問題之一。這個(gè)問題是指：從某一年某一月開始，把雌雄各一的一對兔子放入養(yǎng)殖場中，從第二個(gè)月雌兔每月產(chǎn)雌雄各一的一對新兔。每對新兔也是從第二個(gè)月起每月產(chǎn)一對兔子。試問第n個(gè)月后養(yǎng)殖場中共有多少對兔子？ 4.1 遞推關(guān)系建立例3-24.1 遞推關(guān)系的建立例 題解：設(shè)第n個(gè)月時(shí)養(yǎng)殖場中兔子的對數(shù)為Fn。并定義F0=1，顯然有，F(xiàn)1=1。由于在第n個(gè)月時(shí)，除了有第n-1個(gè)月時(shí)養(yǎng)殖場中的全部兔子Fn-1外，還應(yīng)該有Fn-2對新兔子，這是因?yàn)樵诘趎-2個(gè)月就已經(jīng)有的每對兔子，在第n個(gè)月里都應(yīng)生一對新的兔子。因此可以建立如下帶初值的遞推關(guān)系 求解上式可以得到我們所需的

6、答案。注：利用該式我們可以推得(F0,F1,Fn,)=(1,1,2,3,5,8,13,21,34,55,)常稱Fn為Fibonacci數(shù)， (F0,F1,Fn,)為Fibonacci數(shù)列。Fibonacci數(shù)列在數(shù)學(xué)中是一個(gè)奇特而又常見的序列，它在算法分析中起著重要的作用。具體性質(zhì)以后討論。4.1 錯(cuò)排問題定理5練習(xí)錯(cuò)排如a1,a2,an為1,2,n的一排列，對所有的i，有aii，稱這種排列為錯(cuò)排Dn 。Dn=(n-1)(Dn-1+Dn-2)，(n3)4.1 遞推關(guān)系定義4.1 遞推關(guān)系的建立定義 4.1設(shè)an為一序列，把該序列中an和它前面幾個(gè)ai (0in-1)關(guān)聯(lián)起來的方程稱做一個(gè)遞推關(guān)

7、系（遞歸關(guān)系）。 如錯(cuò)排數(shù)Dn=(n-1)(Dn-1+Dn-2)，(n3) 和關(guān)系式an=3an-1，(n1)都是遞推關(guān)系。 如a0=d0 , a1=d1, ak=dk，di為常數(shù)(i=0,1,k)，稱為遞推關(guān)系的初值。 如D1=0, D2=1作為初值即可惟一的確定序列(D0,D1, Dn,)，a0=1作為初值即可惟一的確定序列(1,3,32,3n,)。將遞推關(guān)系和初值結(jié)合起來稱為帶初值的遞推關(guān)系。如4.2 普通母函數(shù)概念4.2 母函數(shù)的基本概念定義 4.24.2.1 普通母函數(shù) 注： f(x)是無窮級數(shù)，不管其收斂性； x為形式變元，f(x)為形式冪級數(shù) ； 序列與母函數(shù)一一對應(yīng)； 母函數(shù)是

8、序列的另一表達(dá)形式； 有限序列也可用母函數(shù)表示。給定一無窮序列(a0,a1,an,)(簡記為an)，稱函數(shù) 為序列an的普通母函數(shù)（發(fā)生、生成函數(shù)） 。 4.1 普通母函數(shù)例14.2 母函數(shù)的基本概念例 題4.2.1 普通母函數(shù) 例1、求序列(C(n,0),C(n,1),C(n,2), C(n,n)的普通母函數(shù)。 解：由定義4.1及二項(xiàng)式定理的推論1.9.2有 4.1 普通母函數(shù)例44.2 母函數(shù)的基本概念例 題4.2.1 普通母函數(shù) 例2、求序列(0, 123, 234, n(n+1)(n+2),)的普通母函數(shù)。 4.1 指數(shù)母函數(shù)概念4.2 母函數(shù)的基本概念定義 4.34.2.2 指數(shù)母函數(shù) 注： fe(x)也是形式冪函數(shù)。 經(jīng)?？山Y(jié)合以下公式運(yùn)算：給定一無窮序列(a0,a1,an,)（簡記為an），稱函數(shù) 為序列an的指數(shù)母函數(shù)。 4.1 指數(shù)母函數(shù)例54.2 母函數(shù)的基本概念例 題4.2.2 指數(shù)母函數(shù) 例3、設(shè)n是整數(shù)，求序列(p(n,0), p(n,1), p(n,n)的指數(shù)母函數(shù)fe(x)。 解：由定義4.2及公式P(