《组合数学(第7章7.2).ppt》由会员分享，可在线阅读，更多相关《组合数学(第7章7.2).ppt（25页珍藏版）》请在三一办公上搜索。
1、第七章 递推关系和生成函数 7.2 线性齐次递推关系,学习内容,7.2 线性齐次递推关系重点：线性齐次递推关系的求解方法学习运用代数的方法解决组合数学问题。,线性齐次递推关系的定义,定义:令h0,h1,h2,hn,是一个数列,若存在量a1,a2,ak和bn(ak0,每个量是常数或依赖于n的数)使得:hn=a1hn-1+a2hn-2+akhn-k+bn(nk)则称序列满足k阶线性递推关系.若bn=0,称齐次的;若a1,a2,ak取常数,称常系数的.,一些例子,（1）错位排列数列D0,D1,D2,Dn,满足递推关系：Dn=(n1)D(n1)+(n1)D(n2)和 Dn=nD(n1)+(1)n,（2
2、）斐波那契序列f0,f1,f2,fn,递推关系：fn=f(n1)+f(n2)2阶常系数线性齐次递推关系,（3）几何序列的递推关系：hn=qhn1，1阶常系数线性齐次递推关系本节重点讨论常系数线性齐次递推关系,二次函数,导数,递推关系是一般项函数的“离散导数”。,常系数线性齐次递推关系的解,定理7.2.1令q为一个非零数,则hn=qn是常系数线性齐次递推关系：hn=a1hn-1+a2hn-2+akhn-k(ak0,nk)(1)的解,当且仅当q是多项式方程xk-a1xk-1-a2xk-2-ak=0(2)的一个根.若多项式方程有k个不同的根q1,q2,qk,则 hn=c1q1n+c2q2n+ckqk
3、n(3)是下述意义下(1)的一般解:任意给定初始值h0,h1,hk-1,都存在c1,c2,ck使得(3)式是满足(1)式和初始条件的唯一的序列.,证明：1.hn=qn满足递推关系当且仅当,qna1qn1a2qn2akqnk=0,即q是方程 xka1xk1a2xk2ak=0的根。,2.设q1,q2,.,qk是方程的k个不同的根。那么，hn=q1n,hn=q2n,hn=qkn是递推关系的不同的解，可以验证hn=c1q1n+c2q2n+ckqkn也满足递推关系（1），然后证明它是一般解。,3.设 h0=b0,h1=b1,hk-1=bk-1是初始值，那么满足初始条件的c1,c2,.,ck是下面线性方程
4、组的解：c1+c2+.+ck=b0 c1q1+c2q2+.+ckqk=b1 c1q1k-1+c2q2k-1+ckqkk-1=bk-1方程组的系数矩阵是范德蒙矩阵，因此，方程组存在唯一解。,范德蒙行列式,0,因此，式（3）是递推关系的一般解。,定义,多项式方程xka1xk1a2xk2ak=0称为递推关系hn=a1hn-1+a2hn-2+akhn-k的特征方程，它的根称为特征根。如果特征根互不相同，可以根据定理求出它的一般解。,例1:求满足初始值h0=1,h1=2和h2=0的递推关系:hn=2hn-1+hn-22hn3解：递推关系的特征方程x32x2x+2=0的3个根分别是1,1,2.根据定理 h
5、n=c11n+c2(1)n+c32n是一般解。代入初始条件得：,解得c1=2,c2=2/3,c3=1/3，因此，hn=22/3(1)n1/32n,应用,例.由3个字母a,b,c组成长度为n的一些单词在通信信道传输，满足：不得有两个a连续出现在任一个单词中。确定信道允许传输的单词数。解：设hn表示允许传输的长度为n的单词数。可以得到递推关系：hn=(n2),n,1,2,3,b,c,2hn1,+2hn2,a,b,c,由递推关系求解：（类似方法）,递推关系的特征方程：x22x2=0解得特征根：,，,一般解：,n3,代入初始值h0=1和h1=3，确定c1,c2.得到方程组：,解得：,，,特征方程有重根
6、情形,例.递推关系hn=4hn1 4hn2(n2)的特征方程是：x24x+4=(x2)2=0,2是2重特征根。注意：hn=c12n+c22n 不是递推关系的一般解。并不总是能满足初始值。例如：初始值h0=1,h1=3,那么 c=1;2c=3 没有解。hn不是一般解。,解：（a）我们知道hn=2n是递推关系的一个解，可以证明hn=n2n也是一个解。hn=n2n；hn1=(n1)2n1；hn2=(n2)2n2 因此：hn4hn1+4hn2=n2n4(n1)2n1+4(n2)2n2=2n2(4n8(n1)+4(n2)=2n2(0)=0,（b）进一步可证明：对任意常数c1,c2，hn=c12n+c2n
7、2n 是递推关系的一个解。（c）代入初始条件：h0=a和h1=b得到 c1=a 2c1+2c2=b 方程组存在唯一解。因此，上式是递推关系的一般解。,一般情况,若q是常系数线性齐次递推关系的特征方程的s重根，那么 hn=qn,hn=nqn,hn=n2qn,hn=ns1qn均是递推关系的一个解。（需验证）其线性组合 hn=c1qn+c2nqn+c3n2qn+csns1qn也是一个解。,定理7.2.2 令q1,q2,qt为常系数线性齐次递推关系:hn=a1hn-1+a2hn-2+akhn-k(nk)的特征方程的互异的根,此时,如果qi是si的重根,则该递推关系对qi的部分一般解为:Hn(i)=c1
8、qin+c2nqin+csinsi-1qin递推关系的一般解为:hn=Hn(1)+Hn(2)+Hn(t),常系数线性递推关系的一般解,应用,例.求递推关系hn=hn1+3hn2+5hn3+2hn4满足初始值h0=1,h1=0,h2=1,h3=2的解。解：递推关系的特征方程为 x4+x33x25x2=0特征根：重根x1=x2=x3=1,x4=2.,对重根1得到:Hn=c1(1)n+c2n(1)n+c3n2(1)n对应根2是：Hn=c42n那么一般解：hn=Hn+Hn=c1(1)n+c2n(1)n+c3n2(1)n+c42n代入初始关系：,(1),(2),(1),(2),c1+c4=1,c1c2 c3+2c4=0,c1+2c2+4c3+4c4=1,c13c2 9c3+8c4=2,解线性方程组，确定系数得到解：,小结,求解线性齐次递推关系的步骤：（1）给出相应的特征方程；（2）求解特征方程，如果没有重根，则直接给出一般解；若有重根，根据重根求出一般解；（3）将初始条件代入一般解，得到满足初始条件的解。,作业,习题7.8.14),15),16).,
