递推关系和生成函数.ppt

第7章 递推关系和生成函数,7.1 一些数列,算术序列（等差数列）几何序列（等比数列）例1：确定平面一般位置上的n个互相交叠的圆所形成的区域数。,例2(Fibonacci问题):Fibonacci数列是递推关系的又一典型问题,数列的本身有着许多应用.(1)问题的提出：假定初生的一对雌雄兔子,从出生的第2个月之后每个月都可以生出另外一对雌雄兔.如果第1个月只有一对初生的雌雄兔子,问n个月之后共有多少对兔子？,1月,2月,3月,4月,5月,6月,(2)求递推关系:设满n个月时兔子对数为Fn,则第n-1个月留下的兔子数目为Fn-1对;当月新生兔数目为Fn-2对,即第n-2个月的所有兔子到第n个月都有繁殖能力 Fn=Fn-1+Fn-2,F1=F2=1(7.1)由递推关系(7.1)式可依次得到 F3=F1+F2=2,F4=F2+F3=3,F5=F3+F4=3+2=5,前几项为：0，1，1，2，3，5，8，13，21，34，55，89，144，233，,(3)Fibonacci数列的性质部分和Sn=f0+f1+f2+fn=fn+2-1Fibonacci数列是偶数当且仅当n能被3整除Fibonacci数列满足公式,例3：令g0,g1,g2,gn,是满足下面给出的Fibonacci数列递推关系和初始条件：gn=gn-1+gn-2(n2)g0=2,g1=-1例4：确定2Xn棋盘用多米诺骨牌完美覆盖的方法数hn。例5：确定用单牌和多米诺骨牌对1Xn棋盘完美覆盖的方法数bn。,定理 沿Pascal三角形左下到右上对角线上的二项式系数的和是Fibonacci数,7.2 线性齐次递推关系,数列h0,h1,h2,hn,hn=a1hn-1+a2hn-2+akhn-k+bn(nk)错排数列Dn=(n-1)(Dn-2+Dn-1)(n 2)Dn=nDn-1+(-1)n(n 1)Fibonacci数列 Fn=Fn-1+Fn-2(n 2)阶乘序列hn=nhn-1(n 1)几何序列hn=qhn-1(n 1),hn=a1hn-1+a2hn-2+akhn-k(nk)其中a1,a2,ak 是常系数，称为常系数线性齐次递推关系。定理 令q为一非零数。则hn=qn是hn-a1hn-1-a2hn-2-akhn-k=0(ak0,nk)的解，当且仅当q是多项式方程xk-a1xk-1-a2xk-2-ak=0的一个根。如果多项式方程有k个不同的根q1,q2,qk，则hn=c1q1n+c2q2n+ckqkn,例6：求满足初始值h0=1,h1=2,h2=0的递推关系hn=2hn-1+hn-2-2hn-3(n3)的解例7：只由三个字母a,b,c组成的长度为n的一些单词将在通信信道上传输，满足条件：传输中不得有两个a连续出现在任一单词中。确定通信信道允许传输的单词个数。例8：递推关系hn=4hn-1-4hn-2(n2)的解定理7.2.2 令q1,q2,qt为hn=a1hn-1+a2hn-2+akhn-k(ak0,nk)的特征方程的互异的根。此时，如果qi是si重根，则对qi部分一般解为Hn(i)=(c1+c2n+csinsi-1)qin,7.3 非齐次递推关系,例9(Hanoi塔问题)：n个圆盘依其半径大小,从下而上套在柱A上,如图3.1所示.每次只允许取一个转移到柱B或C上,而且不允许大盘放在小盘上方.若要求把A上的n个盘转移到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)算法分析：令hn表示n个圆盘所需要的转移次数.根据算法先把前面n-1个盘子转移到B上;然后把第n个盘子转移到C上;最后再一次将B上的n-1个盘子转到C上.算法可实现性可用归纳法得到.因n=2时对,假定n-1对,那么n自然也对.关于转移次数容易得到一个递归关系:hn=2hn-1+1,h1=1.,例10：解hn=3hn-1-4n(n1)h0=2步骤总结求齐次关系的一般解求非齐次关系的一个特解将一般解和特解联合，按初始条件求系数困难在于特解的求解。例11：hn=2hn-1+3n(n1)h0=2例12：hn=3hn-1+3n(n1)h0=2 例13：hn=hn-1+n3(n1)h0=0,7.4 生成函数（母函数）,母函数就象一根晒衣绳,我们把需要得到的一列数就挂在它上面.假定我们的问题的解是一列数:a0,a1,a2,an,.我们想知道这个数列是什么,我们期望得到怎样的答案?当然,最好的答案就是关于an的一个简单的公式.比如诸如an=n2+3之类的表达式.即,通项公式.,但是,如果一个未知数列没有简单公式,或者即便存在,但是很复杂,很不容易得到,我们也不知道,该怎么办?如果我们还希望研究这个数列,讨论它的性质,该如何下手?举一个极端的例子,假定这个数列是2,3,5,7,11,13,17,19,23,.,此处an是第n个素数.这样的情况,期望任何简单的公式都是不合理的.,母函数把数列的所有成员用一种非常巧妙的方法联系在一起,虽然这样做并不一定能得到数列的简单公式,可是也许能够给出一个幂级数和的简单公式,展开这个和函数,所得到的幂级数的系数就是我们所要找的数列.比如后面我们将会学习到的Fibonacci 数列,它满足一个递归关系 Fn+1=Fn+Fn-1(n2;F1=F2=1).,1.母函数概念 设有a,b,c三个不同的球,从中选取一个,或选a,或选b,或选c,把这些可能的选取形象地表示为a+b+c.类似地,从中选取二个,或选a和b,或选a和c,或选b和c.可形象地表示为ab+ac+bc,同样,从中选取三个,只有一种方法,也可形象地表示为abc.,从多项式(1+ax)(1+bx)(1+cx)(7.2)=1+(a+b+c)x+(ab+ac+bc)x2+(abc)x3 中发现,所有这些可能的选取方式正好是x幂的系数.其中xi的系数是从三个球中选取i个的方法之形象表示.因子(1+ax)形象地指出,对球a,有两种选取方法:不选a,或选a.因子(1+ax)中的1表示不选a,而x的系数a表示选a.,既然在上述多项式中,xi的系数表明选取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)x2+C(3,3)x3=1+3x+3x2+x3.(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 利用给定序列a0,a1,a2,所构造的函数 F(x)=a0+a1x+a2x2+称为序列a0,a1,a2,的母函数.母函数定义中的级数是形式幂级数,不必关心收敛性,x只是一个形式变量.有限序列 a0,a1,an也可以定义它的母函数.(后面添加0),3.母函数的运算 设序列ai的母函数A(x)=aixi,bi的母函数为B(x)=bixi.运算定义如下:(1)相等:A(x)=B(x)ai=biai=bi,i=1,2,(2)相加:A(x)+B(x)=(ai+bi)xi(3)相减:A(x)-B(x)=(ai-bi)xi(4)数乘:cA(x)=(cai)xi,(5)相乘:A(x)B(x)=cixi,其中 c0=a0b0,c1=a0b1+a1b0,c2=a0b2+a1b1+a2b0,.,cr=a0br+a1br-1+arb0,.(6)逆:如果A(x)B(x)=1,则称B(x)为A(x)的逆,记为B(x)=A-1(x)=1/A(x).(显然两者互为逆.),例14 设F(x)=1+x+x2+,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-3x+2x2)=x.这说明,这与把它们看成普通函数的运算是一致的.,例16：令k是一个整数，并令序列h0,h1,h2,hn,使hn等于e1+e2+ek=n的非负整数解的个数。例17：确定苹果、香蕉、橘子和梨的n组合的个数，其中在每个n组合中苹果的个数是偶数，香蕉的个数是奇数，橘子的个数在0和4之间，而且至少要有一个梨。例18：确定可以由苹果、香蕉、橘子和梨袋装水果的袋数hn，其中在每个袋子中苹果数是偶数，香蕉数是5的倍数，橘子数最多是4个，梨的个数为0或1。,例19：确定方程e1+e2+ek=n的非负奇整数解e1,e2,ek的个数hn的母函数。例20：令hn表示方程3e1+4e2+2e3+5e4=n的非负整数解的个数。求h0,h1,h2,hn,的母函数g(x)。例21：有无限多现成的一分、五分、一角、两角五分和五角的硬币。确定用这些硬币凑成n分钱方法数hn的母函数g(x)。,7.5 母函数与递归,例22(Hanoi塔问题)：hn=2hn-1+1,h1=1.(7.4)令 H(x)=h1x+h2x2+h3x3+H(x)是序列h1,h2,h3,的母函数.给出了序列,就可确定对应的母函数.反过来也一样,求得了母函数,对应得序列也就可得而知.当然,利用递推关系(7.4)也可迭代求得h2,h3,.但现在我们一要寻找明确的公式,二要显示母函数的作用.,令H(x)=h1x+h2x2+h3x3+hnxn+为生成函数，有以下方程：H(x)=h1x+h2x2+h3x3+hnxn+-2xH(x)=-2h1x2-2h2x3-2h3x4-2hnxn+1-相加：(1-2x)H(x)=h1x+(h2-2h1)x2+(h3-2h2)x3+(hn-2hn-1)xn+=x(1+x+x2+x3+)=x/(1-x)H(x)=x/(1-x)(1-2x)(7.5),这就是转移次数数列的母函数.但是我们希望得到显式表达式.这不难做到.可以从母函数的幂级数展开式中求得数列h1,h2,h3,.我们下面所运用的方法是处理这种问题的一个常规的方法,初看起来可能感觉不太适应,用多了就习以为常了.这就是所谓的部分分数的算法.,(A+B)-(2A+B)x=x.,解得A=-1,B=1.其实一眼就可看出结果.这里只是想说 明方法而已.,(3)算法评价:hn是要移动圆盘数n(规模)的指数函数,以n=60为例子.可以计算出260 1.152921018.这个数是一个什么概念?假如你每秒钟移动一个盘,按照上述算法,你移动60个盘的时间是:,真是不算不知道,一算吓一跳.n=60,数不过百,2也是很小的整数,可是260却是一个很大的数.这就是所谓的“指数爆炸”现象.一般称复杂性为规模n的指数函数的算法为“坏算法”.好算法是指多项式算法或者线性算法.,例23：确定平方项序列0,1,4,n2,的母函数例24：求解满足初始值h0=1和h1=-2的递推关系hn=5hn-1-6hn-2(n2)例25：令h0,h1,hn,是满足递推关系hn+hn-1-16hn-2+20hn-3=0(n3)的数列，其中h0=0,h1=1,h2=-1。求hn的一般公式。,定理 令h0,h1,hn,为满足k阶常系数线性齐次递推关系hn-c1hn-1-c2hn-2-ckhn-k=0(ck0,nk)的数列。则它的生成函数g(x)形如g(x)=p(x)/q(x)其中，q(x)为具有非零常数项的k次多项式，p(x)是小于k次的多项式。反之也成立。,一般母函数是用基函数1,x,x2,来定义的.这种母函数对于组合类型的数列的研 究很有用.但是,对研究排列类型的数列用起来很不方便.排列类型数列是用基函数1,x,x2/2!,来定义,这样使用起来更方便一些.基本思想并没有变,只是选择了新的基.,7.6 指数生成函数,基函数正好是出现在函数ex的幂级数展开式中的函数:,设有数列a0,a1,a2,，则称下列函数为 该数列的指数型母函数:,构造指数型母函数的目的是为了使得母函数形式更简单,尤其对排列类型的递归数列更是如此.看几个简单例子.例26 设n为正整数,则数列P(n,0),P(n,1),P(n,2),P(n,n)的指数型母函数为:,其普通型母函数如何?,例27 数列1,1,1,的指数型母函数为,更一般的,设a为任意实数,数列a0=1,a1,a2,a3,的指数型母函数为,(a)设n=n1+n2+nk.若元素a1有n1个,元素a2有n2个,元素ak有nk个,则由 这n个元素组成的不同的排列总数为,(b)设n=n1+n2+nk.若元素a1有n1个,元素a2有n2个,元素ak有nk个,由这n个元素中取r个排列数为pr,则序列p0,p1,pn的指数型母函数为:,xr项的系数为ar=pr/r!.pr=arr!,定理 令S为多重集n1.a1,n2.a2,nk.ak,其中n1,n2,nk均为非负整数。令hn是S的n排列数，则序列h1,h2,hn的指数生成函数由 给定，其中，,例28 若有8个元素,其中设a1重复3次，a2重复2次,a3重复3次.从中取r个元素的排列数pr,则序列p0,p1,p2,p8的指数型母函数为:,如何得出pr?例如：p4=4!(35/12)=70.,例29 确定用红、绿、蓝三色对1n棋盘的方格进行染色的方案数an,并且使得绿色的方格数为偶数.,解 约定a0=1.显然 an为三种颜色组成的n阶排列,每种颜色的重复数没有限制,但是绿色在排列中必须出现偶数次.这样an的指数型母函数为,例30：令hn表示数字1，2或3组成的n位数字数的个数，其中1的个数为偶数，2的个数至少是3，3的个数最多是4。确定结果数列h1,h2,hn的指数生成函数。例31：确定每位数字都是奇数的n位数的个数hn，其中1和3出现偶数次。例32：确定用红色、白色和蓝色对1行n列棋盘的方格涂色的方法数hn，其中红方格的个数是偶数并且至少有一个蓝方格。,例33 一个凸n边形,通过不相交于n边形内部的对角线,把n边形拆分成若干三角形,不同拆分的数目用hn表之.五边形有如下五种拆分方案,故h5=5.,7.7 一个几何的例子,定理 通过画出区域内部不相交的对角线将具有n+1条边的凸多边形区域分割成三角形区域，令hn表示分成三角形区域的方法数。定义h1=1。则hn满足递推关系 该递推关系的解为,