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

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

序列普通母函數為。例2

序列普通母函數為。

序列普通母函數為

例3

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

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

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

⑵

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

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

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

⑵

C(x)=A(x)B(x)當且僅當，

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

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

3)若則

4)若收斂,,則

5)若,則

6)若,則.§4.3母函數在排列、組合中的應用一、考慮從n個不同物體中選取k個的方式數表示⑴三個不同的物體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。再考慮以下多項式(1+ax)(1+bx)(1+cx)=1+(a+b+c)x+(ab+bc+ca)x2+abcx3從中可見，以上所有可能的選取可作為x冪的系數被表示出來，即xi的系數為從三個不同物體取i個物體的方式數。如只考慮選取方法的個數，則可令a=b=c=1即有

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

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

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

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

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

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

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

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

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

求由數字2,3,4,5,6,7組成的r位數中，3和5出現偶數次，