第四章母函數(shù)及應(yīng)用

第四章母函數(shù)及應(yīng)用§4.1母函數(shù)的基本概念----母函數(shù)是序列的一種表示,它又稱為發(fā)生函數(shù)或生成函數(shù),是解決組合計(jì)數(shù)問題的有效工具之一常見母函數(shù):1.普通母函數(shù)----適用于包含組合數(shù)的序列定義4.1.1

給定無窮序列{a0,a1,a2,…,an,…},簡記為{an},稱函數(shù)為序列{a0,a1,a2,…,an,…}的普通母函數(shù).注:①普通母函數(shù)從形式上看是一個無窮級數(shù),但沒有必要討論它的收斂性,它實(shí)質(zhì)上是序列的記號,x為形式變元.對該級數(shù)可把它看成形式冪級數(shù),從而可進(jìn)行加法、乘法及形式微分等運(yùn)算,從而構(gòu)成一個代數(shù)體系。②一個序列和它的普通母函數(shù)是一一對應(yīng)的。③對有限序列{a0,a1,a2,…,an},它可表示為無窮序列{a0,a1,a2,…,an,…},，其中an+1=an+2=…=0。例1

序列普通母函數(shù)為。例2

序列普通母函數(shù)為。

序列普通母函數(shù)為

例3

求序列普通母函數(shù)。2.指數(shù)母函數(shù)----適用于包含排列數(shù)的序列定義4.1.2

給定無窮序列{a0,a1,a2,…,an,…},稱函數(shù)為序列{a0,a1,a2,…,an,…}的指數(shù)母函數(shù).例3①序列{P(n,0),P(n,1),…,P(n,n)}的指數(shù)母函數(shù)為②序列{P(0,0),P(2,1),…,P(2n,n),…}的指數(shù)母函數(shù)為

普通母函數(shù)與指數(shù)母函數(shù)間的關(guān)系：設(shè)f(x)，fe(x)分別為序列{a0,a1,a2,…,an,…}的普通母函數(shù)和指數(shù)母函數(shù)，則§4.2母函數(shù)的運(yùn)算1.普通母函數(shù)設(shè)A(x),B(x),C(x)分別為序列{a0,a1,a2,…,an,…},{b0,b1,b2,…,bn,…},{c0,c1,c2,…,cn,…}的普通母函數(shù)，則有以下定義⑴C(x)=A(x)+B(x)當(dāng)且僅當(dāng)ci=ai+bi,i=0,1,…,n,…;

⑵

C(x)=A(x)B(x)當(dāng)且僅當(dāng)例1

設(shè)A(x)為序列{a0,a1,…,an,…}的普通母函數(shù),則A(x)/(1-x)為序列{a0,a0+a1,…,a0+a1+…+an,…}的普通母函數(shù)。例2

求和的值。2.指數(shù)母函數(shù)設(shè)A(x),B(x),C(x)分別為序列{a0,a1,a2,…,an,…},{b0,b1,b2,…,bn,…},{c0,c1,c2,…,cn,…}的指數(shù)母函數(shù)，則有以下定義⑴C(x)=A(x)+B(x)當(dāng)且僅當(dāng)ci=ai+bi,i=0,1,…,n,…;

⑵

C(x)=A(x)B(x)當(dāng)且僅當(dāng)，

i=0,1,…,n,…;例4

證明下列恒等式：普通母函數(shù)的基本性質(zhì)1)若則.2)若,則

3)若則

4)若收斂,,則

5)若,則

6)若,則.§4.3母函數(shù)在排列、組合中的應(yīng)用一、考慮從n個不同物體中選取k個的方式數(shù)表示⑴三個不同的物體a、b、c，從中選取一個：或選a，或選b，或選c，這些可能的選取象征性地記為

a+b+c.

從a、b、c中選取兩個有三種方法：或選a與b，或選b與c，或選c與a，這些可能的選取也可象征性地記為

ab+bc+ca.從a、b、c中選取三個只有一種方法，象征性地記為abc。再考慮以下多項(xiàng)式(1+ax)(1+bx)(1+cx)=1+(a+b+c)x+(ab+bc+ca)x2+abcx3從中可見，以上所有可能的選取可作為x冪的系數(shù)被表示出來，即xi的系數(shù)為從三個不同物體取i個物體的方式數(shù)。如只考慮選取方法的個數(shù)，則可令a=b=c=1即有

這樣，有一種方法從三個物體中一個也不取，有3種方法從中取一個，有3種方法取2個，有一種方法取3個。

⑵由于故從n個不同物體中取k個的方法數(shù)即為xk的系數(shù)。⑶從n個不同物體中允許重復(fù)選取k個物體1+x：可象征地表示一物體可不選，或只選取一次，即至多選取一次；

1+x+x2:可象征地表示一物體可不選，或只選取一次，或選取兩次，即至多選取兩次；1+x+x2+x3+….：可象征地表示一物體可不選，或只選取一次，或選取兩次，或選取三次，….。這樣，中xk的系數(shù)即可表示從n個不同物體中允許重復(fù)取k個物體的方式數(shù)。二、普通母函數(shù)在組合計(jì)數(shù)問題中的應(yīng)用例1

求⑴從n個不同物體中允許重復(fù)選取k個不同的物體的方式數(shù)為F(n,k)；⑵從n個不同物體中允許重復(fù)選取k個不同的物體，但每個物體至少出現(xiàn)一次的方式數(shù)；⑶從n個不同物體中允許重復(fù)選取k個不同的物體，但每個物體至少出現(xiàn)奇數(shù)次的方式數(shù)；⑷從n個不同物體中允許重復(fù)選取2k個不同的物體，但每個物體至少出現(xiàn)偶數(shù)次的方式數(shù)；例2

一個書架上共有16本書，其中4本高等數(shù)學(xué)，3本普通物理，4本數(shù)據(jù)結(jié)構(gòu)，5本離散數(shù)學(xué)，⑴求從中選取k本書的方式數(shù)，其中k=12；⑵k=12本書中至少有2本高數(shù)，1本物理，又有多少種選取方式？例3

現(xiàn)有無窮多個字母A、B、C，求從中取n個字母但必須含有偶數(shù)個A的方式數(shù)。例4

現(xiàn)有2n個A，2n個B和2n個C，求從它們中選取3n個字母的不同方式數(shù)。三、指數(shù)母函數(shù)在排列計(jì)數(shù)問題中的應(yīng)用已知所以從n個不同物體中取k個物體的組合數(shù)ak所成序列的普通母函數(shù)可變?yōu)榇吮砻?，從n個不同物體中取k的排列數(shù)所成序列的指數(shù)母函數(shù)為(1+x)n。另外，象征性地表示某一物體在排列中可以不取或取一次，同樣某物體在排列中可以不取，或取一次，或取兩次，….，或取k次可象征性地表示為如某物體的重復(fù)次數(shù)為無窮次，則上式為例1

求從n個不同物體中允許重復(fù)地選取r個物體的排列數(shù)(nr)。例2

求1,3,5,7,9五個數(shù)字組成的r位數(shù)的個數(shù)，其中要求7、9出現(xiàn)的次數(shù)為偶數(shù)，其他數(shù)字的出現(xiàn)不限。例3

求由數(shù)字2,3,4,5,6,7組成的r位數(shù)中，3和5出現(xiàn)偶數(shù)次，