组合数学〔第7章7.2〕.ppt

第七章 递推关系和生成函数 7.2 线性齐次递推关系 学习内容 7.2 线性齐次递推关系 重点：线性齐次递推关系的求解方法 学习运用代数的方法解决组合数学问题。 线性齐次递推关系的定义 定义: 令h0, h1, h2,…, hn,…是一个数列, 若存在量a1, a2,…,ak和bn(ak≠0,每个量是常数或依赖于n的数)使得: hn=a1hn-1+a2hn-2+…+akhn-k+bn (n≥k) 则称序列满足k阶线性递推关系. 若bn=0, 称齐次的; 若a1, a2, …,ak取常数,称常系数的. 一些例子 （1）错位排列数列D0, D1, D2,…, Dn,…满足 递推关系：Dn=(n?1)D(n?1)+(n?1)D(n?2) 和 Dn=nD(n?1)+(?1)n （3）几何序列的递推关系：hn=qhn?1， 1阶常系数线性齐次递推关系 本节重点讨论常系数线性齐次递推关系 常系数线性齐次递推关系的解 定理7.2.1 令q为一个非零数,则hn=qn是常系数线性齐次递推关系： hn=a1hn-1+a2hn-2+…+akhn-k (ak≠0, n≥k) (1) 的解, 当且仅当q是多项式方程 xk-a1xk-1- a2xk-2-…- ak=0 (2) 的一个根. 若多项式方程有k个不同的根q1, q2,…, qk,则 hn=c1q1n+ c2q2n+…+ ckqkn (3) 是下述意义下(1)的一般解: 任意给定初始值h0, h1, …,hk-1, 都存在c1, c2,…, ck使得(3)式是满足(1)式和初始条件的唯一的序列. 证明： 1. hn=qn满足递推关系当且仅当 定义 多项式方程xk?a1xk?1?a2xk?2?…?ak=0称为递推关系hn=a1hn-1+a2hn-2+…+akhn-k的特征方程，它的根称为特征根。 如果特征根互不相同，可以根据定理求出它的一般解。 例1: 求满足初始值h0=1, h1=2和h2=0的递推关系: hn=2hn-1+hn-2?2hn?3 解：递推关系的特征方程x3?2x2?x+2=0的3个根分别是1, ?1, 2. 根据定理 hn=c11n+c2(?1)n+c32n 是一般解。 代入初始条件得： 应用 例. 由3个字母a,b,c组成长度为n的一些单词在通信信道传输，满足：不得有两个a连续出现在任一个单词中。确定信道允许传输的单词数。 解：设hn表示允许传输的长度为n的单词数。可以得到递推关系： hn= (n?2) 由递推关系求解：（类似方法） 特征方程有重根情形 例. 递推关系hn=4hn?1? 4hn?2 (n?2)的特征方程是：x2?4x+4=(x?2)2=0, 2是2重特征根。 注意：hn=c12n+c22n 不是递推关系的一般解。并不总是能满足初始值。 例如：初始值h0=1, h1=3, 那么 c=1; 2c=3 没有解。hn不是一般解。 解：（a）我们知道hn=2n是递推关系的一个解，可以证明hn=n2n也是一个解。 hn=n2n； hn?1=(n?1)2n?1； hn?2=(n?2)2n?2 因此： hn?4hn?1+4hn?2 = n2n?4(n?1)2n?1+4(n?2)2n?2 =2n?2(4n?8(n?1)+4(n?2)) =2n?2(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=ns?1qn 均是递推关系的一个解。（需验证） 其线性组合 hn=c1qn+c2nqn+c3n2qn+?+ csns?1qn 也是一个解。 常系数线性递推关系的一般解 定理7.2.2 令q1, q2,…,qt为常系数线性齐次递推关系: hn=a1hn-1+a2hn-2+…+akhn-k (n≥k)