组合数学课件4常系数递归关系

1《图论与组合优化》第五讲

常系数递归关系2第四讲:

常系数递归关系I

.常系数齐次递归关系

(1)

特征值为不同的实数

(2)

特征值均为实数但是有重根(3)

特征值有复根*

II.常系数非齐次递归关系*3I.常系数齐次线性递归关系常系数线性递归关系有齐次和非齐次两种.设Hn是一个递归数列.常系数齐次递归关系:其中

是实常数,f(n)非零.

常系数非齐次递归关系:4假定ar≠0,

则递归关系(4.1)称为是r阶的.如果序列中r个相邻的H值Hk-r,Hk-r+1,

…,Hk-1对某一k已知,则可用(4.1)算出Hk的值,于是Hk+1,Hk+2,…的值也可递归的算出.所以(4.1)的解唯一的由r个相邻的H值(边界条件)所决定.因此,(4.1)的解的一般形式包含有r个待定常数,这些常数可由序列中相邻的r个H值来决定.一般给定初值:H0,H1,…,Hr-1.5

对于(4.1)中的r阶齐次递归关系:

我们定义如下的一元

r

次方程:称(4.2)为(4.1)的特征方程.特征方程的根叫原递归关系的特征根(值).6定理

设q1,q2是二次齐次递推方程

Hn+2+a1Hn+1+a2Hn=0的两个特征根，则Hn是递推方程的解的充要条件是Hn可表成如下形式：

当q1≠q2时，

Hn=b1q1n+b2q2n;(1)

当q1=q2=q时，

Hn=(b1+b2n)qn

(2)其中b1,b2为常数。7证明：充分性.当q1≠q2时,将(1)代人递推方程的左边，因q1,q2是特征根，有即

Hn=b1q1n+b2q2n

是递推方程的解。8当q1=q2=q时,将(2)代人递推方程的左边，因q是重根，2q+a1=0即

Hn=(b1+b2n)qn

是递推方程的解。9必要性

设Hn是二次齐次递推方程

Hn+2+a1Hn+1+a2Hn=0的解，因为q1,q2是两个特征根，由韦达定理，q1+q2=-a1,q1q2=a2,

代人递推方程，得

Hn+2-(q1+q2)Hn+1+q1q2Hn=0,即得

Hn+2-q1Hn+1=q2(Hn+1-q1Hn)(3)

Hn+2-q2Hn+1=q1(Hn+1-q2Hn)(4)10当q1≠q2时，令Fn=Hn-q1Hn-1，Gn=Hn-q2Hn-1

则(3),(4)式化为

Fn+2=q2Fn+1，Gn+2=q1Gn+1所以

Fn+1=q2nF1，Gn+1=q1nG1从而有

Hn+1-q1Hn=q2nF1

Hn+1-q2Hn=q1nG1两式相减，得11当q1=q2=q时，令Fn=Hn-qHn-1，

则(3),(4)式化为

Fn+2=qFn+1，所以

Fk=qk-1F1，从而有

Hk=qHk-1+qk-1F1上式两边乘于qn-k，再自k=1至k=n取和，得等式两边展开，得因为a2≠0，故q≠0,记c1=H0,c2=F1/q,则有12

对于(4.1)中的r阶齐次递归关系:

我们定义如下的一元

r

次方程:称(4.2)为(4.1)的特征方程.特征方程的根叫原递归关系的特征根(值).下面我们根据特征根的情况来给出相应的解法.

131.有r个不同的实特征根定理4.1

设q1,q2,…,qr是递归关系(4.1)

的r个互不相同的实特征根,则其一般解为:

证(1)

先证(4.3)一定是原来的递归关系的解.

在(4.3)式当中,令n

取n-1,n-2,…,n-r,得到r个等式:1415把这r个等式相加并整理,右边正好是(4.3)的右边,即得到这说明(4.3)中定义的数列满足定理4.1中的递归关系(4.1).

从而证明了对任意参数c1,c2,…,cr而言(4.3)都是定理中递归关系的一个解.16(2)下面证明任何一个解都可以表示成(4.3)的形式.对任意一个解hn来说,它由边界条件h0=b0,h1=b1,…,

hr-1=br-1完全确定.由(1)我们知道(4.3)定义的数列都满足定理中的递归关系.我们需要证明由这些边界条件可以完全决定一般解(4.3)中的参数c1,c2,…,cr.17我们使用待定系数法来证明c1,c2,…,cr存在性.根据需要可以得到联立方程组这个方程组的系数矩阵的行列式在著名的Vandermonde行列式.18因为所有的特征值q1,q2,…,qr都不相同,所以这个行列式不为零.于是原方程组关于c1,c2,…,cr有唯一解.说明在这种条件下(4.1)的解是唯一确定的.

19例4.1

Fibonacci数列的递归关系:

Fn=Fn-1+Fn-2,F0=F1=1(4.4)可以利用特征值的方式来求解这个递归关系.解

该递归关系的特征方程为x2-x-1=0,其特征根为20可设该数列的解为:

由边界条件得到方程组21解这个方程组得到:

所以,该递归数列的解为例4.2

求解递归关系22解

该递归关系所对应的特征方程:设递归关系:特征根:由边界条件确定常数c1,c2,c3.

需要解下列线性方程组:23解之可得:通解为:例4.3

在信道上传输仅用3个字母a,b,c组成并且长度为n的词.规定连续出现两个a的词不能传输.试确定这个信道允许传输的词的个数.解

令h(n)为允许传输长度为n的词总数,n=1,2,….

直接计算知,h(1)=3,h(2)=8.24设n≥3,第一个字母是b或c的词数均为h(n-1);

第一个字母是a的词,第二个字母必须是b或c,这种词的数目为2h(n-2).故有以下递归关系:

且h(1)=3,h(2)=8.

该递归关系的特征方程为25

其特征根为：

故一般解为:由边界条件h(1)=3,h(2)=8

解方程组：262.特征根有重根的情况

对于这种情况,我们只通过例题说明求解方法,最后给出一般结论,不详细推导.例4.4

求解递归关系:解

特征方程:可见3是二重特征根.此时,除了Hn=3n这个解之外,还有一个解:

Hn=n3n.27一般解可设为:

利用边界条件得到线性方程组并求解:28定理4.2

设q1,q2,…,qt是递归关系

全部不同特根,qi的重数为ei(i=1,2,…,t),

则该递归关系对应于qi部分的一般解是:293.仅有两个有复特征根*当特征方程有复数根时,因为复数根总是成对出现的,而且任意复数a+bi都可以写成ceid的形式,故可设两个复根分别为30

此时这两个根对应的一般解部分为:

因此这部分解也可以设为:

其中A,B为待定参数,可利用边界条

件得到.31例4.5

给定边界条件a1=1,a2=0,求解递归关系:解

该递归关系对应的特征方程为:其特征根为:32所以其中该递归关系的一般解可设为:33由边界条件a1=1,a2=0,

便可决定A和B,这只需要解下列方程组:34例

有n枚相同的棋子，甲、乙两人轮流取子，每次可取1至2枚，取完为止。求首尾两次都是甲取子的取法种数Hn.解：递推方程为其中规定其特征方程为354个特征根为所以，通解为其中c1,c2,b1,b2为待定常数36把初始条件代人通解，得方程组解得37II.常系数线性非齐次递归关系*

线性非齐次递归关系:这里,a1,…,

ar全部是常数.例如:都是常系数线性非齐次递归关系.38常系数线性非齐次递归关系的求解方法与非齐次线性方程组的求解思路类似.非齐次通解=齐次通解+非齐次特解.齐次通解求法已介绍.问题归结为如何寻找递归关系的特解.对于寻找递归关系的特解,还没有一般方法.通常根据f(n)的组成形式,由观察法来决定特解.

当函数f(n)比较复杂时,用观察法来决定特解是相当困难的.

39当非齐次项是多项式时,可通过增加递归关系的阶,降低非齐次项的幂次,从而化成齐次递归关系求解.

下面通过一个例题来说明这种升阶法.例4.5

平面上有n条直线,任何两条直线不平行,且任何三条直线不交于一点,问共有多少个交点？解

令hn为n条直线的交点个数.第n条直线与前n-1条有n-1个交点,故有递归关系hn=hn-1+n-1,且h1=0,h2=1,h3=3.

40下面是通过增阶化为齐次的过程:hn=hn-1+n-1,(1)

hn-1=hn-2+n-2,

(2)(1)式-(2)式整理得:

hn-2hn-1+hn-2=1(3)

hn-1-2hn-2+hn-3=1

(4)(3)式-(4)式整理得:

hn-3hn-1+3hn-2-hn-3=0(5)41特征方程:

x3-3x2+3x-1=(x-1)3=0特征根:1(三重)齐次一般解:

hn=(c1+c2n+c3n2)1n由边界条件h1=0,h2=1,h3=3决定c1,c2,c3:42解之得到:

因此,该递归关系的解为43定理

设一阶非齐次递推方程

Hn+1+aHn=f(n)的自由项f(n)是n的m次多项式，则当a≠-1时，递推方程有一个n的m次特解f0(n)；当a=-