遞推方程與生成函數(shù)

遞推方程與生成函數(shù)1第一頁，共八十七頁，編輯于2023年，星期五13.1遞推方程的定義及實(shí)例定義13.1

設(shè)序列a0,a1,…,an,…,簡記為{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)=12第二頁，共八十七頁，編輯于2023年，星期五例1從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.遞推方程的實(shí)例:Hanoi塔3第三頁，共八十七頁，編輯于2023年，星期五兩個(gè)排序算法歸并算法Mergesort(A,p,r)//對A的下標(biāo)p到r之間數(shù)排序1.ifp<r2.thenq(p+r)/2//q為p到r的中點(diǎn)，3.Mergesort(A,p,q)4.Mergesort(A,q+1,r)5.Merge(A,p,q,r)//歸并排好序數(shù)組A[p..q]與A[q+1..r]插入排序算法INSERTION-SORT(A,n)1.forj

2ton

keyA[j]

ij–14whilei>0andA[i]>key5.doA[i+1]A[i];ii–17.A[i+1]key

4第四頁，共八十七頁，編輯于2023年，星期五遞推方程的實(shí)例:算法分析例2哪種排序算法在最壞情況下復(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)5第五頁，共八十七頁，編輯于2023年，星期五13.2遞推方程的公式解法特征方程、特征根遞推方程的解與特征根的關(guān)系無重根下通解的結(jié)構(gòu)求解實(shí)例有重根下通解的結(jié)構(gòu)求解實(shí)例6第六頁，共八十七頁，編輯于2023年，星期五其中a1,a2,…,ak為常數(shù)，ak

0稱為

k階常系數(shù)線性齊次遞推方程b0,b1,…,bk1為k個(gè)初值定義13.2

常系數(shù)線性齊次遞推方程的標(biāo)準(zhǔn)形：常系數(shù)線性齊次遞推方程實(shí)例：Fibonacci數(shù)列的遞推方程7第七頁，共八十七頁，編輯于2023年，星期五特征方程與特征根

定義13.3

特征方程

xk

a1xk1

…

ak

=0，特征方程的根稱為遞推方程的特征根實(shí)例：

遞推方程fn=fn1+fn2特征方程x2x1=0特征根8第八頁，共八十七頁，編輯于2023年，星期五遞推方程解與特征根的關(guān)系定理13.1設(shè)q是非零復(fù)數(shù)，則qn

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

qn是遞推方程的解

qna1qn1a2qn2…akqnk=0

qnk(qka1qk1a2qk2…ak)=0

qka1qk1a2qk2…ak=0（因?yàn)閝0）

q是它的特征根定理13.2設(shè)h1(n)和h2(n)是遞推方程的解，c1,c2為任意常數(shù),則c1h1(n)+c2h2(n)也是這個(gè)遞推方程的解.推論若q1,q2,…,qk

是遞推方程的特征根，則c1q1n

+c2q2n

+…+ckqkn是該遞推方程的解，其中c1,c2,…,ck

是任意常數(shù).9第九頁，共八十七頁，編輯于2023年，星期五無重根下通解的結(jié)構(gòu)定義13.4

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

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

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

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

H(n)=c1q1n+c2q2n+…+ckqkn為該遞推方程的通解.10第十頁，共八十七頁，編輯于2023年，星期五例3Fibonacci數(shù)列：

fn=fn1+fn2，特征根為

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

解是實(shí)例11第十一頁，共八十七頁，編輯于2023年，星期五有重根下求解中的問題例4解特征方程x24x+4=0

通解H(n)=c12n+c22n=c2n

代入初值得：

c無解.問題：兩個(gè)解線性相關(guān)12第十二頁，共八十七頁，編輯于2023年，星期五有重根下的通解結(jié)構(gòu)定理13.4設(shè)q1,q2,…,qt是遞推方程的不相等的特征根，且qi的重?cái)?shù)為ei，i=1,2,…,t，令那么通解13第十三頁，共八十七頁，編輯于2023年，星期五例5求解以下遞推方程其中待定常數(shù)滿足以下方程組

原方程的解為

解特征方程x4+x33x25x2=0,特征根1,1,1,2通解為求解實(shí)例14第十四頁，共八十七頁，編輯于2023年，星期五遞推方程的標(biāo)準(zhǔn)型通解結(jié)構(gòu)特解的求法多項(xiàng)式函數(shù)指數(shù)函數(shù)組合形式常系數(shù)線性非齊次遞推方程求解15第十五頁，共八十七頁，編輯于2023年，星期五證代入驗(yàn)證,H(n)是解.下面證明任意解h(n)為某個(gè)齊次解與特解H*(n)之和.設(shè)h(n)為遞推方程的解，則h(n)H*(n)是齊次解，即h(n)是一個(gè)齊次解與H*(n)之和.定理13.5

設(shè)是對應(yīng)齊次方程的通解，H*(n)是一個(gè)特解，則

是遞推方程的通解.

遞推方程的標(biāo)準(zhǔn)型及通解16第十六頁，共八十七頁，編輯于2023年，星期五解設(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)例6找出遞推方程an

2an1=2n2

的通解如果f(n)為n次多項(xiàng)式，則特解一般也是n次多項(xiàng)式特解的形式：多項(xiàng)式17第十七頁，共八十七頁，編輯于2023年，星期五例7Hanoi塔T(n)=2T(n1)+1

T(1)=1實(shí)例解令T*(n)=P代入方程

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

T(n)=c2n–1,代入初值得c=1,解為T(n)=2n–1.18第十八頁，共八十七頁，編輯于2023年，星期五例8求解關(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ù))19第十九頁，共八十七頁，編輯于2023年，星期五特解的形式:指數(shù)f(n)為指數(shù)函數(shù)n，若是e重特征根(e可以等于0)，則特解為Pnen,其中P為待定常數(shù).例9通信編碼問題解an=6an1+8n1,a1=7設(shè)a*n=P8n1,代入得P=4通解an=c6n+48n1

代入初值得an=(6n+8n)/2例10

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

20第二十頁，共八十七頁，編輯于2023年，星期五換元法迭代歸納法應(yīng)用實(shí)例13.3遞推方程的其他解法21第二十一頁，共八十七頁，編輯于2023年，星期五思想：通過換元轉(zhuǎn)化成常系數(shù)線性遞推方程

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

b0=4解得例11an>0換元法22第二十二頁，共八十七頁，編輯于2023年，星期五解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例12歸并排序換元法:實(shí)例23第二十三頁，共八十七頁，編輯于2023年，星期五迭代歸納法：歸并排序例1324第二十四頁，共八十七頁，編輯于2023年，星期五迭代歸納法：錯(cuò)位排列例14

Dn

=(n–1)(Dn–1+Dn–2)解：25第二十五頁，共八十七頁，編輯于2023年，星期五快速排序算法算法Quicksort(A,p,r)//p和r分別表示A首和末元素下標(biāo)1.ifp<r2.thenqPartition(A,p,r)//劃分為A[p..q1]和A[q+1..r]3.A[p]A[q]4.Quicksort(A,p,q1)5.Quicksort(A,q+1,r)26第二十六頁，共八十七頁，編輯于2023年，星期五劃分過程算法Partition(A,p,r)1.x

A[p]//選首元素作為劃分標(biāo)準(zhǔn)x2.i

p1

3.j

r+14.whiletrue5.dorepeatj

j16.untilA[j]<x//A[j]是從后找的第一個(gè)比x小元素7.repeati

i+18.untilA[i]>x//A[i]是從前找的第一個(gè)比x大的元素9.ifi<j//繼續(xù)搜索A[i]到A[j]之間的范圍10thenA[i]

A[j]//A[i]與A[j]交換，回到行411.elsereturnj//結(jié)束While循環(huán)27第二十七頁，共八十七頁，編輯于2023年，星期五實(shí)例

2799081364861671088

2590

i

j272508136486167108899

90

i

j

2725081310

86167

64

8899

90

ij

27

25081310

7

16

86

64

8899

90

ji

1625081310

727

8664

889990

28第二十八頁，共八十七頁，編輯于2023年，星期五平均情況時(shí)間復(fù)雜度分析遞推方程差消法化簡29第二十九頁，共八十七頁，編輯于2023年，星期五迭代求解30第三十頁，共八十七頁，編輯于2023年，星期五遞歸樹W(n)=n

k–(1+2+…+2k1)=nk–(2k–1)=nlogn–n+131第三十一頁，共八十七頁，編輯于2023年，星期五13.4生成函數(shù)及其應(yīng)用牛頓二項(xiàng)式系數(shù)與牛頓二項(xiàng)式定理生成函數(shù)的定義生成函數(shù)的應(yīng)用32第三十二頁，共八十七頁，編輯于2023年，星期五牛頓二項(xiàng)式系數(shù)定義13.5

設(shè)r為實(shí)數(shù)，n為整數(shù)，引入形式符號稱為牛頓二項(xiàng)式系數(shù).實(shí)例33第三十三頁，共八十七頁，編輯于2023年，星期五牛頓二項(xiàng)式定理定理13.6

（牛頓二項(xiàng)式定理）設(shè)為實(shí)數(shù)，則對一切實(shí)數(shù)x,y，|x/y|<1，有若=m，其中m為正整數(shù)，那么34第三十四頁，共八十七頁，編輯于2023年，星期五重要展開式令x=z，y=1，那么牛頓二項(xiàng)式定理就變成

在上面式子中用z代替z，則有

35第三十五頁，共八十七頁，編輯于2023年，星期五生成函數(shù)定義定義13.6

設(shè)序列{an}，構(gòu)造形式冪級數(shù)G(x)=a0+a1x+a2x2+…+an

xn+…稱G(x)為序列{an}的生成函數(shù).例如，{C(m,n)}的生成函數(shù)為(1+x)m給定正整數(shù)k,{kn}的生成函數(shù)為G(x)=1+kx+k2x2+k3x3+…=36第三十六頁，共八十七頁，編輯于2023年，星期五例14求序列{an}的生成函數(shù)(1)an=7·3n

(2)an=n(n+1)解由序列求生成函數(shù)37第三十七頁，共八十七頁，編輯于2023年，星期五由生成函數(shù)求序列通項(xiàng)例15已知{an}的生成函數(shù)為求an.解38第三十八頁，共八十七頁，編輯于2023年，星期五生成函數(shù)的應(yīng)用求解遞推方程計(jì)數(shù)多重集的r組合數(shù)不定方程的解整數(shù)拆分39第三十九頁，共八十七頁，編輯于2023年，星期五求解遞推方程例16

an–5an1+6an2=0，a0=1,a1=

2

G(x)=a0+a1x+a2x2+a3x3+…5xG(x)=5a0x5a1x25a2x3-…6x2

G(x)=+6a0x2+6a1x3+…(15x+6x2)G(x)=a0+(a15a0)x

40第四十頁，共八十七頁，編輯于2023年，星期五例17

解：設(shè){hn}的生成函數(shù)為

求解遞推方程41第四十一頁，共八十七頁，編輯于2023年，星期五求解遞推方程42第四十二頁，共八十七頁，編輯于2023年，星期五多重集的r組合數(shù)S={n1a1,n2a2,…,nkak}的r組合數(shù)就是不定方程

x1+x2+…+xk

=r

xi

nii=1,2,…,k的非負(fù)整數(shù)解的個(gè)數(shù)的展開式中yr的系數(shù)生成函數(shù)43第四十三頁，共八十七頁，編輯于2023年，星期五實(shí)例例18

S={3a,4b,5c}的10組合數(shù)解：生成函數(shù)G(y)=(1+y+y2+y3)(1+y+y2+y3+y4)(1+y+y2+y3+y4+y5)=(1+2y+3y2+4y3+4y4+3y5+2y6+y7)(1+y+y2+y3+y4+y5)=(1+…+3y10+2y10+y10+…)

N=6組合方案{a,a,a,b,b,b,b,c,c,c},{a,a,a,b,b,b,c,c,c,c},

{a,a,a,b,b,c,c,c,c,c},{a,a,b,b,b,b,c,c,c,c},

{a,a,b,b,b,c,c,c,c,c},{a,b,b,b,b,c,c,c,c,c}44第四十四頁，共八十七頁，編輯于2023年，星期五不定方程解的個(gè)數(shù)基本的不定方程

x1+x2+…+xk=r，xi為自然數(shù)

45第四十五頁，共八十七頁，編輯于2023年，星期五推廣的不定方程帶限制條件的不定方程x1+x2+…+xk

=r，li

xi

ni帶系數(shù)的不定方程

p1x1+p2x2+…+pkxk=r，xiN生成函數(shù)生成函數(shù)46第四十六頁，共八十七頁，編輯于2023年，星期五重量0123456789101112方案1121212121211實(shí)例例191克砝碼2個(gè)，2克砝碼1個(gè)，4克砝碼2個(gè)，問能稱出哪些重量，方案有多少？解：x1+2x2+4x3=r0

x12,0x21,0

x32

G(y)=(1+y+y2)(1+y2)(1+y4+y8)=1+y+2y2+y3+2y4+y5+2y6+y7+2y8+y9+2y10+y11+y1247第四十七頁，共八十七頁，編輯于2023年，星期五有序無序不重復(fù)4=44=1+34=3+14=44=1+3重復(fù)4=44=1+34=3+14=2+24=2+1+14=1+2+14=1+1+24=1+1+1+14=44=1+34=2+24=2+1+14=1+1+1+1拆分的定義：將給定正整數(shù)N表示成若干個(gè)正整數(shù)之和.正整數(shù)拆分48第四十八頁，共八十七頁，編輯于2023年，星期五無序拆分基本模型：將N無序拆分成正整數(shù)

a1,a2,…,an

a1x1+a2x2+…+anxn

=N

不允許重復(fù)

允許重復(fù)49第四十九頁，共八十七頁，編輯于2023年，星期五實(shí)例例20證明任何正整數(shù)都可以唯一表示成2進(jìn)制數(shù).對應(yīng)于將任何正整數(shù)N拆分成2的冪，20,21,22,23,…,且不允許重復(fù).對于所有的n,系數(shù)是1，這就證明唯一的表法.生成函數(shù)50第五十頁，共八十七頁，編輯于2023年，星期五解N允許重復(fù)無序拆分成k個(gè)數(shù)（kr）的方案

N允許重復(fù)無序拆分成正整數(shù)k（kr）的方案做下述Ferrers圖

將圖以y=x對角線翻轉(zhuǎn)180度，得到共軛的Ferrers圖.16=6+5+3+2（k4）對應(yīng)每個(gè)數(shù)不超過4的拆分:16=4+4+3+2+2+1這種拆分?jǐn)?shù)的生成函數(shù)為

無序拆分：個(gè)數(shù)限制大小k個(gè)數(shù)k例21給定r,求N允許重復(fù)無序拆分成k個(gè)數(shù)(kr)的方法數(shù)51第五十一頁，共八十七頁，編輯于2023年，星期五定理13.7將N允許重復(fù)地有序拆分成r個(gè)部分的方案數(shù)為C(N1,r1).證設(shè)N=a1+a2+…+ar是滿足條件的拆分，則令

r1個(gè)Si取值為1,2,…,N1，方法數(shù)為C(N1,r1).不允許重復(fù)有序拆分：不允許重復(fù)無序拆分+全排列有序拆分推論對N做任意重復(fù)的有序拆分，方案數(shù)為52第五十二頁，共八十七頁，編輯于2023年，星期五指數(shù)生成函數(shù)的定義與實(shí)例指數(shù)生成函數(shù)的應(yīng)用13.5指數(shù)生成函數(shù)及其應(yīng)用53第五十三頁，共八十七頁，編輯于2023年，星期五例22給定正整數(shù)m,an

=P(m,n),{an}的指數(shù)生成函數(shù)為

例23

bn=1,則{bn}的指數(shù)生成函數(shù)為定義13.7

設(shè){an}為序列，稱為{an}的指數(shù)生成函數(shù).指數(shù)生成函數(shù)的定義與實(shí)例54第五十四頁，共八十七頁，編輯于2023年，星期五應(yīng)用：多重集排列計(jì)數(shù)定理13.8設(shè)S={n1a1,n2a2,…,nkak}為多重集，則S的r排列數(shù)的指數(shù)生成函數(shù)為55第五十五頁，共八十七頁，編輯于2023年，星期五實(shí)例例24由1,2,3,4組成的五位數(shù)中，要求1出現(xiàn)不超過2次，但不能不出現(xiàn)，2出現(xiàn)不超過1次，3出現(xiàn)可達(dá)3次，4出現(xiàn)偶數(shù)次.求這樣的五位數(shù)個(gè)數(shù).

N=215解56第五十六頁，共八十七頁，編輯于2023年，星期五實(shí)例解設(shè)方案數(shù)為an

例25

紅、白、蘭涂色1n

的方格，要求偶數(shù)個(gè)為白色，問有多少方案？57第五十七頁，共八十七頁，編輯于2023年，星期五13.6Catalan數(shù)與Stirling數(shù)Catalan數(shù)第一類Stirling數(shù)第二類Stirling數(shù)58第五十八頁，共八十七頁，編輯于2023年，星期五Catalan數(shù)定義定義13.8一個(gè)凸n+1邊形，通過不相交于n+1

邊形內(nèi)部的對角線把n+1

邊形劃分成三角形，劃分方案個(gè)數(shù)記作hn，稱為Catalan數(shù).

實(shí)例：h4=5初值h2=159第五十九頁，共八十七頁，編輯于2023年，星期五考慮n+1條邊的多邊形，端點(diǎn)A1,An+1的邊記為a,對于任意的k=1,2,…,n1，以Ak+1A1為邊，An+1Ak+1為另一邊，與a構(gòu)成三角形T,T將多邊形劃分成R1和R2兩個(gè)部分，分別為k+1邊形和nk+1邊形.

遞推方程Catalan數(shù)的遞推方程解：60第六十頁，共八十七頁，編輯于2023年，星期五

實(shí)例：計(jì)數(shù)堆棧的輸出個(gè)數(shù)例261,2,…,n放入堆棧后的不同的輸出個(gè)數(shù)

解在1進(jìn)棧到出棧之間作為一個(gè)子問題，1出棧后作為一個(gè)子問題.過程如下：步2：子問題規(guī)模k，步4：子問題規(guī)模nk1

1．1進(jìn)棧；2．處理k個(gè)數(shù)（2,…,k+1）的進(jìn)棧問題；3．1出棧；4．處理k+2,…,n的進(jìn)棧問題；

61第六十一頁，共八十七頁，編輯于2023年，星期五求解遞推方程62第六十二頁，共八十七頁，編輯于2023年，星期五第一類Stirling數(shù)將xr

系數(shù)的絕對值Sr

記作，稱為第一類Stirling數(shù)定義13.9

多項(xiàng)式x(x1)(x2)…(xn+1)的展開式為

Snxn

Sn1xn1+Sn2xn2…+(1)n1S1x

實(shí)例

x(x1)=x2x

x(x1)(x2)=x33x2+2x

63第六十三頁，共八十七頁，編輯于2023年，星期五第一類Stirling數(shù)的遞推方程64第六十四頁，共八十七頁，編輯于2023年，星期五第一類Stirling數(shù)的恒等式65第六十五頁，共八十七頁，編輯于2023年，星期五第二類Stirling數(shù)定義定義13.10

n個(gè)不同的球恰好放到r個(gè)相同的盒子里的方法數(shù)稱為第二類Stirling數(shù)，記作實(shí)例具體方案如下：a,b,c|da,c,d|ba,b,d|cb,c,d|aa,b|c,da,c|b,da,d|b,c66第六十六頁，共八十七頁，編輯于2023年，星期五第二類Stirling數(shù)遞推方程證明：取球a1，a1單獨(dú)放一個(gè)盒子，a1不單獨(dú)放一個(gè)盒子，先放n1個(gè)球到r個(gè)盒子，插入a1有r種方法，111111761115251031n=1n=2n=3n=4n=5r=1r=2r=3r=4r=5遞推方程67第六十七頁，共八十七頁，編輯于2023年，星期五第二類Stirling數(shù)恒等式68第六十八頁，共八十七頁，編輯于2023年，星期五恒等式證明1.a1先放在一個(gè)盒子里，剩下的n1個(gè)球每個(gè)有2種選擇，但是全落入a1的盒子的方法不符合要求.n個(gè)球放到n1個(gè)盒子，必有一個(gè)盒子含2個(gè)球，其余每個(gè)盒子1個(gè)球.選擇兩個(gè)球有C(n,2)種方法.69第六十九頁，共八十七頁，編輯于2023年，星期五恒等式證明對應(yīng)n個(gè)不同的球恰好放到m個(gè)不同盒子的方法數(shù)（無空盒）按照含球的盒子數(shù)k分類，對應(yīng)了允許存在空盒的方法至多n個(gè)不同的球放到r1個(gè)相同的盒子不存在空盒的方法按照球數(shù)分類70第七十頁，共八十七頁，編輯于2023年，星期五放球問題的計(jì)數(shù)球標(biāo)號盒標(biāo)號允空盒放球方法數(shù)對應(yīng)的組合問題否否否Pm(n)Pm1(n)將n恰好無序拆分成m部分否否是Pm(n)將n無序拆分成t個(gè)部分(tm)否是否C(n1,m1)x1+x2+…+xm=n正整數(shù)解否是是C(n+m1,n)x1+x2+…+xm=n非負(fù)整數(shù)解是否否第二類Stirling數(shù)是否是第二類Sirling數(shù)性質(zhì)是是否第二類Stirling數(shù)性質(zhì)是是是乘法法則71第七十一頁，共八十七頁，編輯于2023年，星期五第十三章習(xí)題課主要內(nèi)容遞推方程的求解方法：公式法、換元法、迭代歸納法、生成函數(shù)法遞推方程與遞歸算法生成函數(shù)的應(yīng)用：計(jì)算多重集的r組合數(shù)、確定不定方程的整數(shù)解個(gè)數(shù)、計(jì)算拆分方案數(shù)、求解遞推方程指數(shù)生成函數(shù)的應(yīng)用：計(jì)算多重集的r排列數(shù)常用的計(jì)數(shù)符號：組合數(shù)、排列數(shù)、多項(xiàng)式系數(shù)、錯(cuò)位排列數(shù)、Fibonacci數(shù)、Catalan數(shù)、兩類Stirling數(shù)基本計(jì)數(shù)模型：選取問題、不定方程的解、非降路徑、正整數(shù)拆分、放球等72第七十二頁，共八十七頁，編輯于2023年，星期五基本要求能夠使用遞推方程求解計(jì)數(shù)問題能夠使用生成函數(shù)或指數(shù)生成函數(shù)求解計(jì)數(shù)問題掌握Fibonacci數(shù)、Catalan數(shù)、兩類Stirling數(shù)的定義、組合意義以及相關(guān)的公式.73第七十三頁，共八十七頁，編輯于2023年，星期五練習(xí)1已知a0=0,a1=1,a2=4,a3=12滿足遞推方程

an+c1an1+c2an2=0，求c1和c2.解得c1=4,c2=4.代入a0,a1,a2,a3的值得到根據(jù)已知條件得到74第七十四頁，共八十七頁，編輯于2023年，星期五練習(xí)22．求解遞推方程.用換元法.令bn=nan,代入原遞推方程得

用公式法解得從而得到75第七十五頁，共八十七頁，編輯于2023年，星期五練習(xí)33．確定序列{an}的生成函數(shù)，其中an=76第七十六頁，共八十七頁，編輯于2023年，星期五練習(xí)377第七十七頁，共八十七頁，編輯于2023年，星期五練習(xí)44．已知是序列{an}的生成函數(shù)，求an.解得A=1/4,B=3/4,C=1/4,從而得到78第七十八頁，共八十七頁，編輯于2023年，星期五練習(xí)479第七十九頁，共八十七頁，編輯于2023年，星期五練習(xí)55．求下列n階行列式的值dn.解得dn=n+1.方程80第八十頁，共八十七頁，編輯于2023年，