離散數(shù)學(xué)及其應(yīng)用-第2版 課件 第7章高級(jí)計(jì)數(shù)技術(shù)

第7章

高級(jí)計(jì)數(shù)技術(shù)第7章高級(jí)計(jì)數(shù)技術(shù)7.1遞推方程7.2生成函數(shù)7.1遞推方程定義7.1.1設(shè)序列

簡(jiǎn)記為

。序列

的遞推方程是一個(gè)把

an用序列中在an

前面的一項(xiàng)或多項(xiàng)

ai(i<n)來(lái)表示的等式稱(chēng)作關(guān)于序列{an}的遞推方程。例題例7.2.113世紀(jì)意大利數(shù)學(xué)家斐波那契（Fibonacci）提出了一個(gè)有趣的兔子繁殖問(wèn)題：在一個(gè)島上放了一對(duì)剛出生的兔子，其中一只公兔，一只母兔。經(jīng)過(guò)兩個(gè)月長(zhǎng)成，長(zhǎng)成后即可生育，假定每對(duì)兔子每個(gè)月都可以生出一對(duì)小兔，且新生的小兔也是一只公兔和一只母兔。如果兔子不會(huì)死去，也不會(huì)被運(yùn)走，問(wèn)12個(gè)月時(shí)島上有多少對(duì)兔子?例題（續(xù)）解用

表示第

個(gè)月初的兔子對(duì)數(shù)，n是正整數(shù)。那么

f1=1（最初的兔子對(duì)數(shù)，第1個(gè)月的兔子對(duì)數(shù)）

f2=1（第2個(gè)月的兔子對(duì)數(shù)）f3=1+1=2（最初的一對(duì)加上它們的后代）

f4=2+1=3（第3個(gè)月的2對(duì)加上最初的一對(duì)的后代）f5=3+2=5（第4個(gè)月的3對(duì)加上第3個(gè)月2對(duì)的后代）

f6=5+3=8（第5個(gè)月的5對(duì)加上第4個(gè)月3對(duì)的后代）

f12=89+55=144（第11個(gè)月的89對(duì)加上第10個(gè)月55對(duì)的后代）12個(gè)月時(shí)島上共有兔子144對(duì)。一般的，斐波那契數(shù)列滿(mǎn)足下列遞推方程數(shù)列

稱(chēng)作斐波那契數(shù)列，其中的每一個(gè)數(shù)也稱(chēng)作斐波那契數(shù)。例題在股票投資中，復(fù)合利息的作用是強(qiáng)大的?！肮缮瘛蔽謧悺ぐ头铺?Warren

Buffett)據(jù)說(shuō)就是以年平均30%的復(fù)利戰(zhàn)勝市場(chǎng)，從而成為舉世矚目的價(jià)值投資大師。假設(shè)他的初始投資為10000美元，年投資收益的復(fù)利是30%，那么在30年后賬上的總資產(chǎn)有多少錢(qián)？解

令Pn表示n年后的總資產(chǎn)錢(qián)數(shù)。因?yàn)閚年后賬上的資產(chǎn)總額等于n-1年賬上的資產(chǎn)加上第n年的投資收益，容易知道序列{Pn}滿(mǎn)足遞推關(guān)系例題（續(xù)）初始條件是P0=10000，我們可以知道代入初始條件，得將n=30代入，

26199956.44美元。常系數(shù)線性齊次遞推方程的求解定義7.2.1設(shè)遞推方程滿(mǎn)足其中

為常數(shù),,這個(gè)方程稱(chēng)為k階常系數(shù)線性遞推方程。

為k個(gè)初值。當(dāng)

時(shí)，即稱(chēng)這個(gè)遞推方程為齊次方程。

常系數(shù)線性齊次遞推方程的求解定義7.2.2給定常系數(shù)線性齊次遞推方程如下：（7.2）,求解該方程的基本方法是找到形如G(n)=rn的解，其中r是常數(shù)，即

等式兩邊同時(shí)除以rn-k，得

因此我們將形如方程

稱(chēng)為該遞推方程的特征方程，特征方程的根r稱(chēng)為遞推方程的特征根。定理定理7.2.1設(shè)g1(n)和g2(n)是遞推方程(7.2)的兩個(gè)解，c1,c2為任意常數(shù)，則c1g1(n)+c2

g2(n)也是這個(gè)遞推方程的解。證明

將

g1(n)和g2(n)代入到方程(7.2)得，因此c1g1(n)+c2

g2(n)也是這個(gè)遞推方程的解。

推論

若

是遞推方程(7.2)的特征根，則

也是該遞推方程的解，其中

是任意常數(shù)。以上推論說(shuō)明

是遞推方程的解。那么，除了這種形式的解以外，是否存在其他形式的解?為了解決這個(gè)問(wèn)題，先定義通解。定義7.2.3能夠表示遞推方程（7.2）的每個(gè)解

的表達(dá)式稱(chēng)為該遞推方程的通解。定理定理7.2.2設(shè)

是遞推方程(7.2)不等的特征根，則

為該遞推方程的通解，其中

是任意常數(shù)。證明

此定理是推廣了定理7.2.1，證明類(lèi)似。例題例7.2.1求下面遞推方程的解：其中

，

。解遞推方程的特征方程是

，它的根是2和-1。因此，遞推方程的通解為c1,c2是常數(shù)。將初值

代入得解得,從而得到遞推方程的解為，

定理定理7.2.3設(shè)

是遞推方程（7.2）的不相等的特征根，且

ri的重?cái)?shù)為ei，其中

那么該遞推方程的通解是其中

為常數(shù)。

例題例7.2.4求解以下遞推方程解

特征方程

為即

特征根是2，其重?cái)?shù)是3，根據(jù)定理7.2.3

通解為代入初始條件，則有以下方程組解得

原方程的解為例題（續(xù)）解得

原方程的解為常系數(shù)線性非齊次遞推方程的求解常系數(shù)線性非齊次遞推方程的標(biāo)準(zhǔn)形是

（7.3）其中

f(n)是只依賴(lài)于n的函數(shù)。將

稱(chēng)作相伴的線性齊次遞推方程。定理7.2.4設(shè)

是對(duì)應(yīng)的相伴的線性齊次遞推方程的通解，

是方程（7.3）的一個(gè)特解，則是遞推方程（7.3）的通解。例題例7.2.5找出下述遞推方程的通解：解

該方程對(duì)應(yīng)相伴的線性齊次遞推方程是

它的通解是c3n，其中c是常數(shù)。設(shè)特解

，其中c1,c2

是常數(shù)。代入遞推方程得例題（續(xù)）整理得從而得線性方程組解得

因此

是一個(gè)特解，根據(jù)定理7.2.4，原方程的通解為初始條件

帶入通解得,因此得原方程的通解為7.2生成函數(shù)生成函數(shù)是研究組合計(jì)數(shù)中的一個(gè)重要工具，其基本思想是把要計(jì)數(shù)或研究的離散數(shù)列同多項(xiàng)式或冪級(jí)數(shù)的系數(shù)一一對(duì)應(yīng)起來(lái)，從而可以用數(shù)學(xué)分析的方法去研究這一數(shù)列，給出數(shù)列的一個(gè)顯示解或漸近解。牛頓二項(xiàng)式系數(shù)與牛頓二項(xiàng)式定理定義7.3.1設(shè)r為實(shí)數(shù)，n為整數(shù)，引入形式符號(hào)稱(chēng)為牛頓二項(xiàng)式系數(shù)．定理定理7.3.1牛頓二項(xiàng)式定理．

設(shè)r為實(shí)數(shù)，則對(duì)一切實(shí)數(shù)

，有其中

生成函數(shù)的定義及其性質(zhì)定義7.3.2設(shè)序列

，構(gòu)造形式冪級(jí)數(shù)

稱(chēng)f(x)為序列

的生成函數(shù)。

定義7.3.2給出的生成函數(shù)有時(shí)叫做

的普通生成函數(shù)，以和這個(gè)序列的其他類(lèi)型的生成函數(shù)相區(qū)別，序列

叫做f(x)的生成序列。例題例7.3.1設(shè)m是正整數(shù)，令ak=C(m,k)k=0,1,…m，

。那么序列{ak}的生成函數(shù)是什么？解這個(gè)序列的生成函數(shù)是由二項(xiàng)式定理可得

生成函數(shù)的性質(zhì)設(shè)

是已知序列，它們的生成函數(shù)分別為若

為常數(shù)，則

若

，則

若

，則

若

生成函數(shù)的性質(zhì)(續(xù)）(5)若

，則

(6)若

，則(7)若

，且

收斂，則

(8)若

為常數(shù)，則

(9)若

，則

，其中

為A(x)的導(dǎo)數(shù)。(10)若

，則

例題生成函數(shù)與序列是一一對(duì)應(yīng)的。例7.3.2求序列{an}的生成函數(shù)

解

例題已知{an}的生成函數(shù)為

，求an.

解

因此我們可以得到

生成函數(shù)的應(yīng)用例7.3.4求解遞推方程

且初始條件

解

設(shè)序列

的生成函數(shù)為首先注意到例題（續(xù)）因?yàn)閚>=1時(shí)有

且

所以有即得所以

指數(shù)型生成函數(shù)定義7.3.3

設(shè){an}為序列，構(gòu)造形式冪級(jí)數(shù)稱(chēng)

為{an}的指數(shù)型生成函數(shù)。例題設(shè){an}是序列，求下列數(shù)列的指數(shù)生成函數(shù)

。（1）

，m為正整數(shù)；（2）an=1；（3）an=bn

；解（1）

（2）

（3）定理定理7.3.2

設(shè)

為多重集，則S的r-排列數(shù)由指數(shù)生成函數(shù)的展開(kāi)式中

的系數(shù)給出。例題例7.3.10由1，2，3，4組成的5位數(shù)中，要求1出現(xiàn)不超過(guò)2次，但不能不出現(xiàn)，2出現(xiàn)不超過(guò)1次，3出現(xiàn)至多2次，4出現(xiàn)偶數(shù)次，求這樣的5位數(shù)個(gè)數(shù)。解展開(kāi)后

的

的系數(shù)為185，所以這樣的5位數(shù)有185個(gè)。