組合數(shù)學(xué)第六章

1、2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,1,第六章 遞推關(guān)系,§6.1 遞推關(guān)系的建立§6.2 常系數(shù)線性齊次遞推關(guān)系的求解§6.3 常系數(shù)線性非齊次遞推關(guān)系的求解§6.4* 用生成函數(shù)求解遞推關(guān)系§6.5* 用其他方法求解遞推關(guān)系,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,2,遞推關(guān)系的建立,構(gòu)建求解遞推關(guān)系是組合計數(shù)的重要方法； 在第三章 Stirli

2、ng數(shù)的性質(zhì)3.5.1中給出了遞推關(guān)系。 S2（n+1,k)=S2(n,k-1)+k*S2(n,k) 在第四章討論錯位排列數(shù)Dn時，也可以建立關(guān)于Dn的遞推關(guān)系： Dn=(n-1)(Dn-1 + Dn-2) n≥3 D1=0，D2=1,,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,3,遞推關(guān)系的建立,定義6.1.1 給定一個數(shù)的序列H(0),H(1),…, H(n),…若存在正整

3、數(shù)n0，使得當(dāng)n≥n0時，可以用等號(或小于，大于號)把H(n)和前面某些項H(i)，0≤ i <n，聯(lián)系起來，這樣的式子叫做遞推關(guān)系。 遞推關(guān)系也稱遞歸關(guān)系，遞歸方程。從本質(zhì)上講，遞推關(guān)系是研究整變量函數(shù)的或者說是研究數(shù)列的，與此對應(yīng)的是連續(xù)論域中的微分方程。因此，我們可以類似的方法對它們進行研究。,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,4,遞推關(guān)系的建立,利用遞推關(guān)系和初值在某些情況下可以求出序列的

4、通項表示式H(n) 。 但是對于大多數(shù)遞推關(guān)系，目前還解不出H(n)的顯式來， 即使這樣，對于給定的n也可以從初值開始，一步一步地計算出H(n)的值或者范圍，而H(n)一般代表了某個組合計數(shù)問題的解，因此遞推關(guān)系是組合計數(shù)的重要工具。,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,5,遞推關(guān)系的建立,求解遞推關(guān)系的常用方法（1）特征根法；（2）迭代歸納法；（3）生成函數(shù)法；,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,6,遞

5、推關(guān)系的建立,例6.1.1（爬樓梯問題）一個小孩要爬上n階樓梯，每次可上一階或兩階，問上n階有多少種上法？解：,顯然登上1階臺階有1種方法，登上2臺階有2種方法，f(1）=1，f(2)=2 ,稱為遞推關(guān)系的初始條件。設(shè)有f(n) 種方法，要登上這n階臺階，最后邁上一個臺階或兩個臺階完成.（1）若最后是邁上一個臺階完成的，則前面登上了n-1階臺階，有f(n-1) 種方法；（2）若最后是邁上兩個臺階完成的，則前面登上了n-2階臺階，

6、有f(n-2) 種方法，根據(jù)加法原理有遞推關(guān)系：f(n)=f(n-1)+f(n-2) .,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,7,遞推關(guān)系的建立,例6.1.2 Fibonacci數(shù)列問題是一個古老的數(shù)學(xué)問題，是于1202年提出的，問題表述如下: 把一對兔子（雌、雄各一只）在某年的開始放到圍欄中，每個月這對兔子都生出一對新兔，其中雌、雄各一只。由第二個月開始，每對新兔每個月也生出一對新兔，也是雌、雄各一只。問一年后圍欄中有多

7、少對兔子？這是一個數(shù)學(xué)模型的形象表示，不能真正用來表示兔子的繁殖規(guī)律。,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,8,遞推關(guān)系的建立,對于n=1,2,…,令f(n)表示第n個月開始時圍欄中的兔子對數(shù)，顯然有f(1)=1,f(2)=2。 在第n個月的開始，那些第n-1個月初已經(jīng)在 圍欄中的兔子仍然存在，而且每對在第n-2個月初就存在的兔子將在第n-1個月開始將要生出一對新兔來，所以有： f(n

8、)=f(n-1)+f(n-2) (n≥3, n為整數(shù)) f(1)=1,f(2)=2 這是一個帶有初值的遞推關(guān)系。,,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,9,遞推關(guān)系的建立,如果規(guī)定f(0)=1,則上式變成： f(n)=f(n-1)+f(n-2) (n≥2, n為整數(shù)) f(0)=1,f(1)=1稱滿足這個式子的數(shù)列就成為Fibonacci數(shù)列，

9、數(shù)列中的項叫做Fibonacci數(shù).,,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,10,遞推關(guān)系的建立,多米諾牌（可以看作是2*1大小的方格)完全覆蓋一個n*2的棋盤。覆蓋的方案數(shù)？f(n)=f(n-1)+f(n-2) (n≥2, n為整數(shù))f(1)=1,f(2)=2稱滿足這個式子的數(shù)列就成為Fibonacci數(shù)列，數(shù)列中的項叫做Fibonacci數(shù).,,,,,,,,,,,,,,,,,,,,1 2

10、 n-1 n,1 2 n-1 n,,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,11,遞推關(guān)系的建立,例6.1.3 （Hanoi塔問題）現(xiàn)有A，B，C三根立柱以及n個大小不等的中空圓盤，這些圓盤自小到大套在A柱上形成塔形，如圖6.1.1所示，要把n個圓盤從A柱上搬到C柱上，并保持原來的順序不變，要求每次只能從一根立

11、柱上拿下一個圓盤放在另一根立柱上，且不允許大盤壓在小盤上，問至少要搬多少次 ？,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,12,解：記f(n)為n個圓盤從A柱搬到C柱所需的最小次數(shù).整個搬運過程可分成三個階段；（1）將套在A柱上面的n-1個圓盤從A柱按要求搬到B柱，搬動 次數(shù)為f(n-1);（2）把A柱上最下面的那個圓盤搬到C柱上，搬動次數(shù)為1;（3）把B柱上的n-1個圓盤按要求搬到C柱上，搬動次數(shù)為f(n-1);由加法原則知

12、， f(n)=2f(n-1)+1又顯然f(1)=1，所以有如下帶有初值的遞推關(guān)系: f(n)=2f(n-1)+1 f(1)=1,,遞推關(guān)系的建立,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,13,遞推關(guān)系的建立,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,14,常系數(shù)線性齊次遞推關(guān)系的求解,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,15,常系數(shù)線性齊次遞推關(guān)系的求解,,,f替換為x

13、，n替換為k，并變?yōu)橹笖?shù),2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,16,常系數(shù)線性齊次遞推關(guān)系的求解,(6.2.2),(6.2.3),qn是(6.2.2)的解,兩邊除以qn-kq是(6.2.3)的解,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,17,常系數(shù)線性齊次遞推關(guān)系的求解,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,18,常系數(shù)線性齊次遞推關(guān)系的求解,(6.2.2),(6.2.3),2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,19,

14、常系數(shù)線性齊次遞推關(guān)系的求解,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,20,常系數(shù)線性齊次遞推關(guān)系的求解,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,21,常系數(shù)線性齊次遞推關(guān)系的求解,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,22,齊次遞推關(guān)系使用特征方程的求解步驟（1）,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,23,常系數(shù)線性齊次遞推關(guān)系的求解,例6.2.1 解關(guān)于Fibonacci數(shù)的遞推關(guān)系,2024/3/19,計算機科學(xué)與

15、技術(shù)學(xué)院,24,常系數(shù)線性齊次遞推關(guān)系的求解,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,25,常系數(shù)線性齊次遞推關(guān)系的求解,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,26,常系數(shù)線性齊次遞推關(guān)系的求解,例6.2.2,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,27,常系數(shù)線性齊次遞推關(guān)系的求解,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,28,常系數(shù)線性齊次遞推關(guān)系的求解,例 6.2.3,由定理6.2.1，可知3n是此遞推關(guān)系的解（不考慮初

16、值），我們不妨試一試n3n ，將其帶入此遞推關(guān)系。,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,29,常系數(shù)線性齊次遞推關(guān)系的求解,這說明n3n也是遞推關(guān)系的解，而且與線性3n無關(guān)，所以原遞推關(guān)系的通解為,,代入初值，得：,,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,30,常系數(shù)線性齊次遞推關(guān)系的求解,設(shè)遞推關(guān)系 的特征方程為 令,如果q是P(x)=0的二重根，這q也是Pn(x)=0的二重根，也是P’n(x)=0的根

17、， P’n(x)是Pn(x)的微商，即,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,31,常系數(shù)線性齊次遞推關(guān)系的求解,因此，q也是xP’n（x）=0的根，而,代入x=q ，得,這說明nqn是原遞推關(guān)系的解。 可以證明以下的結(jié)論：如果q是P(x)=0的e重根,則qn,nqn,n2qn,…,ne-1qn都是原遞推關(guān)系的解.,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,32,常系數(shù)線性齊次遞推關(guān)系的求解,可以證明以下的結(jié)論：如果q是P(x)=

18、0的e重根,則qn,nqn,n2qn,…,ne-1qn都是原遞推關(guān)系的解.,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,33,常系數(shù)線性齊次遞推關(guān)系的求解,定理6.2.2設(shè)q1，q2，……qt是遞推關(guān)系f(n)=a1f(n-1)+a2f(n-2)+……+akf(n-k) (n≥k，ak≠0),的不相等的特征根，其重數(shù)分別為e1，e2，…

19、…et( e1+e2+……+et=k),則這個遞推關(guān)系的通解是：f(n)= f1(n)+ f2(n)+ …… + ft(n)其中： fi(n)＝c1qi n＋c2nqi n＋……＋,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,34,齊次遞推關(guān)系使用特征方程的求解步驟（2）,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,35,例6.2.5. 求解遞推關(guān)系,對,常系數(shù)線性齊次遞推關(guān)系的求解,2024/3/19,計

20、算機科學(xué)與技術(shù)學(xué)院,36,對,通解為,解方程組，得c1=5,c2=2,c3=-4所以原遞推關(guān)系的解為,常系數(shù)線性齊次遞推關(guān)系的求解,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,37,常系數(shù)線性非齊次遞推關(guān)系的求解,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,38,常系數(shù)線性非齊次遞推關(guān)系的求解,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,39,常系數(shù)線性非齊次遞推關(guān)系的求解,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,40,常系數(shù)線性非齊次遞

21、推關(guān)系的求解,對于一般g(n)沒有普遍的解法，只對一些簡單的情況可以用待定系數(shù)法求f´(n) 。,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,41,非齊次遞推關(guān)系使用特征方程的求解步驟,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,42,比較等式兩邊,常系數(shù)線性非齊次遞推關(guān)系的求解,解： 因為4不是特征方程的根，所以該遞推關(guān)系的非齊次特解為,，將其代入遞推關(guān)系，得,的系數(shù)，得,從而 a=2.,例6.3.1 求解遞

22、推關(guān)系,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,43,而相應(yīng)齊次遞推關(guān)系的通解為,，由定理6.3.1知，非齊次遞推關(guān)系的通解為,由初值,得,從而,故,常系數(shù)線性非齊次遞推關(guān)系的求解,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,44,例6.3.2 求解遞推關(guān)系,解 由于3是特征方程的根，所以該遞推關(guān)系的特解為,將它代入遞推關(guān)系，得到 a=6,常系數(shù)線性非齊次遞推關(guān)系的求解,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,45,從而非齊次遞推

23、關(guān)系的通解為,再由初值,求得,于是,常系數(shù)線性非齊次遞推關(guān)系的求解,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,46,根據(jù)前面的分析，可知該遞推關(guān)系的通解為,解 相應(yīng)的特征方程為x=2，故齊次解為2n。設(shè)非齊次特解為b，代入原遞推關(guān)系，得,例6.3.3 求Hanoi塔問題滿足的遞推關(guān)系,所以特解為,代入初值,得,所以,常系數(shù)線性非齊次遞推關(guān)系的求解,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,47,常系數(shù)線性非齊次遞推關(guān)系的求解,20

24、24/3/19,計算機科學(xué)與技術(shù)學(xué)院,48,常系數(shù)線性非齊次遞推關(guān)系的求解,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,49,常系數(shù)線性非齊次遞推關(guān)系的求解,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,50,常系數(shù)線性非齊次遞推關(guān)系的求解,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,51,利用生成函數(shù)求解各類遞推關(guān)系有廣泛的適用性，其基本步驟是： （1）令,（2）將關(guān)于,的遞推關(guān)系式轉(zhuǎn)化成關(guān)于,的方程式；,，將,展開成x的冪級數(shù)，,的

25、系數(shù)即是,。,（3）解出,用生成函數(shù)求解遞推關(guān)系,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,52,例6.4.1 求解遞推關(guān)系,解： 令,則有,用生成函數(shù)求解遞推關(guān)系,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,53,將,代入上式并整理，得,所以,用生成函數(shù)求解遞推關(guān)系,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,54,用生成函數(shù)求解遞推關(guān)系,求解h(n)=5h(n-1)-6h(n-2),h0=1,h1=-2 令g(x)=h0+h1

26、x+ h2x2 …+hnxn+… -5xg(x)= -5h0x-5h1x2-…-5hn-1xn+… 6x2g(x)= 6h0x2+…+6hn-2xn+… (1-5x+6x2)g(x)=h0+(h1-5h0)x+(h2-5h1+6h0)x2+ g(x)=(1-7x)/ (1-5x+6x2) h(n)=5*2n-4*3n,另一種：,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,55,其中,是給

27、定常系數(shù),那么，,定理6.4.1 具有初值條件的的k階常系數(shù)線性遞歸關(guān)系為：,有生成函數(shù),,其中，,是不大于k-1次的多項式。當(dāng)且僅當(dāng),關(guān)于遞歸關(guān)系的特征方程為,用生成函數(shù)求解遞推關(guān)系,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,56,用生成函數(shù)求解遞推關(guān)系,證明 設(shè) 序列的特征多項式和生成函數(shù)分別為其中 由遞歸關(guān)系，有將以上等式組兩邊相加，并注意，C0=1,有即,2024/3

28、/19,計算機科學(xué)與技術(shù)學(xué)院,57,用生成函數(shù)求解遞推關(guān)系,亦即其中，P(x)多項式的次數(shù)不大于k-1， C0=1 。易知注意到k次特征多項式在復(fù)數(shù)域上有k個零點。,,,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,58,用生成函數(shù)求解遞推關(guān)系,設(shè),所以,其中,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,59,例6.4.2 已知序列,。,求,解法1 由定理6.4.1,的生成函數(shù)為,用,替代,，知特征方程為,特征根為,故,用生成函數(shù)求

29、解遞推關(guān)系,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,60,利用整式除法,,,知,,解得,,從而,用生成函數(shù)求解遞推關(guān)系,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,61,例6.4.3 求如下遞歸關(guān)系的生成函數(shù)：,解： 特征方程為,對,，,，,，求得,用生成函數(shù)求解遞推關(guān)系,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,62,例6.4.5 求解Hanoi塔問題,解 設(shè),，,對等式兩邊對應(yīng)乘以 xn ，n≥2,并將等式組成左右兩邊相加。,左端

30、為：,右端為：,用生成函數(shù)求解遞推關(guān)系,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,63,從而,用生成函數(shù)求解遞推關(guān)系,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,64,例6.4.6 求解遞推關(guān)系：,解：先求它的生成函數(shù)：,用生成函數(shù)求解遞推關(guān)系,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,65,所以,用生成函數(shù)求解遞推關(guān)系,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,66,例6.4.6 求解遞推關(guān)系：,解：先求它的生成函數(shù)：,用生成函數(shù)求解遞

31、推關(guān)系,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,67,所以,用生成函數(shù)求解遞推關(guān)系,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,68,用迭代歸納法求解遞推關(guān)系及其應(yīng)用,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,69,用迭代歸納法求解遞推關(guān)系及其應(yīng)用,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,70,用迭代歸納法求解遞推關(guān)系及其應(yīng)用,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,71,用迭代歸納法求解遞推關(guān)系及其應(yīng)用,2024/3/19,計算機

32、科學(xué)與技術(shù)學(xué)院,72,用迭代歸納法求解遞推關(guān)系及其應(yīng)用,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,73,用迭代歸納法求解遞推關(guān)系及其應(yīng)用,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,74,用迭代歸納法求解遞推關(guān)系及其應(yīng)用,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,75,用迭代與歸納法求解遞推關(guān)系,在第四章討論錯位排列數(shù)Dn時，也可以建立關(guān)于Dn的遞推關(guān)系： Dn=(n-1)(Dn-1 + Dn-2) n≥3

33、 D1=0，D2=1并由迭代法推出以下的遞推關(guān)系： Dn=nDn-1 + (-1)n n≥2 D1=0,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,76,錯位排列,,,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,77,錯位排列,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,78,用迭代與歸納法求解遞推關(guān)系,例6.5.3 估計快速排序算法的平均復(fù)雜度。 解 設(shè)要排序的

34、數(shù)為 將快速排序算法記作Quicksort(f, l)，該算法的描述如下：（1）若f >=l則算法結(jié)束。（2）i?f+1。 當(dāng)xi xf時，做j?j-1（從右到左找到小于xf的第一個數(shù)xj） 。,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,79,用迭代與歸納法求解遞推關(guān)系,（3）當(dāng)i xf時，做j?j-1 （把放好，將原來的序列劃分成兩個序列）。（4）Quicksort(

35、 f, j-1)（對子序列遞歸地排序）。（5）Quicksort( j+1, l )（對子序列遞歸地排序）。,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,80,用迭代與歸納法求解遞推關(guān)系,例如，下面給出了排序13個數(shù)的一個實例，按照算法執(zhí)行步驟（1），（2）和（3），各步交換的結(jié)果如圖6.5.1所示。,不難看到，到第（3）步結(jié)束時，分別與xf比較了一次， 也分別與xf比較了一次，而xs,xs+1各與xf比較了兩次

36、，這n個數(shù)共比較了n+1次，令Cn表示對n個數(shù)進行快速排序所需的平均比較次數(shù)， Ps表示xf為第s個最小數(shù)的概率，如果假設(shè)對任意s，這個概率都相等，即，Ps=1/n,那么有,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,81,用迭代與歸納法求解遞推關(guān)系,圖 6.5.1,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,82,用迭代與歸納法求解遞推關(guān)系,用n-1代替n，得,2024/3/19,計算機科學(xué)與技術(shù)學(xué)院,83,用迭代與歸納法求解遞推關(guān)系,把