第7章 递推关系和生成函数.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,7,章 递推关系和生成函数,7.1,一些数列,算术序列（等差数列）,几何序列（等比数列）,例,1,：确定平面一般位置上的,n,个互相交叠的圆所形成的区域数。,例,2,(Fibonacci,问题,):,Fibonacci,数列是递推关系的又一典型问题,数列的本身有着许多应用,.,(1),问题的提出,：假定初生的一对雌雄兔子,从出生的第,2,个月之后每个月都可以生出另外一对雌雄兔,.,如果第,1,个月只有一对初生的雌雄兔子,问,n,个月之后共有多少对兔子？,1,月,2,月,3,月,4,月,5,月,6,月,(2),求递推关系,:,设满,n,个月时兔子对数为,F,n,则第,n,-1,个月留下的兔子数目为,F,n-1,对,;,当月新生兔数目为,F,n-2,对,即第,n,-2,个月的所有兔子到第,n,个月都有繁殖能力,F,n,=F,n,-1,+F,n,-2,F,1,=F,2,=1,(7.1),由递推关系,(7.1),式可依次得到,F,3,=F,1,+F,2,=2,F,4,=F,2,+F,3,=3,F,5,=F,3,+F,4,=3+2=5,前几项为：,0,，,1,，,1,，,2,，,3,，,5,，,8,，,13,，,21,，,34,，,55,，,89,，,144,，,233,，,(3),Fibonacci,数列的性质,部分和,S,n,=f,0,+f,1,+f,2,+f,n,=f,n+2,-1,Fibonacci,数列是偶数当且仅当,n,能被,3,整除,Fibonacci,数列满足公式,例,3,：令,g,0,g,1,g,2,g,n,是满足下面给出的,Fibonacci,数列递推关系和初始条件：,g,n,=g,n-1,+g,n-2,(n,2)g,0,=2,g,1,=-1,例,4,：确定,2Xn,棋盘用多米诺骨牌完美覆盖的方法数,h,n,。,例,5,：确定用单牌和多米诺骨牌对,1Xn,棋盘完美覆盖的方法数,b,n,。,定理,7.1.2,沿,Pascal,三角形左下到右上对角线上的二项式系数的和是,Fibonacci,数,7.2,线性齐次递推关系,数列,h,0,h,1,h,2,h,n,h,n,=a,1,h,n-1,+a,2,h,n-2,+,a,k,h,n-k,+b,n,(,n,k,),错排数列,D,n,=(n-1)(D,n-2,+D,n-1,),(n,2),D,n,=nD,n-1,+(-1),n,(n,1),Fibonacci,数列,F,n,=F,n,-1,+F,n,-2,(n,2),阶乘序列,h,n,=nh,n-1,(n,1),几何序列,h,n,=qh,n-1,(n,1),h,n,=a,1,h,n-1,+a,2,h,n-2,+,a,k,h,n-k,(,n,k,),其中,a,1,a,2,a,k,是常系数，称为常系数线性齐次递推关系。,定理,7.2.1,令,q,为一非零数。则,h,n,=,q,n,是,h,n,-a,1,h,n-1,-a,2,h,n-2,-,a,k,h,n-k,=0(a,k,0,n,k),的解，当且仅当,q,是多项式方程,x,k,-a,1,x,k-1,-a,2,x,k-2,-,a,k,=0,的一个根。如果多项式方程有,k,个不同的根,q,1,q,2,q,k,，则,h,n,=c,1,q,1,n,+c,2,q,2,n,+,c,k,q,k,n,例,6,：求满足初始值,h,0,=1,h,1,=2,h,2,=0,的递推关系,h,n,=2h,n-1,+h,n-2,-2h,n-3,(n,3),的解,例,7,：只由三个字母,a,b,c,组成的长度为,n,的一些单词将在通信信道上传输，满足条件：传输中不得有两个,a,连续出现在任一单词中。确定通信信道允许传输的单词个数。,例,8,：递推关系,h,n,=4h,n-1,-4h,n-2,(n,2),的解,定理,7.2.2,令,q,1,q,2,q,t,为,h,n,=a,1,h,n-1,+a,2,h,n-2,+,a,k,h,n-k,(a,k,0,n,k),的特征方程的互异的根。此时，如果,q,i,是,s,i,重根，则对,q,i,部分一般解为,H,n,(i,),=(c,1,+c,2,n+c,si,n,si-1,)q,i,n,7.3,非齐次递推关系,例,9,(,Hanoi,塔问题,),：,n,个圆盘依其半径大小,从下而上套在柱,A,上,如,图,3.1,所示,.,每次只允许取一个转移到柱,B,或,C,上,而且,不允许大盘放在小盘上方,.,若要求把,A,上的,n,个盘转移到,C,柱上,.,请设计一种方法,并估计要移动几个盘次,.,现在只有,A,B,C,三根柱子可供使用,.,图,A,B,C,4,1,3,2,Hanoi,塔是个经典问题,.,对于这个问题,我们先要设计算法,进而估计算法的计算复杂性,这里就是,移动的总次数,.,(1),算法设计：,n,=2,时,圆盘,1,从,A,套在,B,上；把圆盘,2,从,A,转移到,C,上；把圆盘,1,从,B,上转移到,C,上,.,完毕,.,n,=3,时,把圆盘,1,从,A,转移到,C,上；把圆盘,2,从,A,转移到,B,上；把圆盘,1,从,C,上转移到,B,上,;,把圆盘,3,从,A,套在,C,上,;,把圆盘,1,从,B,再转移到,A,上,;,把圆盘,2,从,B,转移到,C,上,把圆盘,1,从,A,套在,C,上,.,完毕,.,看看,n,=3,的演示过程,.,A,B,C,假定,n,-1,个盘子的转移算法已经确定,.,对,n,个圆盘问题,先把上面的圆盘,1,2,n,-1,转移到,B,上,再把最后一个盘子转移到,C,上,然后把,B,上的,n,-1,个圆盘转移到柱,C,上,.,转移完毕,.,这运用的是递归算法,n,=2,时给出了算法,;,n,=3,时先利用,n,=2,时的算法把圆盘,1,2,移,B,上,;,再把圆盘,3,转移到柱,C,上,;,再利用,n,=2,时的算法把,B,上两个圆盘转移到柱,C,上,.,n,=4,5,以此类推,.,(2),算法分析,：令,h,n,表示,n,个圆盘所需要的转移次数,.,根据算法先把前面,n,-1,个盘子转移到,B,上,;,然后把第,n,个盘子转移到,C,上,;,最后再一次将,B,上的,n,-1,个盘子转到,C,上,.,算法,可实现性,可用归纳法得到,.,因,n,=2,时对,假定,n,-1,对,那么,n,自然也对,.,关于转移次数容易得到一个递归关系,:,h,n,=2,h,n,-,1,+1,h,1,=1.,例,10,：解,h,n,=3h,n-1,-4n(n,1)h,0,=2,步骤总结,求齐次关系的一般解,求非齐次关系的一个特解,将一般解和特解联合，按初始条件求系数,困难在于特解的求解。,例,11,：,h,n,=2h,n-1,+3,n,(n,1),h,0,=2,例,12,：,h,n,=3h,n-1,+3,n,(n,1),h,0,=2,例,13,：,h,n,=h,n-1,+n,3,(n,1),h,0,=0,7.4,生成函数（母函数）,母函数就象一根晒衣绳,我们把需要得到的一列数就挂在它上面,.,假定我们的问题的解是一列数,:,a,0,a,1,a,2,a,n,.,我们想知道这个数列是什么,我们期望得到怎样的答案,?,当然,最好的答案就是关于,a,n,的一个简单的公式,.,比如诸如,a,n,=,n,2,+3,之类的表达式,.,即,通项公式,.,但是,如果一个未知数列没有简单公式,或者即便存在,但是很复杂,很不容易得到,我们也不知道,该怎么办,?,如果我们还希望研究这个数列,讨论它的性质,该如何下手,?,举一个极端的例子,假定这个数列是,2,3,5,7,11,13,17,19,23,.,此处,a,n,是第,n,个素数,.,这样的情况,期望任何简单的公式都是不合理的,.,母函数,把数列的所有成员用一种非常巧妙的方法联系在一起,虽然这样做并不一定能得到数列的简单公式,可是也许能够给出一个,幂级数和,的简单公式,展开这个和函数,所得到的,幂级数,的,系数,就是我们所要找的,数列,.,比如后面我们将会学习到的,Fibonacci,数列,它满足一个递归关系,F,n,+1,=F,n,+F,n,-1,(,n,2;F,1,=F,2,=1).,1.,母函数概念,设有,a,b,c,三个不同的球,从中选取一个,或选,a,或选,b,或选,c,把这些可能的选取形象地表示为,a,+,b,+,c,.,类似地,从中选取二个,或选,a,和,b,或选,a,和,c,或选,b,和,c,.,可形象地表示为,ab,+,ac,+,bc,同样,从中选取三个,只有一种方法,也可形象地表示为,abc,.,从多项式,(1+,ax,)(1+b,x,)(1+c,x,),(7.2),=,1,+,(,a+b+c,),x+,(,ab+ac+bc,),x,2,+,(,abc,),x,3,中发现,所有这些可能的选取方式正好是,x,幂的系数,.,其中,x,i,的系数是从三个球中选取,i,个的方法之形象表示,.,因子,(1+,ax,),形象地指出,对球,a,有两种选取方法,:,不选,a,或选,a,.,因子,(1+,ax,),中的,1,表示不选,a,而,x,的系数,a,表示选,a,.,既然在上述多项式中,x,i,的系数表明选取,i,个球的方法,那么,(1+,ax,)(1+,bx,)(1+,cx,),所表明的是,:,对,a,b,c,三球,选取的方法是,“,选,a,或不选,a,”,和“选,b,或不选,b,”,以及“选,c,或不选,c,”.,多项式中,x,的幂次表示选取球的个数,而其相应系数表示一切可能的选取方法,.,如果我们只,关心,不同组合方案的,数目,不关心,各种,方案,的罗列,.,可以在,(7.2),式中令,a,=,b,=,c,=1,则得到,(1+,x,),3,=C(3,0)+C(3,1),x,+C(3,2),x,2,+C(3,3),x,3,=1+3,x,+3,x,2,+,x,3,.,(7.3),总方案数,N=C(3,0)+C(3,1)+C(3,2)+C(3,3),=1+3+3+1=8.,(7.3),就是一个关于形式变量,x,的幂函数,这个幂函数中不同幂次的系数都是一个组合数,.,这可以推广到任意,n,个不同球所有可能组合的方案数情况,.,这其实就是我们大家熟悉的二项式系数,.,不过现在我们是用形式级数的观点来看问题,.,利用这种形式级数不仅仅是一种不同的表达形式,还非常有用,.,2.,母函数定义,定义,7.1,利用给定序列,a,0,a,1,a,2,所构造的函数,F(,x,)=,a,0,+,a,1,x,+,a,2,x,2,+,称为序列,a,0,a,1,a,2,的,母函数,.,母函数定义中的级数是,形式幂级数,不必关心收敛性,x,只是一个形式变量,.,有限序列,a,0,a,1,a,n,也可以定义它的母函数,.(,后面添加,0,),3.,母函数的运算,设序列,a,i,的母函数,A(x,)=,a,i,x,i,b,i,的母函数为,B(,x,)=,b,i,x,i,.,运算定义如下,:,(1),相等,:,A(,x,)=,B(,x,),a,i,=,b,i,a,i,=,b,i,i,=1,2,(2),相加,:,A(,x,)+B(,x,)=,(,a,i,+,b,i,),x,i,(3),相减,:,A(,x,)-B(x,)=,(,a,i,-,b,i,),x,i,(4),数乘,:,cA(,x,)=,(,c,a,i,),x,i,(5),相乘,:,A(,x,)B(,x,)=,c,i,x,i,其中,c,0,=a,0,b,0,c,1,=a,0,b,1,+a,1,b,0,c,2,=a,0,b,2,+a,1,b,1,+a,2,b,0,.,c,r,=a,0,b,r,+a,1,b,r-1,+a,r,b,0,.,(6),逆,:,如果,A(,x,)B(,x,)=1,则称,B(,x,),为,A(,x,),的逆,记为,B(,x,)=A,-1,(,x,)=1/A(,x,).,(,显然两者互为逆,.),例,14,设,F(x,)=1+,x,+,x,2,+,G(,x,)=1-,x,由定义可以得到,F(,x,)G(,x,)=1,因此,1/G(,x,)=,G,-1,(,x,)=,F(,x,),即,这同微积分中函数,1/(1-,x,),的幂级数展开式是完全一致的,.,例,15,设,则,(F(,x,)-G(,x,)(1-3,x,+2,x,2,)=,x,.,这说明,这与把它们看成普通函数的运算是一致的,.,例,16,：令,k,是一个整数，并令序列,h,0,h,1,h,2,h,n,使,h,n,等于,e,1,+e,2,+,e,k,=n,的非负整数解的个数。,例,17,：确定苹果、香蕉、橘子和梨的,n,组合的个数，其中在每个,n,组合中苹果的个数是偶数，香蕉的个数是奇数，橘子的个数在,0,和,4,之间，而且至少要有一个梨。,例,18,：确定可以由苹果、香蕉、橘子和梨袋装水果的袋数,h,n,，其中在每个袋子中苹果数是偶数，香蕉数是,5,的倍数，橘子数最多是,4,个，梨的个数为,0,或,1,。,例,19,：确定方程,e,1,+e,2,+,e,k,=n,的非负奇整数解,e,1,e,2,e,k,的个数,h,n,的母函数。,例,20,：令,h,n,表示方程,3e,1,+4e,2,+2e,3,+5e,4,=n,的非负整数解的个数。求,h,0,h,1,h,2,h,n,的母函数,g(x,),。,例,21,：有无限多现成的一分、五分、一角、两角五分和五角的硬币。确定用这些硬币凑成,n,分钱方法数,h,n,的母函数,g(x,),。,7.5,母函数与递归,例,22,(,Hanoi,塔问题,),：,h,n,=2,h,n,-,1,+1,h,1,=1.,(7.4),令,H(,x,)=,h,1,x,+,h,2,x,2,+,h,3,x,3,+,H(,x,),是序列,h,1,h,2,h,3,的母函数,.,给出了序列,就可确定对应的母函数,.,反过来也一样,求得了母函数,对应得序列也就可得而知,.,当然,利用递推关系,(7.4),也可迭代求得,h,2,h,3,.,但现在我们一要寻找明确的公式,二要显示母函数的作用,.,令,H(x,)=h,1,x+h,2,x,2,+h,3,x,3,+,+,h,n,x,n,+,为生成函数，有以下方程：,H(x,)=h,1,x+h,2,x,2,+h,3,x,3,+,+,h,n,x,n,+,-2xH(x)=-2h,1,x,2,-2h,2,x,3,-2h,3,x,4,-,-2,h,n,x,n+1,-,相加：,(1-2x)H(x)=h,1,x+(h,2,-2h,1,)x,2,+(h,3,-2h,2,)x,3,+,+(,h,n,-2h,n-1,)x,n,+,=x(1+x+x,2,+,x,3,+),=x/(1-x),H,(,x,),=x/,(1,-x,)(1,-2x,),(7.5),这就是转移次数数列的母函数,.,但是我们希望得到,显式,表达式,.,这不难做到,.,可以从母函数的幂级数展开式中求得数列,h,1,h,2,h,3,.,我们下面所运用的方法是处理这种问题的一个,常规,的方法,初看起来可能感觉不太适应,用多了就习以为常了,.,这就是所谓的部分分数的算法,.,(A+B)-(2A+B)x=x.,解得,A=-1,B=1.,其实一眼就可看出结果,.,这里只是想说,明方法而已,.,(3),算法评价,:,h,n,是要移动圆盘数,n,(,规模,),的指数函数,以,n,=60,为例子,.,可以计算出,2,60,1.15292,10,18,.,这个数是一个什么概念,?,假如你每秒钟移动一个盘,按照上述算法,你移动,60,个盘的时间是,:,真是不算不知道,一算吓一跳,.,n,=60,数不过百,2,也是很小的整数,可是,2,60,却是一个很大的数,.,这就是所谓的“,指数爆炸,”现象,.,一般称复杂性为规模,n,的指数函数的算法为“,坏算法,”,.,好算法,是指多项式算法或者线性算法,.,例,23,：确定平方项序列,0,1,4,n,2,的母函数,例,24,：求解满足初始值,h,0,=1,和,h,1,=-2,的递推关系,h,n,=5h,n-1,-6h,n-2,(n,2),例,25,：令,h,0,h,1,h,n,是满足递推关系,h,n,+h,n-1,-16h,n-2,+20h,n-3,=0,(n,3),的数列，其中,h,0,=0,h,1,=1,h,2,=-1,。求,h,n,的一般公式。,定理,7.5.1,令,h,0,h,1,h,n,为满足,k,阶常系数线性齐次递推关系,h,n,-c,1,h,n-1,-c,2,h,n-2,-,c,k,h,n-k,=0(c,k,0,n,k),的数列。则它的生成函数,g(x,),形如,g(x,)=,p(x)/q(x,),其中，,q(x,),为具有非零常数项的,k,次多项式，,p(x,),是小于,k,次的多项式。反之也成立。,一般母函数是用基函数,1,x,x,2,来定义的,.,这种母函数对于,组合类型的数列,的研 究很有用,.,但是,对研究,排列类型的数列,用起来很不方便,.,排列类型数列是用基函数,1,x,x,2,/2!,来定义,这样使用起来更方便一些,.,基本思想并没有变,只是选择了新的,基,.,7.6,指数生成函数,基函数正好是出现在函数,e,x,的幂级数展开式中的函数,:,设有数列,a,0,a,1,a,2,，,则称下列函数为,该数列的,指数型母函数,:,构造指数型母函数的目的是为了使得母函数形式更简单,尤其对排列类型的递归数列更是如此,.,看几个简单例子,.,例,26,设,n,为正整数,则数列,P(,n,0),P(,n,1),P(,n,2),P(,n,n,),的,指数型母函数,为,:,其普通型母函数如何,?,例,27,数列,1,1,1,的指数型母函数为,更一般的,设,a,为任意实数,数列,a,0,=1,a,1,a,2,a,3,的指数型母函数为,(a),设,n,=,n,1,+,n,2,+,n,k,.,若元素,a,1,有,n,1,个,元素,a,2,有,n,2,个,元素,a,k,有,n,k,个,则由,这,n,个元素组成的不同的排列总数为,(b),设,n,=,n,1,+,n,2,+,n,k,.,若元素,a,1,有,n,1,个,元素,a,2,有,n,2,个,元素,a,k,有,n,k,个,由这,n,个元素中取,r,个排列数为,p,r,则序列,p,0,p,1,p,n,的指数型母函数为,:,x,r,项的系数,为,a,r,=p,r,/r!.,p,r,=,a,r,r,!,定理,令,S,为多重集,n,1,.a,1,n,2,.a,2,n,k,.a,k,其中,n,1,n,2,n,k,均为非负整数。令,h,n,是,S,的,n,排列数，则序列,h,1,h,2,h,n,的指数生成函数由 给定，其中，,例,28,若有,8,个元素,其中设,a,1,重复,3,次，,a,2,重复,2,次,a,3,重复,3,次,.,从中取,r,个元素的排列数,p,r,则序列,p,0,p,1,p,2,p,8,的指数型母函数为,:,如何得出,p,r,?,例如：,p,4,=4!,(35/12)=70.,例,29,确定用,红,、,绿,、,蓝,三色对,1,n,棋盘的方格进行染色的方案数,a,n,并且使得,绿色,的方格数为,偶数,.,解,约定,a,0,=1,.,显然,a,n,为三种颜色组成的,n,阶排列,每种颜色的重复数没有限制,但是绿色在排列中必须出现偶数次,.,这样,a,n,的指数型母函数为,例,30,：,令,h,n,表示数字,1,，,2,或,3,组成的,n,位数字数的个数，其中,1,的个数为偶数，,2,的个数至少是,3,，,3,的个数最多是,4,。确定结果数列,h,1,h,2,h,n,的指数生成函数。,例,31,：,确定每位数字都是奇数的,n,位数的个数,h,n,，其中,1,和,3,出现偶数次。,例,32,：,确定用红色、白色和蓝色对,1,行,n,列棋盘的方格涂色的方法数,h,n,，其中红方格的个数是偶数并且至少有一个蓝方格,。,例,33,一个凸,n,边形,通过不相交于,n,边形内部的对角线,把,n,边形拆分成若干三角形,不同拆分的数目用,h,n,表之,.,五边形有如下五种拆分方案,故,h,5,=5,.,7.7,一个几何的例子,定理,通过画出区域内部不相交的对角线将具有,n+1,条边的凸多边形区域分割成三角形区域，令,h,n,表示分成三角形区域的方法数。定义,h,1,=1,。则,hn,满足递推关系,该递推关系的解为,