组合数学第7章7.2

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(n

2、2) 和 Dn=nD(n1)+(1)n,（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) 的一个根. 若多

3、项式方程有k个不同的根q1, q2, qk,则 hn=c1q1n+ c2q2n+ ckqkn (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），

4、然后证明它是一般解。,3. 设 h0=b0, h1=b1, hk-1=bk-1是初始值，那么满足初始条件的c1, c2,., ck是下面线性方程组的解： 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: 求满足初

5、始值h0=1, h1=2和h2=0的递推关系:hn=2hn-1+hn-22hn3 解：递推关系的特征方程x32x2x+2=0的3个根分别是1, 1, 2. 根据定理 hn=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

6、,由递推关系求解：（类似方法）,递推关系的特征方程：x22x2=0 解得特征根：,，,一般解：,n3,代入初始值h0=1和h1=3，确定c1, c2. 得到方程组：,解得：,，,特征方程有重根情形,例. 递推关系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；

7、hn2=(n2)2n2 因此： hn4hn1+4hn2 = n2n4(n1)2n1+4(n2)2n2 =2n2(4n8(n1)+4(n2) =2n2(0) =0,（b）进一步可证明：对任意常数c1, c2，hn=c12n+c2n2n 是递推关系的一个解。 （c）代入初始条件：h0=a和h1=b得到 c1=a 2c1+2c2=b 方程组存在唯一解。因此，上式是递推关系的一般解。,一般情况,若q是常系数线性齐次递推关系的特征方程的s重根，那么 hn=qn, hn=nqn, hn=n2qn, hn=ns1qn 均是递推关系的一个解。（需验证） 其线性组合 hn=c1qn+c2nqn+c3n2qn+

8、csns1qn 也是一个解。,定理7.2.2 令q1, q2,qt为常系数线性齐次递推关系: hn=a1hn-1+a2hn-2+akhn-k (nk) 的特征方程的互异的根, 此时,如果qi是si的重根,则该递推关系对qi的部分一般解为: Hn(i) =c1qin+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,解线性方