組合數(shù)學課件4常系數(shù)遞歸關系

1《圖論與組合優(yōu)化》第五講

常系數(shù)遞歸關系2第四講:

常系數(shù)遞歸關系I

.常系數(shù)齊次遞歸關系

(1)

特征值為不同的實數(shù)

(2)

特征值均為實數(shù)但是有重根(3)

特征值有復根*

II.常系數(shù)非齊次遞歸關系*3I.常系數(shù)齊次線性遞歸關系常系數(shù)線性遞歸關系有齊次和非齊次兩種.設Hn是一個遞歸數(shù)列.常系數(shù)齊次遞歸關系:其中

是實常數(shù),f(n)非零.

常系數(shù)非齊次遞歸關系: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個待定常數(shù),這些常數(shù)可由序列中相鄰的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為常數(shù)。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)的特征方程.特征方程的根叫原遞歸關系的特征根(值).下面我們根據(jù)特征根的情況來給出相應的解法.

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)中定義的數(shù)列滿足定理4.1中的遞歸關系(4.1).

從而證明了對任意參數(shù)c1,c2,…,cr而言(4.3)都是定理中遞歸關系的一個解.16(2)下面證明任何一個解都可以表示成(4.3)的形式.對任意一個解hn來說,它由邊界條件h0=b0,h1=b1,…,

hr-1=br-1完全確定.由(1)我們知道(4.3)定義的數(shù)列都滿足定理中的遞歸關系.我們需要證明由這些邊界條件可以完全決定一般解(4.3)中的參數(shù)c1,c2,…,cr.17我們使用待定系數(shù)法來證明c1,c2,…,cr存在性.根據(jù)需要可以得到聯(lián)立方程組這個方程組的系數(shù)矩陣的行列式在著名的Vandermonde行列式.18因為所有的特征值q1,q2,…,qr都不相同,所以這個行列式不為零.于是原方程組關于c1,c2,…,cr有唯一解.說明在這種條件下(4.1)的解是唯一確定的.

19例4.1

Fibonacci數(shù)列的遞歸關系:

Fn=Fn-1+Fn-2,F0=F1=1(4.4)可以利用特征值的方式來求解這個遞歸關系.解

該遞歸關系的特征方程為x2-x-1=0,其特征根為20可設該數(shù)列的解為:

由邊界條件得到方程組21解這個方程組得到:

所以,該遞歸數(shù)列的解為例4.2

求解遞歸關系22解

該遞歸關系所對應的特征方程:設遞歸關系:特征根:由邊界條件確定常數(shù)c1,c2,c3.

需要解下列線性方程組:23解之可得:通解為:例4.3

在信道上傳輸僅用3個字母a,b,c組成并且長度為n的詞.規(guī)定連續(xù)出現(xiàn)兩個a的詞不能傳輸.試確定這個信道允許傳輸?shù)脑~的個數(shù).解

令h(n)為允許傳輸長度為n的詞總數(shù),n=1,2,….

直接計算知,h(1)=3,h(2)=8.24設n≥3,第一個字母是b或c的詞數(shù)均為h(n-1);

第一個字母是a的詞,第二個字母必須是b或c,這種詞的數(shù)目為2h(n-2).故有以下遞歸關系:

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

該遞歸關系的特征方程為25

其特征根為：

故一般解為:由邊界條件h(1)=3,h(2)=8

解方程組：262.特征根有重根的情況

對于這種情況,我們只通過例題說明求解方法,最后給出一般結(jié)論,不詳細推導.例4.4

求解遞歸關系:解

特征方程:可見3是二重特征根.此時,除了Hn=3n這個解之外,還有一個解:

Hn=n3n.27一般解可設為:

利用邊界條件得到線性方程組并求解:28定理4.2

設q1,q2,…,qt是遞歸關系

全部不同特根,qi的重數(shù)為ei(i=1,2,…,t),

則該遞歸關系對應于qi部分的一般解是:293.僅有兩個有復特征根*當特征方程有復數(shù)根時,因為復數(shù)根總是成對出現(xiàn)的,而且任意復數(shù)a+bi都可以寫成ceid的形式,故可設兩個復根分別為30

此時這兩個根對應的一般解部分為:

因此這部分解也可以設為:

其中A,B為待定參數(shù),可利用邊界條

件得到.31例4.5

給定邊界條件a1=1,a2=0,求解遞歸關系:解

該遞歸關系對應的特征方程為:其特征根為:32所以其中該遞歸關系的一般解可設為:33由邊界條件a1=1,a2=0,

便可決定A和B,這只需要解下列方程組:34例

有n枚相同的棋子，甲、乙兩人輪流取子，每次可取1至2枚，取完為止。求首尾兩次都是甲取子的取法種數(shù)Hn.解：遞推方程為其中規(guī)定其特征方程為354個特征根為所以，通解為其中c1,c2,b1,b2為待定常數(shù)36把初始條件代人通解，得方程組解得37II.常系數(shù)線性非齊次遞歸關系*

線性非齊次遞歸關系:這里,a1,…,

ar全部是常數(shù).例如:都是常系數(shù)線性非齊次遞歸關系.38常系數(shù)線性非齊次遞歸關系的求解方法與非齊次線性方程組的求解思路類似.非齊次通解=齊次通解+非齊次特解.齊次通解求法已介紹.問題歸結(jié)為如何尋找遞歸關系的特解.對于尋找遞歸關系的特解,還沒有一般方法.通常根據(jù)f(n)的組成形式,由觀察法來決定特解.

當函數(shù)f(n)比較復雜時,用觀察法來決定特解是相當困難的.

39當非齊次項是多項式時,可通過增加遞歸關系的階,降低非齊次項的冪次,從而化成齊次遞歸關系求解.

下面通過一個例題來說明這種升階法.例4.5

平面上有n條直線,任何兩條直線不平行,且任何三條直線不交于一點,問共有多少個交點？解

令hn為n條直線的交點個數(shù).第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=-