组合数学-第5章

第五章递归关系第五章递归关系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…ABC图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骨牌覆盖示意图…………(a)(b)第五章递归关系解(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。由乘法原理得nkknknCCC11第五章递归关系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为任意常数。　证明0)()()()()(2,1,022212122212111112222112122111122112211nnnnnnnnnnnnnininircrcrKrcrcrKrKrKcrKrKcrKrKircrcr第五章递归关系定理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的解。0)2()1()(22112211nnnnnnxncxncnxxcxcxdxdx第五章递归关系定理4只要r1≠r2是方程x2+c1x+c2=0的二不同特征根，那么an=K1rn1+K2rn2一定是递归关系an+c1an-1+c2an-2=0的通解。其中K1,K2为任意实数。　证明假定an是具有初值的递归关系-11002211,0dadaacacannn的任一解。将初值条件代入nnnrKrKa22111221110210drKrKadKKa第五章递归关系由r1≠r2知，0111221rrrr即两方程线性无关,解得211202212101111,111rrdrdKrrrddK于是，由上式确定的K1,K2，可求得递归关系的一个特解：nnnrKrKa2211第五章递归关系例1求解具有初值条件F0=1,F1=1的递归关系Fn=Fn-1+Fn-2。解特征方程x2-x-1=0的根为：251,25121rr构造通解nnnrKrKF2211由初值条件确定K1,K2:2515125151112122111210KKrKrKFKKF第五章递归关系从而112515125151nnnF第五章递归关系例2求解递归关系an-2an-1-2an-2=0，a1=3，a2=8　a0=1。　解特征方程为x2-2x-2=0，特征根为nnnKKa)31()31(21根据初值条件求解K1,K2:3232,32323)31()31(121211210KKKKaKKa故nnna)31(3232)31(3232求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，一对共轭复根为231,23121irir通解为nnnrKrKD2211第五章递归关系由初值条件有D1=K1r1+K2r2=1　D2=K1r21+K2r22=0解得2331)(,2331)(2121212121irrrrKrrrrK昀后有nnniiiD23123312312331第五章递归关系例5an-2an-1-2an-2=0(n≥2)　a0=0,a1=1解特征方程为x2-2x+2=0;一对共轭复根为r1=α+βi，r2=α-βi，α=β=1。解得，θ=π/4，通解为24sin4cos)2(nBnAann第五章递归关系由初值条件得A=0，求解，得B=1。昀后所求特解为1)2/22/2(2BA4434,2)1(24,2)1(14,04sin)2(122mnmnmnmnnammmmnn或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通解形式为4141122010)2(22121211021KKKKKKaaKKannn第五章递归关系故an=2n-2+(-1)n-12n-2常系数二阶线性齐次递归关系的解法，可推广到高阶上去，对