组合数学课件：递归关系

递归关系

5.1几个典型的递归关系实例

5.2常系数线性齐次递归关系的基本解法

5.3常系数线性非齐次递归关系的解法

5.4迭代法求解递归关系

5.5生成函数方法求解递归关系5.1几个典型的递归关系实例

例1(错排问题设S={1,2,…,n}，令D(n)为S上元素的错排数，即n个元素都不在其自然位置上的排列数），则D(n)=(n-1)(D(n-2)+D(n-1)),n≥3,D(1)=0,D(2)=1

证明对于每个错排，第一位上的数字只能取2,3,…,n中之一。以第一位数字的取法可将全部错排分为n-1类:P2,P2,…,Pn

，即P2={(2,i2,i3,…,in)|it≠t,t=2,3,…,n}

P3={(3,j2,j3,…,jn)|jt≠t,t=2,3,…,n}

…

Pn={(n,k2,k3,…,kn)|kt≠t,t=2,3,…,n}易知|P2|=|P3|=…=|Pn|都是相同的，令其为dn，于是Dn=(n-1)·dn考察P2={(2,i2,i3,…,in)|it≠t,t=2,3,…,n}

将P2中的错排按第二位上的数字取1或不取1分为两类，分别记为P21,P2x：P21={(2,1,i3,…,in)|it≠t,t=3,4,…,n}

P2x={(2,i2,i3,…,in)|i2≠1,it≠t,t=3,4,…,n}显见|P21|=D(n-2)

|P2x|=|{(i2,i3,…,in)|it+1≠t,t=1,2,…,n-1}|=D(n-1)从而dn=D(n-2)+D(n-1)，故知D(n)=(n-1)(D(n-2)+D(n-1)),n≥3,D(0)=0,D(2)=1

例2（Hanoi塔问题）n个圆盘，从A柱经B柱移到C柱(参见图5.1.1)。要求每次只移一个圆盘；移动过程始终保持大盘在下，小盘在上；中途A、B、C柱均可作临时柱，最终移至C柱，则A到C的最少移动次数为h(n)=2h(n-1)+1

图5.1.1Hano塔示意图

解设h(n)为问题的解，则h(1)=1,h(2)=3=2h(1)+1,h(3)=5=2h(2)+1,…,h(n)=2h(n-1)+1。又若设利用C柱把A柱上n-1个圆盘移到B柱，移动次数为h(n-1)，则将A柱所剩最大圆盘移到C柱只需移动一次，再将B上的n-1个圆盘利用A柱移到C柱（已有一个最大圆盘在下面）共需移动h(n-1)次。故总的移动次数为h(n)=2h(n-1)+1。

例3(Fibonacci问题)

(1)兔子问题:Fn+1=Fn+Fn-1,F0=F1=1,F2=2。

(2)棋盘用骨牌覆盖问题(如图5.1.2所示)。

(3)S={0,1}的n位符号串中不出现“11”的方案数。

(4)无相邻整数的子集数。图5.1.22×n棋盘用n枚1×2骨牌覆盖示意图

解

(1)兔子问题的递归关系在前面章节已得到。

(2)参见图5.1.2（a）、(b)，求2×n棋盘用n枚1×2骨牌完全覆盖的方案数。设Fn为问题的解，图5.1.2（a）中竖着覆盖1枚骨牌，剩余的为2×(n-1)格棋盘，有Fn-1种方案；图5.1.2（b）中横着覆盖2枚骨牌，剩余2×(n-2)格棋盘，有Fn-2种方案。故Fn=Fn-1+Fn-2,n≥2

Fn+1=Fn+Fn-1,n≥1,F0=F1=1,F2=2图5.1.3n×n方格不穿越对角线走法(3)S={0,1}，重复度为∞，求Ｓ的n位符号串中不出现“11”的串的数目。设Fn为问题的解，末位为0，满足题设的n-1位串有Fn-1个；末位为1，最后两位必为01，满足题设的n-2位串有Fn-2个，故Fn=Fn-1+Fn-2,F1=1,F2=2

F0=1

(4)令S={1,2,…,n}，对T∈2S，构造函数f:2S→{0,1}n，f(T)=b1b2…bn，i=1,2,…,n，bi=1,i∈Tbi=

0,iT，从而，求无相邻整数的子集问题转化为求无“11”字样的n位01串问题。

例4(Catalan问题)设Cn为问题的解，并设第一次碰到对角线的点为(k,k)，参见图5.1.3，则从(0,0)到(k,k)的走法为Ck-1，又(k,k)点以后满足题意的走法为Cn-k。由乘法原理得5.2常系数线性齐次递归关系的基本解法

定义若对n≥2，序列{an}满足

an+c1an-1+c2an-2=0 (5.2.1)

a0=d0,a1=d1 (5.2.2)其中，c1,c2为常数，n≥2，c2≠0，d0，d1为实常数，则称（5.2.1）式为关于序列{an}的二阶常系数线性齐次递归关系，（5.2.2）式称为初值条件。之所以称为二阶是因c2≠0，否则可考虑更低的阶；称为常系数是因an-2,an-1,an之前的c2,c1及c0=1都是常数；称为线性是因an-2,an-1,an都是一次的；称为齐次是因常数项为0。例如：an+2an-1=0 一阶递归关系an+(n-2)an-1+an-2=0变系数递归关系an+3a2n-1+an-2=0非线性递归关系an-2an-1=1非齐次递归关系对x≠0，称x2+c1x+c2=0 (5.2.3)为{an}的特征方程，（5.2.3）式的解称为{an}的特征根。

（1）设（5.2.3）式有二不等实根：r1≠r2，则（5.2.1）式的通解为an=K1rn1+K2rn2其中K1,K2为可由初值确定的待定常数。（2）设（5.2.3）式的解为二相等实数：r1=r2=r，则（5.2.1）式的通解为an=(K1+nK2)rn

其中，K1,K2为待定常数。

（3）设（5.2.3）式的解为一对共轭复根：r1=α+βi=ρeiθ=ρ(cosθ+isinθ)

r2=α-βi=ρe-iθ=ρ(cosθ-isinθ)则（5.2.1）式的通解为an=K1rn1+K2rn2或 an=Aρncosnθ+Bρnsinnθ其中，A=K1+K2，B=(K1-K2)i为待定常数。α,β,ρ=(α2+β2)1/2

为实数，θ=arctan为辐角。

定理1（递归关系的解与特征方程的解之间的关系）对n≥2,r≠0,an=rn是递归关系an+c1an-1+c2an-2=0的解iffr是方程x2+c1x+c2=0的解。

证明对n≥2，r≠0，an=rn为an+c1an-1+c2an-2=0的解。

iff

rn

+c1rn-1+c2an-2=0

iff

r2+c1r+c2=0

iff

r是方程x2+c1x+c2=0的解。

定理2（解的迭加性）设an=rn1，an=rn2都是递归关系an+c1an-1+c2an-2=0的解，则K1rn1+K2rn2也是该递归关系的解。其中，K1,K2为任意常数。

证明

定理3设r1=r2=r≠0是方程x2+c1x+c2=0的重根，则an=rn和an=nrn都是递归关系an+c1an-1+c2an-2=0的解。

证明由定理1知，rn一定是递归关系an+c1an-1+c2an-2的解。现只需证an=nrn也是该递归关系的解即可。事实上，设r≠0是方程x2+c1x+c2=0的非零二重根，则r也一定是方程xn+c1xn-1+c2xn-2=0的非零二重根。从而r一定是方程

的解。这就证明了an=nrn是递归关系an+c1an-1+c2an-2=0的解。

定理4只要r1≠r2是方程x2+c1x+c2=0的二不同特征根，那么an=K1rn1+K2rn2一定是递归关系an+c1an-1+c2an-2=0的通解。其中K1,K2为任意实数。

证明假定an是具有初值的递归关系-的任一解。将初值条件代入由r1≠r2知，即两方程线性无关,解得于是，由上式确定的K1,K2，可求得递归关系的一个特解：

例1

求解具有初值条件F0=1,F1=1的递归关系Fn=Fn-1+Fn-2。

解特征方程x2-x-1=0的根为：构造通解由初值条件确定K1,K2:从而

例2

求解递归关系an-2an-1-2an-2=0，a1=3，a2=8

a0=1。

解特征方程为x2-2x-2=0，特征根为根据初值条件求解K1,K2:故

求a,b,c3个字母组成的n位字符串中，不出现子串“aa”的字符串的个数问题,反映了例2所给递归关系的组合学意义。

例3求解n阶行列式Dn，其中，主对角元全为2，次对角元全为1，其余都是0。Dn-2Dn-1+Dn-2=0,n≥3

D1=2,D2=3

解相应的特征方程为x2-2x+1=0，二重根为r1=r2=1。通解形式为Dn=K1×1n+nK2×1n=K1+nK2

由初值条件有K1+K2=2

K1+2K2=3解得K1=K2=1。故Dn=1+n

例4求解n阶行列式Dn,Dn的主对角元、次对角元均为1，其余都是0。Dn-Dn-1+Dn-2=0

D1=1,D2=0,n≥3解相应的特征方程为x2-x+1=0，一对共轭复根为通解为由初值条件有D1=K1r1+K2r2=1

D2=K1r21+K2r22=0解得最后有例5an-2an-1-2an-2=0(n≥2)

a0=0,a1=1

解特征方程为x2-2x+2=0;一对共轭复根为r1=α+βi，r2=α-βi，α=β=1。解得，θ=π/4，通解为

由初值条件得A=0，求解，得B=1。最后所求特解为an对应的序列为0,1,2,2,0,-4,-8,-8,0,16,32,32,0,…,0。例6求解递归关系：an-4an-2=0

a0=0,a1=1解特征方程为x2=4;特征根为r1=2,r2=-2通解形式为故

an=2n-2+(-1)n-12n-2

常系数二阶线性齐次递归关系的解法，可推广到高阶上去，对此，仅将结果介绍如下。具有初值条件的k阶常系数线性齐次递归关系：的特征方程为an+c1an-1+c2an-2+…+ckan-k=0

ai=di,i=0,1,2,…,k-1其中，

c0=1，ck≠0。表5.2.1高阶线性齐次递归关系特征根与通解an中各项的对应关系例7求解递归关系an-an-1-9an-2+9an-3=0

a0=0,a1=1,a2=2

解特征方程为x3-x2-9x+9=0;特征根为r1=1,r2=3,r3=-3;通解为an=K11n+K23n+K3(-3)n=K1+K23n+K3(-3)n。故例8求解递归关系an-an-2-2an-3-an-4=0

a0=1,a1=1,a2=1,a3=1

解特征方程为x4-x2-2x-1=0,特征根为其中通解为故序列的前几项是：0,1,1,1,3,4,6,11,17,27,45,72,116,…

n根火柴，甲、乙二人轮流取，每次仅能取1根或2根。若甲先取，求最后由甲取完的方案数有多少种。组合学意义正如本例。5.3常系数线性非齐次递归关系的解法

仍以二阶递归关系为主，考虑递归关系an+c1an-1+c2an-2=f(n)其中，关于n的函数f(n)≠0。对初值条件下上述方程的解有如下定理。

定理设an是齐次递归关系an+c1an-1+c2an-2=0的通解，而a*n是非齐次递归关系an+c1an-1+c2an-2=f(n)的任一特解，则an+a*n即为该方程的通解。

证明令pn为方程an+c1an-1+c2an-2=f(n)的任一解，而a*n为其任一特解。则二式相减，显见pn-a*n为的解。又已知an是这一齐次方程的通解。即an可用pn-a*n表示，亦即pn可用an+a*n表示。定理得证。为此，欲求解非齐次方程an+c1an-1+c2an-2=f(n)的通解，只需求出an+c1an-1+c2an-2=f(n)的一个特解a*n

。对一般f(n)，尚未找到一个普遍适用的求a*n的方法。但对f(n)较简单的情形，可有如下解法：（1）f(n)=c1（c为常数）。令A为待定常数，则若1不是特征根，k=0若1是特征方程的k重根

例1求解an-13an-2+12an-3=3。

解特征方程x3-13x+12=0的特征根为1,3,-4，且齐次通解为k1+k23n+k3(-4)n。因1是1重根，故取k=1。特解形式为代入原方程，求得A=-3/10。故非齐次通解为其中K1,K2,K3为任意常数。

例2求解递归关系an-2an-1=1。

解齐次递归关系的特征方程x2-2x=0的特征根为r1=0,r2=2。1不是特征根，故取a*n=A。递归关系的通解为an=K10n+K22n+A。若用初值a0=0,a1=1，则有K2=1，A=-1，即an=2n-1为递归关系的特解。（2）

f(n)=cn（c为常数）。令A为待定常数，则若c不是特征方程的根，k=0若c为特征方程的k重根

例3求解an-4an-1+4an-2=2n的通解。

解特征方程x2-4x+4=0的特征根为r1=r2=2。故其特解形式为a*n=An22n，代入递归关系可求得A=1/2。故原非齐次递归关系的通解为其中，K1,K2为任意常数。

例4求解an+2an-1+an-2=2n。

解特征方程为x2+2x+1=0，特征根为r1=r2=-1，因2不是特征根，故特解形式为将a*n代入an+2an-1+an-2=2n,求得A=4/9。递归关系的通解为其中，K1,K2为待定常数。

（3）f(n)=cnPm(n)，其中c为常数，Pm(n)是关于n的m次多项式。其特解形式为c不是特征方程的根，k=0c是特征方程的k重根其中，

Qm(n)是与Pm(n)同次的多项式。例5

求解an+4an-1+an-2=n(n-1)。解c=1,f(n)=n2-n。求得特征根为c=1不是特征根，故特解形式为代入递归关系有6An2+6(-2A+B)n+2(4A+3B+3C)=n2-n

比较等式两边同次幂系数，可得原非齐次递归关系通解为其中，K1,K2为任意常数。

例6求解递归关系an-2an-1=n3。

解此例c=1，f(n)=n3。求解特征方程x2-2x=0，得特征根r1=0，r2=2。因c=1不是特征根，故特解为an*=An3+Bn2+Cn+D将其代入an-2an-1=n3，解得A=-1,B=-6,C=-18,D=-26原递归关系的通解为an=K22n-n3-6n2-18n-26

例7求和14+24+…+n4。解令an=14+24+…+n4

，则由特征方程r2-r=0知,1是1重特征根，可得非齐次特解为

将其代入an-an-1=n4，比较ni的系数(i=0,1,2,3,4),可求得即非齐次特解为又因相应齐次递归关系的通解为由初值a0=0可求得K=0，故非齐次通解为5.4迭代法求解递归关系例1求解“Hanoi塔”问题:解例2(错排问题)

解错排问题所得结果为非线性递归关系。由题初值易得D0=1。整理原递归关系有Dn-nDn-1=-(Dn-1-(n-1)Dn-2)从而于是注意到D0=1有最后得例3

求解非线性递归关系：解由得例4求解非线性递归关系：解从而例5

求解递归关系：解例6

求解递归关系：解

例7对a,b,c,d4个字母构成的n位字符串，要求不出现“ab”，“ba”子串。求满足条件的不同n位字符串数目。

解令xn表示以a或b开头的n位字符串的方案数；yn表示以c或d开头的n位字符串的方案数，则可得如下递归关系:消去含y的项,得解特征方程x2-3x-2=0,得特征根为通解为考虑初值x0=0,x1=2，有解得又因为yn=xn+xn-1

故解得5.5生成函数方法求解递归关系定理设具有初值条件的k阶常系数线性递归关系为其中ck≠0，di是给定常系数，那么，{an}有生成函数其中

是不大于k-1次的多项式。当且仅当{an}关于递归关系的特征方程为证明设序列{an}的特征多项式和生成函数分别为G(x)=a0+a1x+a2x2+…+ak-1xk-1+akxk+…+anxn+…由递归关系，有将以上等式组两边相加，并注意c0=1，有即亦即其中，多项式P(x)的次数不大于k-1，c0=1。易知注意到（k次）特征多项式在复数域上有k个零点，可设从而

例1

已知序列{an}的生成函数为 ，求an。解法1

由定理1用x替代1/x,知特征方程为特征根为故利用整式除法知a0=1/2，a1=3/4解得从而解法2故例2

求如下递归关系的生成函数:解特征方程为对

k=2，c0=1，c1=c2=-1，F0=1，F1=1，求得例3求的生成函数。解例4

试求如下递归关系中{hn}的生成函数：解设解G2(x)-G(x)+x=0,得注意到，在第二章介绍二项式系数时，已有结论：从而因{hn}是正整数序列，故取最后有或

例5

将一个n+3边的凸多边形用不相交的n条对角线分成若干三角形，求不同的分解法。

解令Cn+1表示对n+3边形的不同分解法的数目。并规定C0=1,C1=1，现考虑n≥2时Cn+1的递归关系。固定一点v及其对边a所成三角形T，则T将凸多边形分成了两部分M1,M2，设M1有k+2条边（k=0,1,2,…,n,而k=0时意味着M1不存在），于是M2有n-k+2条边。显见对k+2边形M1有Ck种分解法，对M2有Cn-k种分解法。

由乘法原理，对某一固定点k，有CkCn-k种分解法。令k遍取0,1,2,…,n，可有如下递归关系式：这正是Catalan数列的形式。由生成函数的一般讨论即知例6求解递归关系：解设生成函数为G(x)=a1x+a2x2+a3x3+a4x4+…则-2xG(x)=-2a1x2-2a2x3-2a3x4+…

-2x2G(x)=-2a1x3-2a2x4+…三式相加并利用递归关系，有(1-2x-2x2)G(x)=a1x+(a2-2a1)x2=3x+2x2从而令则比较系数有即有于是由此例7

求解Hanoi塔问题：

解设 ,对等式hn=2hn-1+1，两边对应乘以xn，n=2,3,…。并将等式组左右两边相加。左端为：h2x2+h3x3+…+hnxn+…=G(x)-x

右端为：解方程得即有从而hn=2n-1

例8

求图5.5.1所示n级电路图的等效电阻Rn。

解所谓等效电阻，相当于用一个电阻Rn取代整个电路，使在两端点n和n′之间与原电路网络有同样效果。图5.5.1等效电阻Rn组成的n级电路图

Rn可视为Rn-1等效电阻与最后一组电路串并联构成。由欧姆定律，有因此令R=1（取单位电阻），可有再令Rn=an/bn，则a1=b1=1，从而由此，有方程组(5.5.1a)(5.5.1b)设{an},{bn}的生成函数分别为不难由(5.5.1a)和(5.5.1b)两式求得：

即解得由于所以又所以从而注意到 ，故对上式右端最后一个分式的分子分母同除以 ，可得

例9对给定存放于单元K(i)中的元素ai(i=1,2,…,n)，要求按照递增次序进行排序。

解

(1)直接选择排序法：第一步，从n个数中选出最大者，与K(n)中的数交换位置；第二步，从n-1个数中选出次大者，与K(n-1)中的数交换位置；

……

经n-1步，排序完成。

如下仅用比较次数计算该算法的时间复杂性。设T(n)表示用直接选择排序算法对n个元素排序所需的比较次数。则因第一次选最大元的比较次数为n-1，剩余的比较次数为T(n-1)。故由加法原理有如下递推关系：解得可见T(n)与n2同阶。(2)分治合并算法：