組合數(shù)學(xué)幻燈片51

1、 5.15.1遞歸關(guān)系的建立遞歸關(guān)系的建立第五章第五章 遞遞 歸歸 關(guān)關(guān) 系系遞歸關(guān)系是組合數(shù)學(xué)的一個(gè)重要課題它不僅在幾乎所有的數(shù)學(xué)分支中占有重要的地位，而且在計(jì)算機(jī)科學(xué)，特別是算法分析中有著廣泛的應(yīng)用。 在這一節(jié)，我們首先給出遞歸關(guān)系的定義然后用幾個(gè)例子來(lái)說(shuō)明是怎樣建立遞歸關(guān)系的。例如例如 第三章3.3節(jié)中的錯(cuò)排數(shù) D Dn n=(n-1)(D=(n-1)(Dn-1n-1+D+Dn-2n-2) )( (n=3,4,)和關(guān)系式 都是遞歸關(guān)系。)1(31 raarr 設(shè)(a(a0 0,a,a1 1, ,a,ar r, ,) )是一個(gè)序列，把該序列中的ar和它前面的幾個(gè)ai(0ir)關(guān)聯(lián)起來(lái)的方程

2、稱做一個(gè)遞歸關(guān)系 如果遞歸關(guān)系式(5.1)給出了初值D D1 1=0,D=0,D2 2=1=1,那么遞歸關(guān)系式(5.1)連同初值一起就唯一地確定了錯(cuò)排數(shù)序列(D(D1 1,D,D2 2,D,D3 3, ,)=(0,1,2,9,44,265,)=(0,1,2,9,44,265,) )。 同樣，對(duì)于遞歸關(guān)系式(5.2)，若給出初始值 a a1 1=3=3，我們就能確定唯一的序列(3,3(3,32 2, ,3,3r r, ,) )。 由上面遞歸關(guān)系的例子可見(jiàn)，遞歸關(guān)系是計(jì)算序列中各項(xiàng)的有效工具。但如何建立遞歸關(guān)系呢?下面用幾個(gè)實(shí)例來(lái)加以說(shuō)明。 331, 0)(1(012121aaaDDDDnDnnn

3、nn 為方便起見(jiàn)，把式(5.1)和(5.2)連同它們的初值一起統(tǒng)一寫(xiě)成如下形式：稱這種形式為稱這種形式為帶初值的遞歸關(guān)系。帶初值的遞歸關(guān)系。解解：要求解這個(gè)問(wèn)題，首先必須建立遞歸關(guān)系，然后求解遞歸關(guān)系即可。 在一個(gè)平面上有一個(gè)圓和n條直線，這些直線中的每一條在圓內(nèi)都同其他的直線相交。如果沒(méi)有三條的直線相交于一點(diǎn)，試問(wèn)這些直線將圓分成多少個(gè)區(qū)域? 設(shè)這n條直線將圓分成的區(qū)域數(shù)為an， 如果有n-1條直線在圓內(nèi)將圓分成an-1個(gè)區(qū)域，那么，再加入第n條直線與在圓內(nèi)的其他n-1條直線相交。 顯然，這條直線被n-1條直線在圓內(nèi)分成n條線段，而每線段又將第n條直線在圓內(nèi)經(jīng)過(guò)的區(qū)域分成兩個(gè)區(qū)域。 這樣，加

4、入第n條直線后，圓內(nèi)就增加了n個(gè)區(qū)域。而對(duì)于n=0，顯然有a0=1。于是對(duì)于每個(gè)整數(shù)n，可以建立如下帶初值的遞歸關(guān)系：求解遞歸關(guān)系式(5.3)(求解方法將在后幾節(jié)中介紹)得 an=(n2+n+2)/2這就是問(wèn)題的解答。 1)1(01annaann(5.3) “Hanoi塔”問(wèn)題是指：n個(gè)大小不 一的圓盤(pán)依半徑的大小，從下而上的套在柱子A上。如圖5-1所示。圖見(jiàn)書(shū)圖見(jiàn)書(shū)8383頁(yè)頁(yè) 現(xiàn)要求將所有的圓盤(pán)從柱子A上全部轉(zhuǎn)移 到柱子C上，每次只允許從一根柱子上轉(zhuǎn)移一個(gè)圓盤(pán)到另一根柱子上， 且在轉(zhuǎn)移過(guò)程中不允許出現(xiàn)大圓盤(pán)放在小圓盤(pán)上。 試問(wèn)要轉(zhuǎn)移多少次才能將柱子A上的n個(gè)圓盤(pán)全部轉(zhuǎn)移到柱子C上去? A

5、B C 當(dāng)n3時(shí)，要將柱子A上的n個(gè)圓盤(pán)全部轉(zhuǎn)移到柱子C上，可以這樣設(shè)想:先把柱子A上的n-1個(gè)圓盤(pán)轉(zhuǎn)移到柱子B上，這需要轉(zhuǎn)移an-1次，然后把柱子A上的最后一個(gè)大圓盤(pán)轉(zhuǎn)移到柱子C上，顯然這需要轉(zhuǎn)移一次，最后再把柱子B上的n-1個(gè)圓盤(pán)轉(zhuǎn)移到柱子C上，這也需要轉(zhuǎn)移an-1次。 解：設(shè)an表示從一根柱子上的n個(gè)圓盤(pán)全部轉(zhuǎn)移到另一根柱子上的轉(zhuǎn)移次數(shù)。 顯然，a1=1,a2=3。 經(jīng)過(guò)這些步驟后，所有A上的n個(gè)圓盤(pán)就全部轉(zhuǎn)移到柱子C上。由加法規(guī)則加法規(guī)則，這一共轉(zhuǎn)移了2an-1+1次。于是可以建立如下帶初值的遞歸關(guān)系： 1)2(1211anaann(5.4)(5.4) 求解遞歸關(guān)系式(5.4)得 a

6、an n=2=2n n-1-1這就是我們所需要的結(jié)果。 “Fibonacci兔子問(wèn)題”也是組合數(shù)學(xué)中著名問(wèn)題之一。 這個(gè)問(wèn)題是指：從某一年開(kāi)始時(shí)，把雌雄各一一的一對(duì)兔子放入養(yǎng)殖場(chǎng)中，雌兔每月產(chǎn)雌雄各一的一對(duì)新兔。 從第二個(gè)月開(kāi)始每對(duì)新兔也是每月產(chǎn)一對(duì)雌雄各一的兔子。 試問(wèn)第n個(gè)月后養(yǎng)殖場(chǎng)中共有多少對(duì)兔子? 解：解：設(shè)第n個(gè)月開(kāi)始時(shí)，養(yǎng)殖場(chǎng)中兔子的對(duì)數(shù)為Fn。并定義F0=1，顯然有F1=1。 1, 1)2(1021FFnFFFnnn求解式(5.5)就得到我們所需要的答案。(5.5)(5.5) 這是因?yàn)?，在第n-2個(gè)月開(kāi)始就已經(jīng)有的每對(duì)兔子在第n-1個(gè)月里都應(yīng)生一對(duì)新的兔子。因此可以建立如下帶初值

7、的遞歸關(guān)系： 由于在第n個(gè)月開(kāi)始時(shí)，除了有第n-1個(gè)月開(kāi)始時(shí)養(yǎng)殖場(chǎng)中的全部兔子Fn-1外，還應(yīng)該有Fn-2對(duì)兔子 利用式(5.5)可以推得(F0,F1,Fn,)=(1,1,2,3,5,8,13,21,34,55,89,144,233,377,) 常稱F Fn n為Fibonacci數(shù)， (F0,F1,Fn，)為Fibonacci序列。 Fibonacci序列在數(shù)學(xué)中是一個(gè)奇特而又常見(jiàn)的序列，它在算法分析中起著重要的作用。 可以證明，F(xiàn)ibonacci數(shù)具有以下性質(zhì)：120 nniiFF1.1.2.2.3.3.4.4.1211) 1( nnnnFFF102 nnniiFFF12112 nniiF

8、F 在一個(gè)平面中，有n個(gè)圓兩兩相交，但任兩個(gè)圓不相切，任三個(gè)圓無(wú)公共點(diǎn)。求這n個(gè)圓把平面分成多少個(gè)區(qū)域?解：解：設(shè)這n個(gè)圓將平面分成an個(gè) 區(qū)域，由圖5-2易見(jiàn)a1=2,a2=4。圖圖5 52 2見(jiàn)書(shū)見(jiàn)書(shū)8484頁(yè)頁(yè) 現(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)把第n個(gè)圓分成2(n-1)條弧,而每條弧正好將前面的n-1個(gè)圓分成的區(qū)域中的每個(gè)區(qū)域分成兩個(gè)區(qū)域， 故新加入的第n個(gè)圓使所成的區(qū)域數(shù)增加了2(n-1)。因此可以建立如下的遞歸關(guān)系： 2)2(),1(211annaann求解這個(gè)遞歸關(guān)系即可得到問(wèn)題的答

9、案。求解這個(gè)遞歸關(guān)系即可得到問(wèn)題的答案。 設(shè)有設(shè)有n n個(gè)數(shù)個(gè)數(shù)b b1 1,b,b2 2, ,b,bn n的連乘積為的連乘積為b b1 1b b2 2b bn n。試求不同的結(jié)合方式數(shù)。試求不同的結(jié)合方式數(shù)( (加加括號(hào)的方式括號(hào)的方式) )。例例5 5解解：設(shè)不同的結(jié)合方式數(shù)為an。定義a1=1。顯然有a2=1。由于對(duì)乘積b1b2bn的任一結(jié)合方式，必有某一個(gè)k k(1kn-1)使得最后的運(yùn)算為積b1b2bk與積bk+1bk+2bn相乘。當(dāng)k k固定時(shí)，對(duì)乘積b1b2bk有ak種不同的結(jié) 合方式，而對(duì)乘積bk+1bk+2bn有an-k種不同的結(jié)合方式。由乘法規(guī)則乘法規(guī)則知，對(duì)某一個(gè)k k共有akan-k種不同的結(jié)合方式。再由加法規(guī)則加法規(guī)則即得如下的遞歸關(guān)系： 1, 1)2(2111aanaaankknkn 求解這個(gè)遞歸關(guān)系即得到問(wèn)題的答案。求解這個(gè)遞歸關(guān)系即得到問(wèn)題的答案。 在上面的幾