離散數(shù)學(xué)-.遞推方程與生成函數(shù)

離散數(shù)學(xué)--.遞推方程與生成函數(shù)1第一頁(yè)，共四十一頁(yè)，2022年，8月28日第10章遞推方程與生成函數(shù)10.1遞推方程及其應(yīng)用10.2生成函數(shù)及其應(yīng)用10.3指數(shù)生成函數(shù)及其應(yīng)用10.4Catalan數(shù)與Stirling數(shù)2第二頁(yè)，共四十一頁(yè)，2022年，8月28日10.1遞推方程及其應(yīng)用10.1.1遞推方程的定義及實(shí)例10.1.2常系數(shù)線性齊次遞推方程的求解10.1.3常系數(shù)線性非齊次遞推方程的求解10.1.4遞推方程的其他解法10.1.5遞推方程與遞歸算法3第三頁(yè)，共四十一頁(yè)，2022年，8月28日遞推方程的定義定義10.1設(shè)序列a0,a1,…,an,…,簡(jiǎn)記為{an}.一個(gè)把a(bǔ)n與某些個(gè)ai(i<n)聯(lián)系起來的等式叫做關(guān)于序列{an}的遞推方程.當(dāng)給定遞推方程和適當(dāng)?shù)某踔稻臀ㄒ淮_定了序列.

例如，

Fibonacci數(shù)列：1，1，2，3，5，8，…，記作{fn}.

遞推方程fn

=fn1+fn2

初值

f0=1，f1=1

階乘計(jì)算數(shù)列：1，2，6，24，5！，…,記作{F(n)}

遞推方程F(n)=nF(n1)

初值F(1)=14第四頁(yè)，共四十一頁(yè)，2022年，8月28日化簡(jiǎn)得

an=6an1+8n1,

可以解得

an=(6n+8n)/2遞推方程的實(shí)例——計(jì)數(shù)編碼例1

一個(gè)編碼系統(tǒng)用八進(jìn)制數(shù)字對(duì)信息編碼，一個(gè)碼是有效的當(dāng)且僅當(dāng)含有偶數(shù)個(gè)7,求n位長(zhǎng)的有效碼字有多少個(gè)？解設(shè)所求有效碼字為an個(gè).分類處理、分步處理得到遞推方程和初值如下：

an=7an1+8n1

an1

a1=7

5第五頁(yè)，共四十一頁(yè)，2022年，8月28日遞推方程的實(shí)例——Hanoi塔例2

從A柱將這些圓盤移到C柱上去.如果把一個(gè)圓盤從一個(gè)柱子移到另一個(gè)柱子稱作一次移動(dòng)，在移動(dòng)和放置時(shí)允許使用B柱，但不允許大圓盤放到小圓盤的上面.問把所有的圓盤的從A移到C總計(jì)需要多少次移動(dòng)？初值是

T(1)=1可證明解是

T(n)=2n1移動(dòng)n個(gè)盤子的總次數(shù)為T(n).因此得到遞推方程

T(n)=2T(n1)+1.6第六頁(yè)，共四十一頁(yè)，2022年，8月28日遞推方程的實(shí)例——算法分析例3

哪種排序算法在最壞情況下復(fù)雜度比較低？

插入排序，歸并排序

插入排序

W(n)=W(n

1)+n1

W(1)=0解得W(n)=O(n2).歸并排序，不妨設(shè)n=2k.

W(n)=2W(n/2)+n－1

W(1)=0解得W(n)=O(nlogn)7第七頁(yè)，共四十一頁(yè)，2022年，8月28日常系數(shù)線性齊次遞推方程求解其中a1,a2,…,ak為常數(shù)，ak

0稱為

k

階常系數(shù)線性齊次遞推方程

b0,b1,…,bk1為

k個(gè)初值實(shí)例：Fibonacci數(shù)列的遞推方程定義10.2

常系數(shù)線性齊次遞推方程的標(biāo)準(zhǔn)形：8第八頁(yè)，共四十一頁(yè)，2022年，8月28日常系數(shù)線性齊次遞推方程

的公式解法特征方程、特征根遞推方程的解與特征根的關(guān)系解的線性性質(zhì)無重根下通解的結(jié)構(gòu)求解實(shí)例有重根下通解的結(jié)構(gòu)求解實(shí)例9第九頁(yè)，共四十一頁(yè)，2022年，8月28日特征方程與特征根

定義10.3特征方程

xk

a1xk1

…

ak

=0，特征方程的根稱為遞推方程的特征根

實(shí)例：遞推方程fn=fn1+fn2

特征方程x2x1=0特征根10第十頁(yè)，共四十一頁(yè)，2022年，8月28日遞推方程解與特征根的關(guān)系定理10.1

設(shè)q是非零復(fù)數(shù)，則qn

是遞推方程的解當(dāng)且僅當(dāng)q是它的特征根.證

qn是遞推方程的解?qna1qn1a2qn2

…akqnk

=0

?

qnk

(qk

a1qk1

a2qk2

…ak

)=0

?

qk

a1qk1

a2qk2

…ak=0?q是它的特征根注：這里遞推方程指常系數(shù)線性齊次遞推方程11第十一頁(yè)，共四十一頁(yè)，2022年，8月28日解的線性性質(zhì)定理10.2

設(shè)h1(n)和h2(n)是遞推方程的解，c1,c2為任意常數(shù)，則c1h1(n)+c2h2(n)也是這個(gè)遞推方程的解.證將c1h1(n)+c2h2(n)代入該遞推方程進(jìn)行驗(yàn)證.推論若q1,q2,…,qk

是遞推方程的特征根，則

c1q1n+c2q2n+…+ckqkn是該遞推方程的解，其中c1,c2,…,ck是任意常數(shù).注：這里的遞推方程指的是常系數(shù)線性齊次遞推方程12第十二頁(yè)，共四十一頁(yè)，2022年，8月28日無重根下通解的結(jié)構(gòu)定義10.4

若對(duì)常系數(shù)線性齊次遞推方程的每個(gè)解h(n)都存在一組常數(shù)c1,c2,…,ck使得

h(n)=c1q1n+c2q2n+…+ckqkn

成立，則稱c1q1n+c2q2n+…+ckqkn為該遞推方程的通解

定理10.3

設(shè)q1,q2,…,qk是常系數(shù)線性齊次遞推方程不等的特征根，則

H(n)=c1q1n+c2q2n+…+ckqkn為該遞推方程的通解.13第十三頁(yè)，共四十一頁(yè)，2022年，8月28日定理的證明證：H(n)是解.設(shè)h(n)是遞推方程的任意解，h(0),h(1),…,h(k1)由初值b0,b1,…,bk1唯一確定.代入方程得到方程組系數(shù)行列式

當(dāng)qi

qj時(shí)，方程組有唯一解14第十四頁(yè)，共四十一頁(yè)，2022年，8月28日求解實(shí)例例4Fibonacci數(shù)列：

fn=fn1+fn2，特征根為

通解為代入初值f0=1,f1=1,得解得

解是15第十五頁(yè)，共四十一頁(yè)，2022年，8月28日有重根下求解中的問題例5解特征方程

x24x+4=0

通解

H(n)=c12n+c22n=c2n

代入初值得：

c無解.問題：兩個(gè)解線性相關(guān)16第十六頁(yè)，共四十一頁(yè)，2022年，8月28日有重根下的通解結(jié)構(gòu)定理10.4

設(shè)q1,q2,…,qt是遞推方程的不相等的特征根，且qi的重?cái)?shù)為ei，i=1,2,…,t，令那么通解17第十七頁(yè)，共四十一頁(yè)，2022年，8月28日求解實(shí)例例6

求解以下遞推方程其中待定常數(shù)滿足以下方程組

原方程的解為

解特征方程x4+x33x25x2=0,特征根21,1,2通解為18第十八頁(yè)，共四十一頁(yè)，2022年，8月28日常系數(shù)線性非齊次遞推方程求解遞推方程的標(biāo)準(zhǔn)型通解結(jié)構(gòu)特解的求法多項(xiàng)式函數(shù)指數(shù)函數(shù)組合形式19第十九頁(yè)，共四十一頁(yè)，2022年，8月28日遞推方程的標(biāo)準(zhǔn)型及通解證代入驗(yàn)證,H(n)是解.下面證明任意解h(n)為某個(gè)齊次解與特解H*(n)之和.設(shè)h(n)為遞推方程的解，則h(n)H*(n)是齊次解，即h(n)是一個(gè)齊次解與H*(n)之和.定理10.5設(shè)是對(duì)應(yīng)齊次方程的通解，H*(n)是一個(gè)特解，則

是遞推方程的通解.

20第二十頁(yè)，共四十一頁(yè)，2022年，8月28日特解的形式——多項(xiàng)式解設(shè)an*=P1n2+P2n

+P3,代入遞推方程得

P1n2+P2n

+P32[P1(n1)2+P2(n1)+P3]=2n2整理得P1n2+(4P1P2)n+(2P1+2P2P3)=2n2

解得P1=2,P2=8,P3=12，原方程的通解為an=c2n2(n2+4n+6)例7

找出遞推方程an

2an1=2n2

的通解如果f(n)為n次多項(xiàng)式，則特解一般也是n次多項(xiàng)式21第二十一頁(yè)，共四十一頁(yè)，2022年，8月28日實(shí)例例8Hanoi塔

T(n)=2T(n1)+1

T(1)=1解令T*(n)=P代入方程

P=2P+1解得P=–1

T(n)=c2n–1,代入初值得c=1,解為T(n)=2n–1.22第二十二頁(yè)，共四十一頁(yè)，2022年，8月28日例9

求解關(guān)于順序插入排序算法的遞推方程解設(shè)特解為W*(n)=P1n+P2，代入遞推方程，得

P1n+P2(P1(n1)+P2)=n1無解.設(shè)特解W*(n)=P1n2+P2n,代入遞推方程得

(P1n2+P2n)(P1(n1)2+P2(n1))=n1解得

P1=1/2,P2=1/2.通解為

W(n)=c1n+n(n1)/2=c+n(n1)/2代入初值W(1)=0，得到W(n)=n(n1)/2=O(n2).實(shí)例(續(xù))23第二十三頁(yè)，共四十一頁(yè)，2022年，8月28日特解的形式——指數(shù)f(n)為指數(shù)函數(shù)

n，若

不是特征根，則特解為

H*(n)=P

n

其中P為待定常數(shù).例10

通信編碼問題解an=6an1+8n1,a1=7設(shè)

a*n=P8n1,代入得

P=4通解an=c6n+48n1

代入初值得

an=(6n+8n)/224第二十四頁(yè)，共四十一頁(yè)，2022年，8月28日特解的形式——指數(shù)(續(xù))若是e重特征根，則特解為Pne

n

例11

H(n)–5H(n–1)+6H(n–2)=2n，解令H*(n)=Pn2n

代入得

Pn2n–5P(n–1)2n–1+6P(n–2)2n–2=2n

解得P=–

2特解

H*(n)=–

n2n+1

25第二十五頁(yè)，共四十一頁(yè)，2022年，8月28日特解的組合形式例12

an–

2an–1=n+3n

a0=0解設(shè)特解為

an*=P1n+P2+P33n代入原方程得

(P1n+P2+P33n)–2[P1(n–1)+P2+P33n–1]=n+3n解得P1=–

1,P2=–2,P3=3通解an=c2n–n

–

2+3n+1

代入初值得c=–1，

an=–2n–n–2+3n+126第二十六頁(yè)，共四十一頁(yè)，2022年，8月28日換元法迭代歸納法——遞歸樹差消法嘗試法應(yīng)用實(shí)例

遞推方程的其他解法27第二十七頁(yè)，共四十一頁(yè)，2022年，8月28日換元法思想：通過換元轉(zhuǎn)化成常系數(shù)線性遞推方程

解令代入得bn=2bn–1+1，

b0=4解得例13an>028第二十八頁(yè)，共四十一頁(yè)，2022年，8月28日實(shí)例解

H(k)=2H(k–1)+2k–1

H(1)=1令H*(k)=P1k2k+P2,解得P1=P2=1

H*(k)=k2k+1通解H(k)=c2k+k2k+1代入初值得c=–1

H(k)=–2k+k2k+1

W(n)=nlogn–n+1例14

歸并排序29第二十九頁(yè)，共四十一頁(yè)，2022年，8月28日迭代歸納法——?dú)w并排序例1530第三十頁(yè)，共四十一頁(yè)，2022年，8月28日迭代歸納法——錯(cuò)位排列例16

Dn

=(n–1)(Dn–1+Dn–2)解：31第三十一頁(yè)，共四十一頁(yè)，2022年，8月28日差消法——化簡(jiǎn)遞推方程例1732第三十二頁(yè)，共四十一頁(yè)，2022年，8月28日積分近似33第三十三頁(yè)，共四十一頁(yè)，2022年，8月28日遞歸樹——二分歸并排序T(n)n-1T(n/2)T(n/2)n/2-1n/2-1T(n/4)T(n/4)T(n/4)T(n/4)n/4-1n/4-1n/4-1n/4-1

……….1111111……111111111T(n)=nk–(1+2+…+2k1)=nk–(2k–1)=nlogn–n+1n1n2n4...n2k1k層34第三十四頁(yè)，共四十一頁(yè)，2022年，8月28日(1)T(n)=C,左邊=O(1)嘗試法例18

(2)T(n)=cn,左邊=cn,35第三十五頁(yè)，共四十一頁(yè)，2022年，8月28日嘗試法(續(xù))(3)T(n)=cn2,左邊=cn2(4)T(n)=cnlogn,左邊=cnlogn

36第三十六頁(yè)，共四十一頁(yè)，2022年，8月28日積分近似37第三十七頁(yè)，共四十一頁(yè)，2022年，8月28日分治策略與遞歸算法n為輸入規(guī)模，n/b為子問題輸入規(guī)模，a為子問題個(gè)數(shù)，d(n)為分解及綜合的代價(jià)38第三十八頁(yè)，共四十一頁(yè)，2022年，8月28日分治策略與遞歸算法(續(xù))(1)d(n)=c