1、2.1 母函數(shù)的概念與性質(zhì),主講教師 魏毅強教授 聯(lián)系電話Email ,2.1 母函數(shù),遞推關(guān)系是計數(shù)的一個強有力的工具，特別是在做算法分析時是必需的。遞推關(guān)系的求解主要是利用母函數(shù)。當(dāng)然母函數(shù)尚有其他用處，但這主要是介紹解遞推關(guān)系上的應(yīng)用。例如,1.問題的提出,x2項的系數(shù)a1a2+a1a3+an-1an，中所有的項包括n個元素a1，a2， an中取兩個組合的全體；同理x3項系數(shù)包含了從n個元素a1，a2， an中取3個元素組合的全體。以此類推。,2.1 母函數(shù),若令a1=a2= =an=1，x2項的系數(shù)中每一個組合有1個貢獻，其他各項以此類推。故有：,另一方面：,

2、2.1 母函數(shù),比較等號兩端xk項對應(yīng)系數(shù)，可得一等式,2.1 母函數(shù),同樣對于 (1+x)n(1+1/x)m ，（設(shè)nm），用類似的方法可得等式：,2.1 遞推關(guān)系與母函數(shù),對于序列an，構(gòu)造一函數(shù)關(guān)系 G(x) =a0+a1x+a2x2+ anxn+， 稱G(x)為序列an 的母函數(shù)。,上述母函數(shù)也稱為普通型母函數(shù)。,注意到： 序列可能是有限的也可能是無限的，從而母函數(shù)可能是多項式也可能是無窮級數(shù)。 母函數(shù)的首項是零次冪項，對應(yīng)序列首項 a0,例如，對于序列1,1,1，的母函數(shù)為,2.1 遞推關(guān)系與母函數(shù),對于序列Cnk的母函數(shù)為,Fibonacci數(shù)列Fn母函數(shù)為,2.1 遞推關(guān)系與母函

3、數(shù),注意到：序列與母函數(shù)是一一對應(yīng)的 給定序列，可以寫出形式母函數(shù)，進而通過求和可以得到序列的母函數(shù)。 給定母函數(shù)，可以將函數(shù)展開或冪級數(shù)展開成為多項式或冪級數(shù)形式，由展開式的唯一性，比較各項系數(shù)，可以求得對應(yīng)序列。,2.1 母函數(shù),比較等式兩端的常數(shù),即得所求,事實上， (1+x)n(1+1/x)m =x-m(1+x)m+n,2.1 母函數(shù),又如等式：,兩端對x求導(dǎo)，并令x=1 可得,用類似的方法還可以得到：,2.1 母函數(shù),還可以類似地推出一些等式，但通過上面一些例子已可見函數(shù)(1+x)n在研究序列 的關(guān)系時所起的作用。對其他序列也有同樣的結(jié)果。現(xiàn)引進母函數(shù)概念如下：,2.1 母函數(shù),定義

4、1：對于序列a1,a2,a3,構(gòu)造一函數(shù) 稱函數(shù)G(x)是序列a1,a2,a3,的母函數(shù)，或普母函數(shù)(普通型母函數(shù)),2.1 母函數(shù),例如 (1+x)n 是序列 C(n,0),C(n,1),C(n,n)的母函數(shù)。,1/(1-x)=1+x+x2+xn+是序列 1,1,1，1 ，的母函數(shù)。,2.母函數(shù)的定義,如若已知序列 則對應(yīng)的母函數(shù)G(x)便可根據(jù)定義給出。反之，如若以求得序列的母函數(shù)G(x)，則該序列也隨之確定。,2.1 母函數(shù),2.1 母函數(shù),例1 設(shè)序列a1,a2,a3,的母函數(shù)為 G(x)=sin(x),求序列a1,a2,a3,解,由于,所以,2.1 母函數(shù),定義2：對于序列a1,a2

5、,a3,構(gòu)造一函數(shù) 稱函數(shù)G(x)是序列a1,a2,a3,的指母函數(shù)(指數(shù)型母函數(shù)),例如 ex是序列 1,1,1，1 ，的指母函數(shù)。,又例如,所以，階乘序列n!的指母函數(shù)為,2.1 母函數(shù),一個序列和它的母函數(shù)一一對應(yīng)。給了序列便得知它的母函數(shù)；反之，求得母函數(shù)序列也隨之而定。這種關(guān)系頗像數(shù)學(xué)中的積分變換，特別酷似離散序列的Z變換。為了求滿足某種遞推關(guān)系的序列，可把它轉(zhuǎn)換為求對應(yīng)的母函數(shù)G(x)，而G(x)可能滿足一代數(shù)方程，或代數(shù)方程組，甚至于是微分方程。,3.母函數(shù)的性質(zhì),2.1 母函數(shù),不特別說明下面假設(shè)ak，bk兩個序列對應(yīng)的母函數(shù)分別為A(x)，B(x),2.1 母函數(shù),性質(zhì)1：,若 則,性質(zhì)1：,若 則,證：,2.1 母函數(shù),例. 已知,則,2.1 母函數(shù),性質(zhì)2：若 ，,則,2.1 母函數(shù),證：,2.1 母函數(shù),例.,2.1 母函數(shù),性質(zhì)2：若 ，則,證：,2.1 母函數(shù),2.1 母函數(shù),例. 已知,2.1 母函數(shù),類似可得：,2.1 母函數(shù),性質(zhì)2：若 收斂，則,2.1 母函數(shù),2.1 母函數(shù),性質(zhì)5. 若 ，則 。,例.,則,2.1 母函數(shù),性質(zhì)5和性質(zhì)6的結(jié)論是顯而易見的。