资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第十二章 生成函数与递推关系,12.1,幂级数型生成函数,（多重集组合）,12.2,指数型生成函数,（多重集排列）,12.3,递推关系,1/98,引言,1.,生成函数,(,母函数,),生成函数,(,称为母函数,),是组合数学中一个主要内容，可用来,求解组累计数,问题。,2/98,1),例,:,(1+a,1,x)(1+a,2,x)(1+a,n,x),=1+(a,1,+a,2,+a,n,)x+(a,1,a,2,+a,1,a,3,+a,n-1,a,n,)x,2,+a,1,a,2,a,n,x,n,x,系数为,a,1,+a,2,+a,n,;,/*,包含从,a,1,a,2,a,n,中取一个组合全体*,/,x,2,系数为,a,1,a,2,+a,1,a,3,+a,n-1,a,n,;,/*,包含从,a,1,a,2,a,n,中取两个组合全体*,/,x,3,系数为,a,1,a,2,a,3,+a,1,a,2,a,4,+a,n-2,a,n-1,a,n,;,/*,包含从,a,1,a,2,a,n,中取三个组合全体*,/,x,n,系数为,a,1,a,2,a,n,;,/*,包含从,a,1,a,2,a,n,中取,n,个组合全体*,/,3/98,若令,a,1,=a,2,=a,n,=1,则,(1+x),n,=1+C(n,1)x+C(n,2)x,2,+C(n,n)x,n,(1+x),n,=,C(n,k),：,从,a,1,a,2,a,n,中取,k,个组合数。,4/98,2),例：,(1+x),m,(1+x),n,=(1+x),m+n,左式,=C(m,0)+C(m,1)x+C(m,m)x,m,C(n,0)+C(n,1)x+C(n,n)x,n,右式,=C(m+n,0)+C(m+n,1)x+C(m+n,m+n)x,m+n,展开左式，得：,C(m,0),C(n,0)+C(m,1),C(n,0)+C(m,0),C(n,1)x+C(m,2),C(n,0)+C(m,1),C(n,1)+C(m,0),C(n,2)x,2,+C(m,m),C(n,n)x,m+n,5/98,比较对应项系数，得：,C(m+n,1)=C(m,1),C(n,0)+C(m,0),C(n,1),C(m+n,2)=C(m,2),C(n,0)+C(m,1),C(n,1)+C(m,0),C(n,2),普通有：,C(m+n,r)=C(m,0)C(n,r)+C(m,1)C(n,r-1)+C(m,r)C(n,0),/*Vandermonde,恒等式*,/,6/98,2.,生成函数,(,母函数,),定义,对于序列,a,0,a,1,a,2,，定义,a,0,+,a,1,x+a,2,x,2,+,为序列,a,0,a,1,a,2,生成函数,(,母函数,),。,比如：,(1+x),n,是,C(n,0),C(n,1),C(n,2),C(n,n),生成函数,(,母函数,),。,7/98,3.,生成函数,(,母函数,),实例,有红球两只，白球、黄球各一只，有多少种不一样组合方案？设,r,w,y,分别代表红球，白球和黄球。,8/98,解题思想：,红球不取（,r,0,=1,），取,1,只（,r,1,=r,），取,2,只（,r,2,）；,黄球不取（,y,0,=1,），取,1,只（,y,1,=y,），,白球不取（,w,0,=1,），取,1,只（,w,1,=w,），,依据乘法原理：,(1+r+r,2,)(1+w)(1+y),=1+(r+w+y)+(r,2,+ry+rw+yw)+(r,2,y+r,2,w+rwy)+r,2,yw,取一个球组合数为,3,：,r,，,w,，,y,取两个球组合数为,4,：,r,2,，,ry,，,rw,，,yw,取三个球组合数为,3,：,r,2,y,，,r,2,w,，,rwy,取四个球组合数为,1,：,r,2,yw,9/98,许多组合学计数问题依赖于一个整数参数,n,。这个参数,n,经常表示问题中某个基本集或多重集大小、组合大小、排列中位置等。所以一个计数问题经常不是一个孤立问题而是一系列单个问题。,例：令,h,n,表示,1,2,n,排列数。,h,n,=n!,，于是得到数列,h,0,h,1,h,2,h,n,。对于这个数列，普通项,h,n,=n!,，经过选择,n,为一个特定整数能够得到这个问题一个实例。如：,h,5,=5!,。,10/98,一个整数参数一些计数问题代数求解方法，或者造成一个显式公式，或者归结为一个函数，即生成函数，它幂级数系数给出计数问题解。,11/98,12.1,幂级数型生成函数,一、实例,二、生成函数定义,三、,形式幂级数运算性质,四、用生成函数来求多重集,r-,组合数,12/98,一、实例,11,章提到：,求多重集,S=n,1,a,1,n,2,a,2,n,k,a,k,(n=n,1,+n,2,+n,k,),r,-,组合数时，当对一切,i=1,2,k,有,n,i,r,时，有计算公式,N=C(k+r-1,r),；而当,rn,，且存在某个,n,i,r,利用容斥原理给予处理。,13/98,利用组合模型来模拟多重集,r-,组合数。,例：,设有,n,个标志为,1,2,n,网袋，第,i,个,(,i=1,2,n,),网袋里放有,n,i,个球。不一样网袋里球是不一样，而同一网袋里球则是没有差异，认为是相同。,14/98,多重集,S,一个,6-,组合,a,1,a,1,a,3,a,3,a,3,a,4,就对应于从第,1,个网袋里取,2,个球，第,3,个网袋里取,3,个球，第,4,个网袋里取,1,个球。,从第,1,个网袋里取,2,个球，第,3,个网袋里取,3,个球，第,4,个网袋里取,1,个球。就对应了,S,一个,6-,组合,a,1,a,1,a,3,a,3,a,3,a,4,。,15/98,多重集,S,r,-,组合数就等于从,n,个网袋里取,r,个球取法数。用,x,代表球，,x,i1,代表从第,1,个网袋里取,i,1,个球，,x,i2,代表从第,2,个网袋里取,i,2,个球，,x,ik,代表从第,k,个网袋里取,i,k,个球。,i,1,i,2,i,k,个满足条件,i,1,+i,2,+i,k,=r,(,i,j,n,j,j=1,2,k,),。故,x,i1,x,i2,x,ik,=x,i1+i2+ik,=x,r,就对应了多重集,S,一个,r,-,组合。因为给出,1,个,x,r,组成就等于给出了多重集,S,一个,r,-,组合，所以,x,r,系数就是多重集,S,r,-,组合数。,利用上述方法就得到了求组合数方法，就称为,生成函数法,。,16/98,二、生成函数定义,定义,12.1,：设,a,0,a,1,a,n,是一个数列，结构形式幂级数,f(x)=a,0,+a,1,x+a,2,x,2,+a,n,x,n,+,称,f(x),是数列,a,0,a,1,a,n,生成函数,，且两个形式幂级数,相等当且仅当对每个,i,，有,a,i,=b,i,。,17/98,对于有限序列，可看成自某项后全为,0,无穷序列。,18/98,为何称为形式幂级数？,依据高等数学，作为幂级数要讨论它们收敛范围，即当,x,在收敛范围内取值时，幂级数才会收敛于某个函数,f(x),。而这里，,x,仅是记号，并不需要赋值，从而也不需要考虑收敛范围，故称为形式幂级数，而,x,也称为形式变元。,19/98,三、,形式幂级数运算性质,定理,12.1,：设数列,a,n,b,n,c,n,生成函数分别是,f(x),g(x),和,h(x),，,r,为常数。,(1),假如,b,n,=ra,n,，则,g(x)=rf(x),。,(2),假如,c,n,=a,n,+b,n,，则,h(x)=f(x)+g(x),。,(3),假如,则,h(x)=f(x)*g(x),。,20/98,21/98,22/98,(6),假如,则,23/98,24/98,(8),假如,b,n,=r,n,a,n,，则,g(x)=f(rx),。,(9),假如,b,n,=na,n,，则,g(x)=,xf(x),。,25/98,26/98,/*,证实思想：定义,12.1*/,27/98,例,12.1,(1),设有质量分别为,n,1,克，,n,2,克，,n,k,克,k,个砝码。现要用天平称,i,克物体，物体放在左边，砝码放在右边，共有多少种不一样称法,?,28/98,(2),用质量分别为,1,克，,2,克，,4,克，,8,克，,16,克,5,个砝码，在天平上能称几个质量物体？每种质量物体有几个不一样称法,?,29/98,(3),用,2,个质量为,1,克，,3,个质量为,2,克，,2,个质量为,5,克砝码在天平上能称几个质量物体,?,且每种质量物体有几个不一样称法,?,30/98,解：,(1),设有,a,i,种方法称,i,克物体。,K,个形式幂集数,积为,(1+x,n1,)(1+x,n2,)(1+x,nk,),。该展开式中,x,i,幂起源于,x,m1,x,m2,x,mk,=x,i,，,m,1,+m,2,+m,k,=i,m,j,0,n,j,。,其中第一个括弧提供,m,1,次幂，第二个括弧提供,m,2,次幂，,，第,k,个括弧提供,m,k,次幂，,m,j,=0(x,0,=1),表示,n,j,克砝码没有用上，,m,j,=n,j,表示,n,j,克砝码用上了，所以展开式中,x,i,系数恰好是称,i,克物体方法数，故有：,31/98,(2),设质量,r,克物体有,a,r,种称法，则数列,a,r,生成函数是,f(x)=(1+x)(1+x,2,)(1+x,4,)(1+x,8,)(1+x,16,),/*1+x,表示砝码为,1,克或者不取或者取,取了就是,1,克,1+x,16,表示砝码为,16,克或者不取或者取,取了就是,16,克*,/,(1-x)f(x),=(1-x)(1+x)(1+x,2,)(1+x,4,)(1+x,8,)(1+x,16,),=1-x,32,。,所以,f(x)=(1-x,32,)/(1-x)=1+x+x,2,+x,31,。,因为,x,i,前面系数都是,1,，这表明凡是不超出,31,克物体都能用给定,5,个砝码称出，且每个恰有一个称法。,32/98,(3),设质量,r,克物体有,a,r,种称法，则数列,a,r,生成函数是,f(x),=(1+x+x,2,)(1+x,2,+(x,2,),2,+(x,2,),3,)(1+x,5,+(x,5,),2,),）,/*1+x+x,2,表示,2,个质量为,1,克砝码或者不用,(x,0,=1),，或者用,1,个,(x,1,=x),，或者用,2,个,(x,2,)*/,=1+x+2x,2,+x,3,+2x,4,+2x,5,+3x,6,+3x,7,+2x,8,+2x,9,+2x,10,+3x,11,+3x,12,+2x,13,+2x,14,+x,15,+2x,16,+x,17,+x,18,。,/*,表明凡是质量不超出,18,克物体都能用给定砝码称出。其中质量为,1,3,15,17,18,克只有一个称法，质量为,2,4,5,8,9,10,13,14,16,克物体有,2,种称法，而质量为,6,7,11,12,克物体有,3,种称法。*,/,33/98,四、用生成函数来求多重集,r-,组合数,例,12.2,：设多重集,S=,a,1,a,2,a,k,，,S,r,-,组合数是,a,r,=C(r+k-1,r),，它也是方程,x,1,+x,2,+x,k,=r,非负整数解个数。现用生成函数方法求,a,r,。,34/98,设,a,r,生成函数为,f(y),，结构幂级数,(1+y+y,2,+),k,/*(1+y+y,2,+),表示,a,i,能够不取,取,1,个,2,个,*/,展开该式，,y,r,幂起源于,y,x1,y,x2,y,xk,=y,x1+x2+xk,x,1,+x,2,+x,k,=r,，其中,y,x1,来自第一个因式,(1+y+y,2,+),，,y,x2,来自第二个因式,(1+y+y,2,+),，,，,y,xk,来自第,k,个因式,(1+y+y,2,+),，且,x,1,x,2,x,k,为非负整数。所以展开式中,y,r,系数对应了不定方程,x,1,+x,2,+x,k,=r,非负整数解个数。故所结构幂级数就是,a,r,生成函数,f(y),。由推论,11.4,可得,:,所以,a,r,=C(k+r-1,r),35/98,设多重集,S=n,1,a,1,n,2,a,2,n,k,a,k,，,S,r-,组合数,a,r,就相当于方程,x,1,+x,2,+x,k,=r(x,1,n,1,x,2,n,2,x,k,n,k,),非负整数解组数。设,a,r,生成函数为,f(y),，类似能够得到：,f(y)=(1+y+y,2,+y,n1,)(1+y+y,2,+y,n2,)(1+y+y,2,+y,nk,),，则,f(y),展开式中,y,r,系数,a,r,就是所求,S,r-,组合数。,36/98,例,12.3,:,设,S=,a,1,a,2,a,k,，求,S,每个元素只出现偶数次,r,-,组合数,a,r,。,解：令,a,r,生成函数是,f(y),，因为要求,S,每个元素只出现偶数次，则对,a,1,来讲，或者不出现，或者是,2,，,4,，,6,，,其它也类似。故生成函数为：,f(y)=(1+y,2,+y,4,+),k,=1/(1-y,2,),k,=1+ky,2,+C(k+1,2)y,4,+C(k+n-1,n)y,2n,+,所以有,37/98,例,12.4,：求,x,1,+x,2,+x,3,=5(0,x,1,0,x,2,1,x,3,),整数解组数。,解：令,x,3,=x,3,-1,，则原问题即为求在约束条件,0,x,1,0,x,2,0,x,3,下,x,1,+x,2,+x,3,=4,非负整数解组数。解组数为,a,4,a,r,生成函数是,所以有,a,4,=C(4+2,4)=15,。,38/98,12.2,指数型生成函数,1.,问题提出：用生成函数处理排列问题,a,1,a,n,互不相同,，,n,个元素,a,1,a,n,全排列：,n,！。,假如其中,a,1,重复,n,1,次，全排列：,n,!/,n,1,!,。,假如其中,a,1,重复,n,1,次，,a,2,重复,n,2,次，,，假如其中,a,h,重复,n,h,次，,n,1,+,n,2,+,n,h,=,n,;,全排列：,39/98,例：,8,个元素中,a,1,重复,3,次，,a,2,重复,2,次，,a,3,重复,3,次，从中取,r,个组合。,解：,(1+x,1,+x,1,2,+x,1,3,)(1+x,2,+x,2,2,)(1+x,3,+x,3,2,+x,3,3,),=1+(x,1,+x,2,)+(x,1,2,+x,1,x,2,+x,2,2,)+(x,1,3,+x,1,2,x,2,+x,1,x,2,2,)+(x,1,3,x,2,+x,1,2,x,2,2,)+x,1,3,x,2,2,(1+x,3,+x,3,2,+x,3,3,),40/98,展开式中,4,次方项为,:,x,1,x,3,3,+x,2,x,3,3,+x,1,2,x,3,2,+x,1,x,2,x,3,2,+x,2,2,x,3,2,+x,1,3,x,3,+x,1,2,x,2,x,3,+x,1,x,2,2,x,3,+x,1,3,x,2,+x,1,2,x,2,2,x,1,x,3,3,项表示,1,个,a,1,3,个,a,3,;,x,1,x,2,2,x,3,项表示,1,个,a,1,2,个,a,2,1,个,a,3,;,x,1,x,3,3,对应排列数为,4!/1!3!,x,1,x,2,2,x,3,对应排列数为,4!/1!2!1!.,41/98,取,4,个元素排列数为,:,42/98,指数型生成函数,:,43/98,取,4,个排列数为,取,5,个排列数为,44/98,2.,定义,12.2:,设,a,0,a,1,a,n,是一个数列，结构形式幂级数,称,f(x),是数列,a,0,a,1,a,n,指数型生成函数。,45/98,定理,12.2,：设,a,n,b,n,指数生成函数分别为,f,e,(x),和,g,e,(x),，则：,其中,46/98,例：数列,1,1,1,指数型生成函数为,:,47/98,3.,指数型生成函数来处理多重集排列问题,定理,12.3,：,设有限多重集,S=n,1,a,1,n,2,a,2,n,k,a,k,，且,n=n,1,+n,2,+n,k,，对任意非负整数,r,，,r,为,S,r,-,排列数，则数列,r,指数型生成函数为：,g(x)=g,n1,(x)g,n2,(x)g,nk,(x),，其中,g,ni,(x)=1+x+x,2,/2!+x,ni,/n,i,!,i=1,2,k,。,48/98,证实思想：要证实,r,指数型生成函数为,g,n1,(x)g,n2,(x)g,nk,(x),，关键是证实,g,n1,(x)g,n2,(x)g,nk,(x),展开式中项,x,r,/r!,系数就是,r,。,49/98,证实：,/*,考查,g,n1,(x)g,n2,(x)g,nk,(x),展开式中项,x,r,/r!,情况。*,/,x,r,项为下述项之和,其中,m,1,+m,2,+m,k,=r,0,m,i,n,i,i=1,2,k.,50/98,上式能够写成,:,所以在,g(x),展开式中 系数是,:,51/98,这里求和是对方程,m,1,+m,2,+m,k,=r,0,m,i,n,i,(i=1,2,k.),一切非负整数解进行求和。又因为对固定,m,1,，,m,2,，,，,m,k,，就是,S,r,元子集,m,1,x,1,m,2,x,2,m,k,x,k,全排列数。,故,a,r,就是,S,全部,r,元子集全排列数之和，即,S,r-,排列数。所以,g(x),展开式中 系数,a,r,就是多重集,S,r-,排列数。,52/98,例,12.5,：设有,6,个数字，其中,3,个数字,1,2,个数字,6,1,个数字,8,，问能组成多少个四位数,?,解：这实际上是求,S=3,x,1,2,x,2,1,x,3,中取,4,个多重集排列数问题。其指数型生成函数为：,g(x),=(1+x+x,2,/2!+x,3,/3!)(1+x+x,2,/2!)(1+x),=1+3x+8(x,2,/2!)+19(x,3,/3!)+38(x,4,/4!)+60(x,5,/5!)+60(x,6,/6!),由此可得,a,4,=38,，即可组成,38,个四位数。,53/98,泰勒级数,54/98,例：求,1,，,3,，,5,，,7,，,9,这,5,个数字组成,n,位数个数，要求其中,3,和,7,出现次数为偶数，其它数字出现次数无限制。,解：,55/98,56/98,12.3,递推关系,1.,递推综述,递推关系是离散变量之间改变规律中常见一个方式，与生成函数一样是处理计数问题有力工具。,对数列,u,n,如从某项后，,u,n,前,k,项可推出,u,n,普遍规律，就称为,递推关系,。,利用递推关系和初值在一些情况下能够求出序列通项表示式,u,n,，称为该,递推关系解,。,57/98,2.,递推关系实例,1),例,12.6,：,13,世纪初意大利数学家,Fibonacci,研究过著名兔子繁殖数目问题,:,设一对一雌一雄小兔刚满,2,个月时，便可繁殖出一雌一雄一对小兔。以后每隔,1,个月生一对一雌一雄小兔。由一对刚出生小兔开始喂养到第,n,个月，有多少对兔子,?,58/98,解：设第,n,个月有,F,n,对兔子，它由两部分组成,:,(1),新生出小兔，其数目等于能生小兔大兔对数目，因为小兔满两个月才能繁殖，故数目为第,(n-2),个月时兔对数目，即为,F,n-2,。,(2),原有小兔，其数目等于上月,(,即第,n-1,个月,),兔对数目，即为,F,n-1,。,所以可建立以下递推关系,:,F,n,=F,n-2,+F,n-1,，并有初始条件：,F,1,=F,2,=1,。即这是一个带有初值递推关系。,/*,满足这种递推关系数列称为,Fibonacci,数列*,/,59/98,2),例,12.7,：设多重集,S=,a,b,c,，求,a,不相邻,n-,排列数。,60/98,解,:,设,a,不相邻,n-,排列数为,a,n,。,则,a,1,=3,a,2,=3,2,-1=8 /*,减,1,是为了减去,aa,*,/,当,n,3,时，,a,不相邻全部,n,-,排列可分为互不相容两类,:,(1),第一个位置排,b,或,c,，剩下,n-1,个位置,a,不相邻，由,a,n,定义知，,a,不相邻,(n-1),-,排列数为,a,n-1,，依据乘法标准，这类排列数为,2a,n-1,。,(2),第一个位置排,a,，则第二个位置只能排,b,或,c,，而剩下,n-2,个位置,a,不相邻，由,a,n,定义知，,a,不相邻,(n-2),-,排列数为,a,n-2,，依据乘法标准，这类排列数为,2a,n-2,。由加法标准知，,a,不相邻,n-,排列数为,:,a,n,=2a,n-1,+2a,n-2,，并有初始条件,:,a,1,=3,a,2,=8,即这是一个带有初值递推关系。,61/98,思想总结：分而治之,62/98,3.,两种求解递推关系方法,1),求解常系数线性递推关系特征根方法,63/98,（,1,）,定义,12.3,数列,a,n,满足递推关系,a,n,=h,1,a,n-1,+h,2,a,n-2,+h,k,a,n-k,h,i,为常数，,i=1,2,k,nk,h,k,0,，称该递推关系为,a,n,k,阶常系数线性齐次递推关系,。,形如,a,n,=h,1,a,n-1,+h,2,a,n-2,+h,k,a,n-k,+f(n),h,i,为常数，,i=1,2,k,nk,h,k,0,，称该递推关系为,a,n,k,阶常系数线性非齐次递推关系,。,64/98,k,阶常系数线性齐次递推关系与微分方程,y,(k),=h,1,y,(k-1),+h,2,y,(k-2),+h,k,y,，,h,i,为常数,（,i=1,2,k,）,在结构上类似；,k,阶常系数线性非齐次递推关系与微分方程,y,(k),=h,1,y,(k-1),+h,2,y,(k-2),+h,k,y+f(n),，,h,i,为常数,(,i=1,2,k,),在结构上也类似；,求解方法也与对应微分方程类似。,65/98,（,2,）求解方法,求解常系数线性递推关系基本方法是寻找形如,a,n,=r,n,解。,a,n,=r,n,是,a,n,=h,1,a,n-1,+h,2,a,n-2,+h,k,a,n-k,解，,r,n,=h,1,r,n-1,+h,2,r,n-2,+h,k,r,n-k,等价方程,r,k,-h,1,r,k-1,-h,2,r,k-2,-h,k,=0,。,这个方程称为该递推关系,特征方程,，方程解称为该递推关系,特征根,。,66/98,（,3,）定义,12.4:,方程,x,k,-h,1,x,k-1,-h,2,x,k-2,-h,k,=0,称为,k,阶常系数线性齐次递推关系,特征方程,它,k,个根,q,1,q,2,q,k,称为该递推关系,特征根,。其中,q,i,(i=1,2,k),是复数。,67/98,定理,12.4.,a,n,=q,n,q0,是常系数线性齐次递推关系解充要条件是,:,q,是该递推关系特征根。,68/98,定理,12.5:,若,k,阶常系数线性齐次递推关系特征方程有,k,个互异特征根,:,q,1,q,2,q,k,，则该递推关系通解为,:,a,n,=c,1,q,1,n,+c,2,q,2,n,+c,k,q,k,n,其中,c,1,c,2,c,k,为任意常数。,69/98,例,12.8,求例,12.7,带初值递推关系解。,解：例,12.7,递推关系特征方程为：,x,2,-2x-2=0,其根为：,由定理,12.5,，递推关系通解为：,70/98,要满足初值条件，故有：,71/98,所以，,a,不相邻,n-,排列数为,:,72/98,定理,12.6:,若,k,阶常系数线性齐次递推关系特征方程有,t,个互异特征根,:,q,1,q,2,q,t,，,m,1,m,2,m,t,为对应根重数，,且,m,1,+m,2,+,+m,t,=k,则该递推关系通解为,:,其中,c,ij,为任意常数,(1jm,i,1it),为任意常数。,73/98,例,12.9,求解递推关系,a,n,+a,n-1,-3a,n-2,-5a,n-3,-2a,n-4,=0,n,4,a,0,=1,a,1,=a,2,=0,a,3,=2,74/98,解,:,该递推关系特征方程是,x,4,+x,3,-3x,2,-5x-2=0,其特征根是,-1,-1,-1,2,。由定理,12.6,得：,a,n,=c,11,(-1),n,+c,12,n(-1),n,+c,13,n,2,(-1),n,+c,21,2,n,代入初值得到以下方程组：,c,11,+c,21,=1,-c,11,-c,12,-c,13,+c,21,=0,c,11,+2c,12,+4c,13,+4c,21,=0,-c,11,-3c,12,-9c,13,+8c,21,=2,75/98,解此方程组得：,c,1,=7/9,c,2,=-13/16,c,3,=1/16,c,4,=1/8,故递推关系解是：,a,n,=7/9(-1),n,-(13/16)n(-1),n,+(1/16)n,2,(-1),n,+(1/8)2,n,76/98,(4),k,阶常系数线性非齐次递推关系,k,阶常系数线性非齐次递推关系通解与,k,阶常系数线性非齐次微分方程通解类似,也是齐次通解与特解之和，即：,a,n,=a,n,+a,n,*,其中,a,n,是,k,阶常系数线性非齐次递推关系所对应,k,阶常系数线性齐次递推关系,a,n,=h,1,a,n-1,+h,2,a,n-2,+,+h,k,a,n-k,=0,通解，而,a,n,*,是,k,阶常系数线性非齐次递推关系特解。,77/98,求解方法,对于,a,n,由定理,12.6,即得，故关键是,a,n,*,求解。对于普通,f(n),没有普遍解法，在一些简单情况下可用待定系数法求出,a,n,*,。,78/98,(1),当,f(n),是,n,t,次多项式时，对应特解形式为：,a,n,*,=P,1,n,t,+P,2,n,t-1,+,+P,t,n+P,t+1,，,其中,P,1,P,2,P,t,P,t+1,为待定系数。,(2),当,f(n),是,n,形式时，若,不是对应齐次递推关系特征根，则对应特解是,P,n,，其中,P,为待定系数；若,是对应齐次递推关系,m,重特征根，则对应特解是,Pn,m,n,，其中,P,为待定系数。,79/98,例,12.10:,求解递推关系,a,n,+2a,n-1,=n+1,n,1,a,0,=2,。,80/98,解,:,该递推关系导出齐次线性递推关系,a,n,+2a,n-1,=0,特征方程是,x+2=0,，其特征根是,-2,。由定理,12.5,知其通解为,a,n,=c(-2),n,；又因,f(n)=n+1,，故它特解含有形式,a,n,*,=P,1,n+P,2,，其中,P,1,P,2,为待定系数。将其代入原递推关系,P,1,n+P,2,+2(P,1,(n-1)+P,2,)=n+1,，即：,3P,1,n+3P,2,-2P,1,=n+1,，比较上式两端,n,同次幂系数，得：,P,1,=1/3,P,2,=5/9,。所以，,a,n,*,=(n/3)+5/9,是原递推关系特解。而它通解是,a,n,=c(-2),n,+(n/3)+5/9,。要它满足初值，只须,2=c+(5/9),故,c=13/9,。所以带初值递推关系解为：,a,n,=(13/9)(-2),n,+(n/3)+5/9,81/98,例,:,求,h(n)=2h(n-1)+1,并有初始条件,:,h(1)=1,递推关系,解,:,特征根,x=2,所以,h(n)=c2,n,因为,f(n)=1,所以特解,h*(n)=P,1,代入原递推关系,P,1,=2P,1,+1,所以,P,1,=-1,.,所以,h(n)=c2,n,-1,.,因为,h(1)=1,所以,c=1,.,故,h(n)=2,n,-1,.,82/98,例,:,求解下面递推关系特解,a,n,=a,n-1,+7n,n,1.,83/98,解,:,该递推关系导出齐次线性递推关系,a,n,-a,n-1,=0,特征方程是,x-1=0,，其特征根是,1,。因为,f(n)=7n,，假如设特解为,a,n,*,=P,1,n+P,2,代入原递推关系,P,1,n+P,2,-P,1,(n-1)-P,2,=7n,，即：,P,1,=7n,，与,P,1,为常量矛盾。其原因是当唯一特征根是,1,时,若所设特解中,n,最高次幂与,f(n),一样时,代入递推关系后,等式左边,n,最高次幂比右边次数低,在此情况上,采取,升幂,方法,且可不设常数项,.,令,a,n,*,=P,1,n,2,+P,2,n,代入原递推关系化简后得,:,2P,1,n+P,2,-P,1,=7n,，比较上式两端,n,同次幂系数，得：,2P,1,=7,P,2,-P,1,=0,，所以,P,2,=P,1,=7/2,。所以，,a,n,*,=7n/2+7/2,84/98,85/98,解：递推关系：,a,n,=4a,n-1,-5a,n-2,+2a,n-3,n,3,(*),特征方程,x,3,-4x,2,+5x-2=0,特征根,x,1,=x,2,=1,x,3,=2,通解：,a,n,=c,1,+c,2,*n+c,3,*2,n,因为,2,是,(*),一重特征根，所以递推关系,a,n,=4a,n-1,-5a,n-2,+2a,n-3,+2,n,(*),(n,3),有形如,a,n,=A*n*2,n,特解，其中,A,为常数。以,a,n,=A*n*2,n,代入,(*),，得,A*n*2,n,=,4,*,A*,（,n-1)*2,n-1,-5*A*(n-2)*2,n-2,+2*A*(n-3)*2,n-3,+2,n,A=4,86/98,所以,a=c,1,+c,2,*n+c,3,*2,n,+4*n*2,n,，由初始条件,87/98,88/98,例：,89/98,解：递推关系,a,n,=7a,n-1,-10a,n-2,n,2,(*),特征方程,x,2,-7x+10=0,，,x,1,=2,，,x,2,=5,，则,(*),通解为,a,n,=c,1,*2,n,+c,2,*5,n,。,因为,3,不是,(*),特征根，所以递推关系,a,n,=7a,n-1,-10a,n-2,n,2,(*),有形如,a,n,=A*3,n,特解，,A,为常数。以,a,n,=A*3,n,代入,(*),，得,A*3,n,=7*,A*3,n-1,10*,A*3,n-2,2*,3,n-3,，即,9A=21A-10A-2,，,A=1,。,a,n,=c,1,*2,n,+c,2,*5,n,+,3,n,。,90/98,由初始条件,91/98,4.,生成函数方法求解递推关系,在求解递推关系时，生成函数法也是一个有力工具。用生成函数法求解递推关系关键是用,f(x),表示,a,n,生成函数，即：,然后将,a,n,递推关系代入右边，便得到一个关于,f(x),方程，解此方程，并将所得解展开成幂级数，就可得到,a,n,表示式。,92/98,例,:,用生成函数法求解递推关系,:,a,n,=a,n-1,+9a,n-2,-9a,n-3,n,3,a,0,=0,a,1,=1,a,2,=2,93/98,解,:,设,a,n,生成函数为：,f(x)=a,0,+a,1,x+a,2,x,2,+,+a,n,x,n,+,则：,-xf(x)=-a,0,x-a,1,x,2,+-a,2,x,3,+a,n,x,n+1,-,-9x,2,f(x)=-9a,0,x,2,-9a,1,x,3,-9a,2,x,4,-,-9a,n-2,x,n,-,9x,3,f(x)=9a,0,x,3,+9a,1,x,4,+9a,n-3,x,n,+,94/98,以上四式相加得：,(1-x-9x,2,+9x,3,)f(x)=a,0,+(a,1,-a,0,)x+(a,2,-a,1,-9a,0,)x,2,+(a,3,-a,2,-9a,1,+9a,0,)x,3,+,+(a,n,-a,n-1,-9a,n-2,+9a,n-3,)x,n,+,因为,a,0,=0,a,1,=1,a,2,=2,，且当,n,3,时,a,n,-a,n-1,-9a,n-2,+9a,n-3,=0,，,(a,n,=a,n-1,+9a,n-2,-9a,n-3,),所以有：,(1-x-9x,2,+9x,3,)f(x)=x+x,2,即：,f(x)=(x+x,2,)/(1-x-9x,2,+9x,3,),=(x+x,2,)/(1-x)(1+3x)(1-3x),95/98,而,1/(1-x)=1+x+x,2,+,+x,n,+,；,1/(1+3x)=1-3x+3,2,x,2,-,+(-1),n,3,n,x,n,+,；,1/(1-3x)=1+3x+3,2,x,2,+,+3,n,x,n,+,；,所以有：,96/98,作业,:2,3,4,5,7,8,10,12,14(1)(3),15,97/98,98/98,
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
