1、第五章 遞推關系及其解法,5.1 遞歸關系的建立 -在計算機科學特別是算法分析中有廣泛的應用 定義5.1.1 設a0,a1,a2,an,為一序列,把該序列中an與它前面的幾個ai關(0in-1)聯(lián)起來的方程稱為一個遞歸關系.,例1(“Hanoi塔”問題)：這是一個組合數學中的著名問題。n個大小不一的圓盤依其半徑大小，從下而上套在A柱上，如下圖示?，F(xiàn)要求將所有的圓盤從A柱上全部轉移到C柱上,每次只允許從一個柱子上轉移一個盤子到另一柱子上，且在轉移過程中不允許出現(xiàn)大盤放在小盤上方。試問要轉移多少次才能將柱A上的n個盤移到C柱上。,例2 “Fibonacci兔子問題”：從某年某月(設為第0月)開始,

2、把雌雄各一的一對小兔放入養(yǎng)殖場,假定兩個月后長成成年兔,并同時(即第二個月)開始每月產雌雄各一的一對小兔,新增的小兔也按此規(guī)律繁殖,問第n個月末養(yǎng)殖場共有多少對兔子? 第n月的兔子包括兩部分:上月留下的和當月新生的,而新生的小兔數即為前月末的兔子數,所以 Fn=Fn-1+Fn-2 Fibonacci序列的性質:,5.2 常系數線性齊次遞歸關系的解法,定義5.2.1 序列a0,a1,a2,an,中相鄰的k+1項之間的關系為 則稱之為序列的k階常系數線性齊次遞歸關系,其中系數bi為常數,i=1,2,k,且bk0。 定義5.2.2 與(5.2.1)相聯(lián)系的方程 稱之為遞歸關系(5.2.1)的特征方程

3、，其根稱為遞歸關系式的特征根。,特征方程的根與遞歸關系的解之間的關系：,1.特征根無重根 定理5.2.1 若q 0, an=qn為遞歸關系(5.2.1)的解當且僅當q為特征方程(5.2.2)的根。 定義5.2.3 稱式 為遞歸關系(5.2.1)的初值條件。,定理5.2.2 若q1,q2,qk為遞歸關系式(5.2.1)的特征根，c1,c2,ck為任意常數，則 為遞歸關系(5.2.1)的解。 定義5.2.4 若對遞歸關系(5.2.1)的任意一個解an，都存在一組常數c1,c2,ck使得 則稱該式為遞歸關系式(5.2.1)的通解。 定理5.2.3 若q1,q2,qk為遞歸關系式(5.2.1)的k個互

4、不相同的特征根，則式(5.2.4)為(5.2.1)的通解。,例1 求Fibonacci序列的通項。 例2 求解遞歸關系,注：若特征根有復根，復根成對出現(xiàn)，故設 則通解可表示為 其中,例3 求解遞歸關系,2.特征根有重根,定理5.2.4 若遞歸關系(5.2.1)的特征方程(5.2.2)有一個m重根q，則qn,nqn,nm-1qn均為(5.2.1)的解。 定理5.2.5 設q1,q2,qt分別為特征方程(5.2.2)的相異的m1,m2,mt重根,且 則遞歸關系(5.2.1)的通解為,例4 求解遞歸關系 例5 求解遞歸關系,5.3 常系數線性非齊次遞歸關系的解法,定義5.3.1 序列a0,a1,a2

5、,an,中相鄰的k+1項之間的關系為 則稱之為序列的k階常系數線性非齊次遞歸關系,其中系數bi為常數,i=1,2,k,bk0,f(n) 0,nk 。 定義5.3.2 在式(5.3.1)中,若f(n)=0, 則稱 為由式(5.3.1)導出的常系數線性齊次遞歸關系。,定理5.3.1 若 為(5.3.1)的一個特解,而 ( )是由(5.3.1)導出的線性齊次遞歸關系(5.3.2)的通解,則 為(5.3.1)的通解。 注：由定理5.3.1知, 要求(5.3.1)的通解,只要求它的一個特解及導出的齊次遞歸關系的通解即可。對非齊線性遞歸關系的特解, 針對f(n)的特殊形式有以下情形:,1.f(n)是n的t

6、次多項式 1不是齊次遞歸關系(5.3.2)的特征根 這時,(5.3.1)的特解形式為 其中 為待定常數。 例1 求解“Hanoi塔”問題的遞歸關系 例2 求解遞歸關系,1是齊次遞歸關系(5.3.2)的m重特征根(m1) 這時,(5.3.1)的特解形式為 其中 為待定常數。 例3 求解遞歸關系,2 f(n)是n的形式 不是導出的齊次線性遞歸關系的特征根 這時,(5.3.1)的特解形式為 其中 A為待定常數。 例4 求解遞歸關系,是導出的齊次線性遞歸關系的m重特征根(m1) 這時,(5.3.1)的特解形式為 其中 A為待定常數。 例5 求解遞歸關系,f(n)= n g(n),其中g(n)為n的t次

7、多項式, 是導 出的齊次線性遞歸關系的m重特征根(m0) 這時,(5.3.1)的特解形式為 其中 為待定常數。 例6 求解遞歸關系,5.4 遞歸關系的其他解法,前面方法當k較大時，面臨求解高階方程及k個未知數k個方程的方程組, 求解困難問題。本節(jié)再介紹一些方法。 一、迭代法 例1 求解遞歸關系 二、歸納法 例2 求解遞歸關系,三、母函數法 主要思想: 用f(x)表示序列a0,a1,a2,an,的普通母函數,即 利用遞歸關系an的表達式與(5.4.1)間的關系將(5.4.1)化為關于f(x)的方程，即有 g(f(x)=0; 解出f(x)； 將f(x)的表達式展開成冪級數的形式，即得an的初等表達

8、式.,例3 求解遞歸關系 例4 求解遞歸關系,四、代換法 將序列a0,a1,a2,an,的遞歸關系轉換為關于新序列b0,b1,b2,bn,的遞歸序列。 例5 求解遞歸關系 五、將常系數線性非齊次遞歸關系轉化為常系數齊次遞歸關系 例6 求an-2an-1=3的通解。 例7 求,5.5 Stirling數,一、第1類Stirling數 令 ，若 則稱S1(n,k)為第1類Stirling數，即為多項式xn中xk的系數。 約定：當nk時， S1(n,k)=0。 定理5.5.1 第1類Stirling數S1(n,k)滿足,由定理5.4.1得第1類Stirling數S1(n,k)的數值：,二、第2類St

9、irling數 若 則稱S2(n,k)為第二類Stirling數。顯然，當nk時， S2(n,k)=0。 定理5.5.2 第2類Stirling數S2(n,k)滿足,S2(n,k)的組合意義涉及集合的劃分。,定理5.5.3 S2(n,k)為n個元素的集合劃分成k個不相交的非空子集的方式數。 證明 設A(n,k)為n個元素的集合劃分成k個不相交的非空子集的方式數，只要證明A(n,k)滿足定理5.5.2即可。 給定一個n+1個元素的集合a1,a2,an+1,將它劃分為k個不相交的非空子集,分以下兩種情況: (1) an+1為k個子集中的一個子集，則將a1,a2,an劃分為k-1個子集的方式數為A(

10、n,k-1)。 (2) an+1不為k個子集中的一個子集，則an+1必為某個子集中的元素。這時，先將a1,a2,an劃分為k個子集共有A(n,k)種方式，然后將an+1加到k個子集中的某一個，共有k種方式，從而得總的劃分數為kA(n,k)。 由加法原理， a1,a2,an+1劃分為k個子集的方式數為 A(n,k-1)+ kA(n,k)。 所以有 A(n+1,k)=A(n,k-1)+ kA(n,k)。 又將0 個元素的集合劃分為0個不相交子集的方式數為1，所以A(0,0)=1。 另一方面，不可能將n個元素的集合中的元素不放進任何一個集合中去，所以A(n,0)=0。 這樣， A(n,k)滿足定理5

11、.5.3，所以 A(n,k) =S2(n,k)。,說明： (1)把n個不同的球放入k 個相同的盒子而無一空盒，等價于將n個元素的集合劃分為k個不相交的非空子集，所以把n個不同的球放入k個相同盒子而無一空盒的放法共有S2(n,k)種。 (2) S2(n,k)具有以下性質： S2(n,n)=1, S2(n,k)=0 (nk, 或 k=0n)； S2(n,2)=2n-1-1; S2(n,n-1)=C(n,2)。,例2 設m,n均為正整數，mn。用組合分析的方法證明 證明 設有n只不同的球，m個盒子，它們的編號依次為1,2,m。把這n個球放入盒子中，允許有空盒且不限制放入盒子內的球的個數，共有mn種方法。 另