組合數(shù)學課件：生成函數(shù)

生成函數(shù)3.1Fibonacci數(shù)列的生成函數(shù)

3.2生成函數(shù)的一般性討論

3.3組合的生成函數(shù)

3.4排列的生成函數(shù)

3.5Catalan數(shù)列與Stirling數(shù)列的生成函數(shù)

3.6分配問題

3.7整數(shù)n分為m個類的(無序)拆分數(shù)Pmn

3.8n的拆分數(shù)Pn的生成函數(shù)

3.9整數(shù)n分為以h為最小類的拆分數(shù)

3.10有序拆分3.1Fibonacci數(shù)列的生成函數(shù)

從 出發(fā)，推證二項式系數(shù)的若干等式，這給問題的討論帶來了許多方便。將數(shù)列 與函數(shù) 聯(lián)系起來的做法，稱做“生成函數(shù)（generatingfunction）方法”。由于將(1+x)n展開即可得到所有的,因此，常稱 為（有限或無限）數(shù)列ak(k=1,2,…)的生成函數(shù)或母函數(shù)。

意大利數(shù)學家Fibonacci在13世紀初提出過如下一個有趣問題：年前養(yǎng)了一對小兔（雌雄各一），這對兔子中的母兔從2月份開始每月都產(chǎn)下一對雌雄各一的小兔。每對新生小兔間隔一月后也開始每個月都產(chǎn)下一對新的小兔（雌雄各一）。如是而下，假定兔子都不死亡，問一年后共有多少對兔子？假定年前為0月份，年后為13月，不難推算各月兔子對數(shù)為：月份：0，1，2，3，4，5，6，7，8，9，10，11，12，13，…

兔子對數(shù)：1，1，2，3，5，8，13，21，34，55，89，144，233，377，…

著名的Fibonacci數(shù)列由此而得名。這一數(shù)列的增長速度是很快的。其中，第二年年底兔子有50000對，第三年年底兔子有15000000對，第55項就超過了1萬億對。若設Fn為第n個月所有的兔子對數(shù)，則由各月兔子數(shù)不難證得如下遞推式成立:(3.1.1)下面求Fibonacci數(shù)列的生成函數(shù)F(x)：由此得(3.1.2)此即Fibonacci數(shù)列的生成函數(shù)。因1-x-x2的二根為于是因此（3.1.3）若從比較系數(shù)，可得二項式系數(shù)表示的Fn為(3.1.4)由此表示式可以推出Fibonacci數(shù)列的組合學意義如下：

命題1

Fn等于集合Zn-1={1,2,…,n-1}中不含相繼整數(shù)的子集的個數(shù)。例如，Z3={1,2,3}的這種子集有￠，{1}，{2}，{3}，{1，3},共F4=5個。

證明令f(n,k)表示Zn={1,2,…,n}中不含相繼整數(shù)的k元子集的個數(shù)。設{i1,i2,…,ik}為此種子集，其中i1

＜i2

＜…＜ik

，由不相繼性知is-is-1≥2，于是若記js=is-s，則必有js-js-1，反之由js＞js-1≥1也可推出is-is-1≥2。易證全體{i1,i2,…,ik}與{j1,j2,…,jk}之間構成一雙射函數(shù)。注意到j1=i1-1≥0∧jk=ik-k≤n-k

可見,{j1,j2,…,jk}為集合{0,1,…,n-k}的一個k元子集，這種子集的個數(shù)為C(n-k+1,k)故f(n,k)=C(n-k+1,k)，由此得表示Zn中不含相繼整數(shù)的子集數(shù)。亦即表示集合Zn-1中不含相繼整數(shù)的子集的個數(shù)。

命題2

f*(n,k)表示不含圈(1,2,…,n,1)中相繼整數(shù)的k元子集的個數(shù)，則不含圈(1,2,…,n,1)中相繼整數(shù)的所有子集數(shù)為其中Fn*有時也稱為校正的Fibonacci數(shù)列。

證明將滿足條件的k元子集分成兩類，第一類不包含n，第二類包含n。顯見第一類k元子集在(1,2,…,n-1)中選取，計有f(n-1,k)種取法；第二類k元子集必不包含1與n-1,故除去n外，余下k-1個元必須在{2,3,…,n-2}中選取，其取法計有f(n-3,k-1)種。因此從而(1)Fn+m=FmFn+Fm-1Fn-1。證明

(3.1.5)

(2)證明注意到對任一級數(shù)有成立，于是從1=F(x)(1-x-x2)=F(x)(2-x-x2)-F(x)得F(x)=F(x)(2-x-x2)-1=F(x)(2+x)(1-x)-1=F(x)(2+x)-(1-x)-1

比較兩邊xn之系數(shù)即得（3.1.6）式。（3.1.6）直接由遞推關系式（3.1.1）不難推得(3.1.7)(3.1.8)·

下面利用（3.1.1）式給出求Fibonacci數(shù)列的算法：№1輸入n；№2

F0

1;F1

1；№3對k=0,n/2

打印F0,F1；

F0

F0+F1;F1

F1+F0;

№4結束?！?/p>

求Fibonacci數(shù)列亦可采用遞歸算法，主要語句如下：

ifn=0orn=1thenF(n)=1elseF(n)=F(n-1)+F(n-2)3.2生成函數(shù)的一般性討論定義1

設gk(x)(k=0,1,2,…)線性無關，則稱為ak(k=0,1,2,…)的生成函數(shù)。(3.2.1)式稱為關于未定元x的形式冪級數(shù)，它是從代數(shù)學觀點引入的。對于實數(shù)R上的數(shù)列{ak}及R上的未定元x，稱表達式(3.2.1)為R上的形式冪級數(shù)。一般情況下，形式冪級數(shù)中的x只是一個抽象符號，并不需要對x賦予具體數(shù)值，從而避開了討論級數(shù)收斂性的問題。(3.2.1)

R上關于未定元x的形式冪級數(shù)的全體記為R(x)。在集合R(x)中適當定義加法（+）和乘法(·)，則(R(x),+,·)構成環(huán)。該環(huán)中的元素即為形式冪級數(shù)。設 若對任意k≥0，有ak=bk，則稱A(x)與B(x)相等，記為A(x)=B(x)

設λ為任意實數(shù)，，則稱為λ與A(x)的數(shù)乘積。設A(x)、B(x)定義如上，則可定義二冪級數(shù)的加法運算為

并可根據(jù)gk(x)的不同形式定義A(x)與B(x)的乘積(如下面的定義3)。在環(huán)(R(x),+,·)上，還可定義形式冪級數(shù)的形式導數(shù)。對 ，規(guī)定稱DA(x)為A(x)的形式導數(shù)。A(x)的n次形式導數(shù)可以遞歸地定義為D0A(x)=A(x)

DnA(x)=D(Dn-1A(x)),n≥1

可證，形式冪級數(shù)的形式導數(shù)滿足如下規(guī)則：（1）D(αA(x)+βB(x))=αDA(x)+βDB(x)；（2）D(A(x)·B(x))=A(x)DB(x)+B(x)DA(x);

（3）DAn(x)=nAn-1(x)DA(x)。生成函數(shù)有如下幾種：(1)取gk(x)=xk,則有此式常稱為尋常或普通（Ordinary）型生成函數(shù)。(2)取gk(x)=xk/k!,則有此式常稱為指數(shù)（Exponential）型生成函數(shù)。(3)取gk(x)=1/kx,則有此式即為Dirichlet生成函數(shù)。(4)取gk(x)=［x］k,則有此式常稱為下階乘生成函數(shù)。

定義2

設A(x),B(x)分別為{ak}與{bk}的生成函數(shù)，則A(x)+B(x)=C(x)為{cn}的生成函數(shù)，其中:ck=ak+bk

定義3

設A(x),B(x)分別為{ak}與{bk}的生成函數(shù)，則A(x)B(x)=C(x)為{cn}的生成函數(shù)，其中：

(1)在尋常生成函數(shù)的情形下，有特別取若{ak}的生成函數(shù)為A(x)，

則的生成函數(shù)為(2)在指數(shù)型生成函數(shù) 的情形下，有(3)在Dirichlet生成函數(shù) 的情形下，有(1)

證明令B(x)=b0+b1x+b2x2+…+bm-1xm-1+bmxm+bm+1xm+1+…，據(jù)前提知例1

設則(2)證明

據(jù)假設知例2設

(3)證明由假設

等式左端相加,顯見為 。等式右端相加,得故例3

設A(x)=1/(1-x),,則類似可得(4)收斂,且

證明因收斂，故bk存在。下面考察B(x)中xk的系數(shù)(k=0,1,2,…)?！瓘亩?5)例4(6)(7)

例5

設A(x)=1+x+x2+…=1/(1-x),B(x)=x+2x2+3x3+…=x/(1-x)2，且易知3.3組合的生成函數(shù)

與組合問題有關的計數(shù)常使用尋常生成函數(shù)。

命題設多重集S={r1·e1,r2·e2,…,rm·em},且r1+r2+…+rm=n,則S的k可重組合數(shù)ck對應序列{ck}的生成函數(shù)為其中，k可重組合數(shù)ck為G(x)展開式中xk的系數(shù)。

證明令G(x)中各∑的項分別對應諸元素的某種可能取法。例如,對i=t,xr表示元素et選取了r次。依次類推。顯見G(x)展開式中的項xk具有一般形式其中k1+k2+…+km=k,0≤ki≤ri,i=1,2,…,m

對此方程的一非負整數(shù)解(k1,k2,…,km)（在前提0≤ki≤ri,i=1,2,…,m下），乘積 就對應了諸元素e1,e2,…,em的一種可重取法。合并同類項后，xk的系數(shù)就表示了從多重集S中取出k個元素的所有可能的可重組合數(shù)ck。

推論1

設S={e1,e2,…,em}，則S的k可重組合數(shù)ck對應序列{ck}的生成函數(shù)為G(x)=(1+x)m其組合數(shù)ck為G(x)展開式中xk的系數(shù)

推論2

設S={∞·e1,∞·e2,…,∞·em}，則S的k（無限）可重組合數(shù)ck對應序列{ck}的生成函數(shù)為

其組合數(shù)ck為G(x)展開式中xk的系數(shù)C(m+k-1,k)。推論2無0≤ki≤ri,i=1,2,…,m限制，由2.6節(jié)中例10即知ck=C(m+k-1,k)

推論3

設S={∞·e1,∞·e2,…,∞·em}，則S的每個元素至少取一次的k（無限）可重組合數(shù)ck（k≥m）對應序列{ck}的生成函數(shù)為其組合數(shù)ck為G(x)展開式中xk的系數(shù)C(k-1,m-1)。這是由于

推論4

設S={∞·e1,∞·e2,…,∞·em}，且S的每個元素出現(xiàn)非負偶數(shù)次，則S的k（無限）可重組合數(shù)ck對應序列{ck}的生成函數(shù)為其組合數(shù)ck為G(x)展開式中xk的系數(shù)，即當k為偶數(shù)時當k為奇數(shù)時

推論5

設S={∞·e1,∞·e2,…,∞·em}，則S的每個元素出現(xiàn)奇數(shù)次的k（無限）可重組合數(shù)ck對應序列{ck}的生成函數(shù)為其組合數(shù)ck為G(x)展開式中xk的系數(shù)，即若2|(k-m)若k-m為奇數(shù)

推論6

設S={∞·e1,∞·e2,…,∞·em}，若限定元素ei出現(xiàn)的次數(shù)集合為Pi(1≤i≤n)，則從S中取出k個元素的組合數(shù)ck對應序列{ck}的生成函數(shù)為

推論7

設多重集S={r1·e1,r2·e2,…,rm·em}，且r1+r2+…+rm=n，則S中的每個元素ei至少出現(xiàn)ki(i=1,2,…,m)次的r可重組合數(shù)cr對應序列{cr}的生成函數(shù)為其組合數(shù)cr為G(x)展開式中xr的系數(shù)，r=k,k+1,…,n;k=k1+k2+…+km。

例1

求不定方程k1+k2+k3+k4=20的解組數(shù)。其中，限制k1可取0，2，4；k2可取1，3，5；k3可取6，7；k4可取8，9。

解設不定方程 的解組數(shù)目為ck，本例中m=4,k=20。注意到對ki(i=1,2,3,4)的限制，序列{ck}對應的生成函數(shù)為G(x)=(1+x2+x4)(x+x3+x5)(x6+x7)(x8+x9)由G(x)展開式中x20的系數(shù)知題給不定方程解組數(shù)目為c20=6。

注意，有時會因對ki的限制使ck取值為0。例如，對S={a,b,c}，若限制a可重復1，3，5次；限制b可重復2，4，6次；限制c必須出現(xiàn)6次，則由G(x)=(x+x3+x5)(x2+x4+x6)x6雖可求出c9=c17=1,c11=c15=2，c13=3,但對小于9及偶數(shù)的k,ck的取值全為0。例2

求S={3·a,4·b,5·c}的10組合數(shù)。解設S的k組合數(shù)為ck，則{ck}對應的生成函數(shù)為展開式中x10的系數(shù)即S的10組合數(shù)為6。

例3

設有5個紅球和8個黃球，要求每次取出不少于2個紅球和偶數(shù)個黃球，求所有的組合方式數(shù)。

解組合方式數(shù)對應序列的生成函數(shù)為因此，總的組合方式數(shù)為1+1+2×8+1+1=20。

若考慮同色球各不相同或加有標記，這時可分別設紅球與黃球取法所成序列的生成函數(shù)為A(x)與B(x)。易知從而C(x)展開式中xk的系數(shù)即為每次取出k個球的組合方式數(shù)，總的組合方式數(shù)目為所有系數(shù)之和。

例4

設有紅球2個，黑、白球各1個，問（1）共有多少不同的選取方法？試加以枚舉。（2）若每次從中任取3個，有多少種不同取法？

解（1）設用r，b，w分別代表紅、黑、白三種球，兩個紅球的取法與r0,r1,r2對應，即紅球的可能取法與1+r+r2中r的各次冪一一對應，亦即r0=1表示不取紅球，r表示取1個紅球，r2表示取2個紅球。對其它球，依此類推法，則不同選取方法數(shù)所成序列對應的尋常生成函數(shù)為

分析上式，不難發(fā)現(xiàn)

1：一個球都不取，僅有一種方案；

r+b+w：取1個球的方案有3種，分別為紅，黑，白；

r2+rb+rw+bw：取2個球的方案有4種，分別為紅紅，紅黑，紅白，黑白；

r2b+r2w+rbw：取3個球的方案有3種，即2紅1黑，2紅1白，三色球各取其一；

r2bw：取4個球的方案僅1種，即所有球全取。若令r=b=w=1，即可求得所有不同的選取方案總數(shù)為G(1,1,1)=1+3+4+3+1=12

（2）若只考慮每次取3個球的方案數(shù)，而不需枚舉，則可令r=b=w=x。寫出G(x)=(1+x+x2)(1+x)2=1+3x+4x2+3x3+x4由x3的系數(shù)知所求方案為3種。

例518張參觀券分發(fā)給a,b,c,d四個小組，其中各組分配票數(shù)ra,rb,rc,rd分別為1≤ra≤5,1≤rb≤6,2≤rc≤7,4≤rd≤10。求所有不同的分配方案數(shù)。

解這實際上相當于由a,b,c,d四類共5+6+7+10=28個元素中可重復地取18個元素的組合問題。各類球取法的下界ki(i=1,2,3,4)分別為1,1,2,4；上界ri分別為5,6,7,10。m=4,n=18。由推論6知相應的生成函數(shù)為由x18前的系數(shù)知，共有140種分配方案。

若將票數(shù)改為n=4，各組所分票下界數(shù)改為ki=0(i=1,2,3,4)，上界不變，這時與中x4的系數(shù)是一樣的，但用G2(x)求解要比用G1(x)求解方便得多。同理，當n=6時，可以用來代替G1(x)求x6的系數(shù)。

例6

求一粒骰子連續(xù)投擲兩次，出現(xiàn)點數(shù)之和為10的概率。

解設骰子各點出現(xiàn)的概率均等。

解法1

投擲一次出現(xiàn)的點數(shù)有6種，連續(xù)投擲兩次所得點數(shù)共有6×6=36種可能。由枚舉法，兩次投擲出現(xiàn)點數(shù)之和為10的方案恰有3種：(4,6)，(5,5)，(6,4)，故出現(xiàn)點數(shù)之和為10的概率為3/36=1/12。解法2

依題意，投擲骰子出現(xiàn)點數(shù)所成序列的生成函數(shù)為

由x10的系數(shù)為3知有3種點數(shù)之和為10的方案，故知所求概率為3/36=1/12。初看解法二比解法一要復雜一些，但若將問題改為一粒骰子連續(xù)投擲10次，求出現(xiàn)點數(shù)之和為30的概率時，解法二就顯得有力多了。這時不難算得x30前的系數(shù)為2930455，故所求概率為3.4排列的生成函數(shù)

當涉及到與排列有關的問題時，通常使用指數(shù)型生成函數(shù)。由于 ,可見或{［n］k}的生成函數(shù)為(1+x)n。因G(x)=(1-x)-1=1+x+x2+…,故其為序列1,1,1,…的尋常生成函數(shù)。又因 ,顯見序列1,1,1,…的指數(shù)型生成函數(shù)為Ge(x)=ex。

命題1

若元素e1可重復α1,α2,…次，元素e2可重復β1,β2,…次，元素em可重復λ1,λ2,…次，則m元集的這種k可重排列數(shù)Pk對應序列{Pk}的生成函數(shù)為事實上，上式右端等于

由多項式系數(shù)的組合學意義知，(k!/αi1!βi2!…

λim!) 正是元素e1出現(xiàn)αi1次，元素e2出現(xiàn)βi2次，元素em出現(xiàn)λim次的k可重排列數(shù)。故按所有可能的αi1+βi2+…+λim=k求和，即得總的k排列數(shù)Pk。

推論1

設S={∞·e1,∞·e2,…,∞·em}，若元素ei(i=1,2,…,m)重復出現(xiàn)的次數(shù)構成集合Γi，則集S中元素的這種k可重排列數(shù)Pk對應序列{Pk}的生成函數(shù)為k可重排列數(shù)Pk為G(x)展開式中xk/k!的系數(shù)。

推論2

設m元多重集S={r1·e1,r2·e2,…,rm·em}，且r1+r2+…+rm=n，則S的k可重排列數(shù)Pk對應序列{Pk}的指數(shù)型生成函數(shù)為

其中，k可重排列數(shù)Pk為Ge(x)展開式中xk/k!的系數(shù)(k=0,1,2,…)。

例13個紅球，2個黃球，3個藍球，每次從中取出4個排成一列，求排列方案數(shù)。

解

m=3,r1=3,r2=2,r3=3,k=4,由推論2知故知，從所給n色球中取出4個的排列方案有70種。類似于組合問題，令

從中可以看出，取1個球的3種排列方案為：r,y,b，即紅，黃，藍分別取其一;取2個球的9種排列方案為：rr,yy,bb,ry,rb,by,yb,yr,br。

推論3

設S={r1·e1,r2·e2,…,rm·em}，則S中元素的k（無限）可重排列數(shù)Pk對應序列{Pk}的指數(shù)型生成函數(shù)為其中，k排列數(shù)Pk為xk/k!的系數(shù)mk。

推論4

特別地，若每個元素ei至少出現(xiàn)一次（這時有k≥n），則Ge(x)=(ex-1)m，從中取出k個元素的可重排列數(shù)事實上，因每個元素至少出現(xiàn)一次的k排列數(shù)Pk的生成函數(shù)為故有應用如下幾個算子：差分算子Δ：Δf(x)=f(x+1)-f(x)

移位算子E：Ef(x)=f(x+1)

恒等算子I：If(x)=f(x)

上式之Pk可以簡寫成

定義移位算子Ea：Eaai=ai+1,Ebbi=bi+1，任一指數(shù)生成函數(shù) 可寫成同樣于是因此若則此即3.2節(jié)中的（3.2.8）式。上述過程可以更簡潔地寫成A(x)=eax,ai≡ai

B(x)=ebx,bi≡bi

cn=(a+b)n,ai≡ai,bi≡bi

后一式表示將(a+b)n按通常方式展開，再易ai為ai,易bi為bi。命題2（Bernoulli求和公式）

證明記Ef(x)=f(x+1)為移位算子，If(x)=f(x)為恒等算子，Δf(x)=f(x+1)-f(x)為差分算子，不難證得Δ=E-I。于是由此可見此式兩邊算子施于f(1)，即得所證。Bernoulli求和公式一般用于f(x)為多項式的場合，此時f(x)的高階差分等于零。如對f(x)=x3,逐次計算Δif(x)，如下所示：k12345

f(k)182764125

Δf(k)7193761

Δ2f(k)121824

Δ3f(k)66

Δ4f(k)0于是f(1)=1,Δf(1)=7,Δ2f(1)=12,Δ3f(1)=6,Δ4f(1)=Δ5f(1)=…=0應用求和公式即得

推論5

設S={r1·e1,r2·e2,…,rm·em}，若要求元素ei至少取ki個（ki≥0），則這種排列數(shù)形成序列的生成函數(shù)為

推論6

設S={r1·e1,r2·e2,…,rm·em}，且r1+r2+…+rm=n，取k=n，即得全排列數(shù)為例2

五個數(shù)字1，1，3，3，5能組成多少4位數(shù)？解令Pk表示組成k位數(shù)的個數(shù)，{Pk}的指數(shù)型生成函數(shù)為由P4=30知能組成30個4位數(shù)。

例3

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

解設滿足條件的n位數(shù)的個數(shù)為Pn，則{Pn}對應的指數(shù)型生成函數(shù)為故例4

注意到故是n元多重集（重復次數(shù)不限）每個不同元素出現(xiàn)偶數(shù)次的k排列數(shù)所成序列的指數(shù)生成函數(shù)。例5是n元多重集（重復次數(shù)不限）第一個元素出現(xiàn)0，2或5次，第二個元素出現(xiàn)1，2或6次，其余n-2個元素出現(xiàn)的次數(shù)不加限制的k排列數(shù)的指數(shù)生成函數(shù)。

例6

確定k格棋盤的3染色方法數(shù)，其中白色染偶數(shù)格，其余兩種顏色所染方格數(shù)不限。

解令ak表示這種染色數(shù)，并定義a0為1。則ak等于三色多重集（每種顏色重復次數(shù)不限）白色出現(xiàn)偶數(shù)次的k排列數(shù)。于是序列a0,a1,…,ak,…的指數(shù)生成函數(shù)為從而

由2.10節(jié)中命題3知,xn是第二類Stirling數(shù)Snk的下階乘生成函數(shù)。又由2.10節(jié)中定義5及命題10可見,［x］n是第一類Stirling數(shù)skn的尋常生成函數(shù)，［x］n是|skn|的尋常函數(shù)。兩類Stirling數(shù)是溝通xn,［x］n,［x］n這三種首項為1的多項式的橋梁。3.5Catalan數(shù)列與Stirling數(shù)列的生成函數(shù)

定義1

空集或有限點集T，滿足：

(1)有一特定結點r稱為“根”；

(2)刪除根r，則剩下的點T\{r}組成兩棵子二叉樹：Tl（左子樹）及Tr(右子樹)。3.5.1Catalan數(shù)列的生成函數(shù)例1

二叉樹（或二元樹）的計數(shù)問題。例如，3個結點可有5棵不同的二叉樹,如圖3.5.1所示。圖3.5.1二叉樹

一般地，設cn為n個結點的不同的二叉樹的個數(shù)，則有c0=1。在n＞0的情形下，二叉樹有一個根結點及n-1個非根結點，設左子樹Tl有k個結點，則右子樹Tr有n-1-k個結點，于是不同的左子樹有ck種，右子樹有cn-1-k種，從而比較上式與3.2節(jié)中(3.2.7)式，可見對應二叉樹數(shù)目的生成函數(shù)B(x)=c0+c1x+c2x2+…滿足方程xB2(x)=B(x)-1,B(0)=1解此二次方程，并應用二項式定理得因此

例2

設有一n+1(n≥2)邊的凸多邊形，若用連接不交對角線的方法把該多邊形進行三角剖分，求所有不同的剖分方案數(shù)。

解令hn表示將n+1(n≥2)邊凸多邊形進行三角形剖分的方案數(shù)，則當n=1時，h1=1，當n≥3時，任取多邊形一邊記作e，其兩端點一端記為v1，一端記為vn+1，余點依次相鄰標記如圖3.5.2所示。現(xiàn)以v1，vn+1及任意頂點vk+1(k=1,2,…,n-1)構作一三角形，該三角形將凸多邊形分為F1,F2兩個區(qū)域。其中，F(xiàn)1由k+1邊凸多邊形圍成，其三角形剖分方案數(shù)為hk，F(xiàn)2由n-k+1邊凸多邊形圍成，其三角形剖分方案數(shù)為hn-k，由乘法原理知 。易證當n=5時，可求得圖3.5.2余點依次相鄰標記圖3.5.3凸6邊形的14個剖分方案3.5.2Stirling數(shù)列的生成函數(shù)為醒目起見，把第一類與第二類Stirling數(shù)分別記為S1(n,k)與S2(n,k)。

（1）序列{S1(n,k)}的指數(shù)型生成函數(shù)為（2）序列{S2(n,k)}的指數(shù)型生成函數(shù)為(et-1)k/k!,且有（3）序列{S2(n,k)}的尋常生成函數(shù)為并且還有證明（1）兩端同乘以tn/n!,并對n求和有（3.5.1）式（3.5.1）若記,則故（3.5.1）式可改寫如下：因為S0(t)=1，Sk(0)=0，所以這就證明了序列{S1(n,k)}的指數(shù)型生成函數(shù)為(2)據(jù)2.10節(jié)中命題3有

另一方面，對于任意正整數(shù)t，應用移位算子E、差分算子Δ及恒等算子I，有由此即知又由2.10節(jié)命題2的推論2知故這就證明了{S2(n,k)}的指數(shù)型生成函數(shù)為且(3)對遞歸關系S2(n+1,k)=S2(n,k-1)+kS2(n,k)兩端同乘以tn+1，并對n求和，得即令則有故從而等式右端展開后，各tn-k項的一般形式為

其中，ni≥0(i=1,2,…,k),且 。合并同類項后知tn-k的系數(shù)為其中，n1,n2,…,nk

是滿足上述不定方程的一切有序非負整數(shù)解組，因此

例如，對S2(n,k)，n=5，k=3，n-k=2，n1+n2+…+nk=2的所有有序非負整數(shù)解組為（2，0，0）,（0，2，0）,（0，0，2）；（1，1，0）,（1，0，1）,（0，1，1）。故知S2(5,3)=12+22+32+11·21+11·31+21·31

=1+4+9+2+3+6=25

Fibonacci數(shù)列，Catalan數(shù)列及Stirling數(shù)列形成組合數(shù)學中三種典型的數(shù)列，實際應用中許多組合計數(shù)結果都與它們相同或相似。3.6分配問題3.6.1盒子不相同的分配問題命題1

有n個相同的球，m個不同的盒子，各盒的容量分別為ni(ni≥0,i=1,2,…,m)。則其分配序列的尋常生成函數(shù)為

證明本命題與3.3節(jié)中的命題是一樣的。這里可將m個盒子看成m個元素，記為e1,e2,…,em，n個相同的球中分別有:x1個球放入e1，即e1被選取x1次，x1≤n1；x2個球放入e2，即e2被選取x2次，x2≤n2；

…

xi個球放入ei，即ei被選取xi次，xi≤ni；

…

xm個球放入em，即em被選取xm次，xm≤nm。以上放法可記為：e1…e1

e2…e2

…

ei…ei

…

em…em

x1個x2個xi個xm個

且x1+x2+…+xm=n,0≤xi≤ni,i=1,2,…,m。以上放法僅與ei的出現(xiàn)次數(shù)有關，而不考慮ei的順序。因此，滿足命題條件的分配問題可歸結為多重集S={n1·e1,n2·e2,…,ni·ei,…,nm·em}的n-可重組合問題，故其生成函數(shù)與3.3節(jié)命題相同。

推論1

若各盒容量ni=1(i=1,2,…,m)，球數(shù)n≤m，則其分配序列的生成函數(shù)為(1+x)m，且分配方案數(shù)為

推論2

若各盒的容量不加限制，則其分配序列的生成函數(shù)是(1-x)-m，其分配方案數(shù)為C(m+n-1,n)。

證明由于各盒容量不加限制，故生成函數(shù)為

推論3

若各盒的容量不加限制，但不允許有空盒，則其分配序列的生成函數(shù)為且其分配方案數(shù)為。

推論4

若各盒容量限制為非負偶數(shù),則其分配序列的尋常生成函數(shù)是(1-x2)-m，分配數(shù)是n為偶數(shù)n為奇數(shù)其生成函數(shù)為其中n=2k為偶數(shù)。

推論5

若各盒的容量限制為奇數(shù)，則其分配序列的尋常生成函數(shù)是［x/(1-x2)］m，其分配方案數(shù)是n-m為偶數(shù)n-m為奇數(shù)

命題2

有n個不同的球，m個不同的盒子，各盒的容量ni(ni≥0,i=1,2,…,m)。則其分配序列的指數(shù)型生成函數(shù)為

證明將n個不同的球放入m個不同的盒子（盒子加有編號），每次不同的放法可按如下方式記錄。用b1,b2,…,bn表示n個不同的球，用e1,e2,…,em表示m個不同的盒子。b1b2…bn——n個不同的球已按某種順序排好j1j2…jn——各球所占盒子的編號(反映于下標)其中ji∈{1,2,…,m}(i=1,2,…,n)。對球的分配不同，排列j1j2…jn也就不同；反之，不同的排列j1j2…jn對應了球的不同分配。而這種排列正是m個元素的n-可重排列。其中每個元素的重復次數(shù)分別是n1,n2,…,nm。從而問題歸結為集合S={n1·e1,n2·e2,…,nm·em}的n-可重排列。故其生成函數(shù)為

推論1

若各盒的容量ni=1(i=1,2,…,m)，則其分配方案數(shù)為P(m,n)(n≤m)，其生成函數(shù)為

推論2

若各盒容量ni≥0且n1+n2+…+nm=n，則其分配方案數(shù)為n!/(n1!n2!…nm!)。其生成函數(shù)為推論3

若各盒容量不加限制，則其分配序列的生成函數(shù)為顯見其分配方案數(shù)為mn。

推論4

若各盒非空（即ni≠0,i=1,2,…,m）。分配方案數(shù)為A(n,m)=m!S(n,m)。且分配序列的生成函數(shù)為(ex-1)m。

推論5

若指定r個盒非空，其余m-r個盒的容量不加限制，則其總的分配方案數(shù)為

證明不妨假定前r個盒非空，其中放入k個球(r≤k≤n),則因由n個球中任取k個的選法有種；又k個球放入r個盒中，各盒非空，據(jù)推論4知分配方案數(shù)為A(k,r)。

把剩余的n-k個球不加限制地放到m-r個盒中，據(jù)推論3可知分配方案數(shù)為(m-r)n-k。由乘法原理，二不同分配方案數(shù)為A(k,r)(m-r)n-k。注意到k可取r,r+1,…,n,共n-r+1種情況，再由加法原理，即得總的分配方案數(shù)為推論6

若有r個以上的空盒，則其分配方案數(shù)為證明空盒數(shù)s≥r，與非空盒數(shù)m-s取法對應羅列如下：空盒數(shù)s=r,r+1,…,m-1，m

非空盒數(shù)m-s=m-r,m-(r+1),…,1,0

以上每組對應的分配方案數(shù)可分為兩步計算：設有m-k個盒非空(r≤k≤n)，則（1）從m個盒中任取m-k個非空盒的選法數(shù)為

（2）

n個球放到m-k個非空盒中，據(jù)推論4，其分配方案數(shù)為A(n,m-k);

（3）由乘法原理，每種情況的分配方案數(shù)為A(n,m-k)。

注意到k=m時A(n,0)=0，故總的分配方案數(shù)為

若干個染有顏色的球，同色球看作一個類，同類中的球視為是相同的。若恰有1個球的顏色有k1種，恰有2個球的顏色有k2種，…，恰有s個球的顏色有ks種，可將所有球分類的型記為k1

·1+k2

·2+…+ks

·s

或者記為例如，14個球染有赤、橙、黃、綠、青、藍、紫7種顏色，即分為7個類，且各種顏色相應的數(shù)量分別為2，1，3，2，1，2，3，則這14個球分類的型為12×23×32。

命題3

m個不同的盒子，分類的型為 的n個球，k1+2k2+…+sks=n，若各盒的容量不限，則其分配方案數(shù)是

證明對n個球按分類情況分別考慮如下：對1k1：

k1個1類中每類1個球，這相當于將k1個不同的球分配給m個不同的盒子，由命題2的推論3知其分配方案數(shù)是

對2k2：k2個2類中每類2個球，這每類中的2個相同的球分配給m個不同的盒子，由命題1的推論2知其分配方案數(shù)是 。因共有k2個2類，類不同，球不同，故共有種分配方案；

…

對sks：ks個s類中每類s個球，這每類中的s個相同的球分配給m個不同的盒子，由命題1的推論2知其分配方案數(shù)是 因共有ks個s類，類不同，球不相同，故共有 種分配方案。

以上各種情況中，不同型的類間球均不相同，因此，不同情況間分配方案彼此無關。故由乘法原理可知，滿足命題條件的全部分配方案數(shù)為3.6.2盒子相同的分配問題

命題4

n個不同的球，m個相同的盒子，各盒非空，則其分配方案數(shù)是Snm。

推論

n個不同的球，m個相同的盒子，若各盒容量無限制，則分配方案數(shù)是

命題5

n個相同的球，m個相同的盒子，各盒非空，則其分配序列的生成函數(shù)是分配方案數(shù)是G(t)展開式中tn的系數(shù)。命題5相當于將整數(shù)n拆分成m部分的無序拆分，n≥m。(其證明參見隨后幾節(jié)。)

命題6

n個不同的球，m個相同的盒子，其分配序列的生成函數(shù)為分配方案數(shù)是G(t)展開式中tn的系數(shù)。命題6相當于將整數(shù)n拆分成k部分的無序拆分，

k=1,2,…,m。表3.6.1分配問題的幾種常見解決方案3.7整數(shù)n分為m個類的（無序）拆分數(shù)Pmn

定義1

整數(shù)（無序）拆分是指把整數(shù)分解成若干整數(shù)的和，若各部分不允許出現(xiàn)0值時，則稱各部分為類。整數(shù)（無序）拆分的組合學意義相當于把n個無區(qū)別的球放入若干相同的盒子的放法（各盒子中可放入t個球,1≤t≤n）；或者將其看作n元集X的劃分（無空盒子）的型，每個型對應于適合條件：及a1≥a2≥a3≥…≥am≥1的一個m元組(α1,α2,…,αm)。該m元組通常就稱為整數(shù)n的一個拆分。整數(shù)n分成恰有m個類（或稱非零部分）的拆分個數(shù)，記作Pmn。例如：整數(shù)n

拆分方式 拆分個數(shù)

2 2,1+13,3,2+1,1+1+14,4,3+1,2+22+1+1,1+1+1+1命題1遞歸關系:

證明只證第一式。設E是將n分成不多于k個類的拆分的集合。屬于E的每個拆分可看成是一個k元組（其分量用0補足k位）。在E上定義映射φ,φ(a)=a′。

a=(a1,a2,…,am,0,0,…,0)

→a′=(a1+1,a2+1,…,am+1,1,1,…,1)

在此映射下，E被映入將n+k分成恰有k個類的拆分的集合E′。因此（1）（2）對a′∈E′

a∈E

使φ(a)=a′可見,φ為一雙射函數(shù)。因此第二個公式直接從定義可得。推論注意到j＞n時有Pjn=0,故對k＞n有利用命題1及其推論給出的公式，可遞歸地推算Pmn如下：Pmn

m=123456

n=11

211

3111

41211

512211

6133211

·

求拆分三角的算法:

№1定義數(shù)組P=(1：n,1：n);

№2對k=1,n,做

P(k,1)

1;P(k,k)

1;

№3打印P（1，1）；打印P（2，1），

P（2，2）；

№4對i=3,n,做

№4.1對j=2,i-1,做

S

0;n1

i-j;n2

min(j,n1);

對t=1,n2,S

S+P(n1,t);

P(i,j)

S;

№4.2對j=2,i，做按行打印P(i,j)；

№5結束。

命題2

n分成k個類的拆分的個數(shù)，等于n分成以k為最大類的拆分的個數(shù)。例如，當n=6時，以3作為最大類的拆分有3個:3+1+1+1，3+2+1，3+3而分成3個類的拆分也有3個：4+1+1，3+2+1，2+2+2

證明考慮一個拆分，例如5+4+1+1，并構作一個相應的圖（稱為Ferrer圖解，見圖3.7.1），在圖中每個類均表示成一行小方塊，每行的方塊數(shù)等于類本身的數(shù)目，考慮到拆分元組的分量由左向右成一遞減序列，故對應的Ferrer圖從上而下，各行方塊數(shù)也自然呈遞減數(shù)列。圖3.7.15+4+1+1對應的Ferrer圖

定義a*=(a*1,a*2,…,a*a1)為a=(a1,a2,…,ak)的共軛拆分，其中a*1是a的基數(shù)不小于i的類的個數(shù)。上例中，不小于4的類有4個，故a*1=4;5,4都是不小于2、3及4的類，故a*2=a*3=a*4=2;又不小于5的類只有5，即a*5=1。從而共軛于5+4+1+1的拆分是4+2+2+2+1。與共軛拆分對應的Ferrer圖顯見可由原拆分的Ferrer圖繞對角線旋轉而得。易證由n的拆分的集合E到共軛拆分的集合E*間存在一雙射函數(shù)。與此同時，也建立了n分為以k為最大類的拆分的集合與n分為k個類的拆分的集合間的雙射函數(shù)。

定義2

若n的一個拆分的Ferrer圖像與它的共軛拆分的Ferrer圖像完全相同，則稱該拆分是自共軛拆分。

命題3

n的自共軛拆分的個數(shù)等于n分成各類都不相等且都是奇數(shù)的拆分的個數(shù)。

證明設 ,其中n1＞n2＞…＞nk。顯見這是一個把n分成各類都不相同且都是奇數(shù)的拆分，對應的Ferrer圖像的第i行有2ni+1個方格。構造一新的Ferrer圖像，使其第i行及第i列都是ni+1個方格。注意到交叉處的方格重合，故這恰用掉原Ferrer圖像的第i行的2ni+1個方格。而新構造的Ferrer圖像以對角線為軸線對稱，即對應的拆分是自共軛的。反之，對任一自共軛拆分，用其Ferrer圖像中第i行及第j列的全部方格（共2ni+1個）作為新構造的Ferrer圖像的第i行，這新得到的圖像對應的拆分又是n分成各類都不相等且都是奇數(shù)的拆分。以上討論建立了兩種拆分間的雙射函數(shù)。

命題4

n分成各類互不相同的拆分的個數(shù)，等于n分成各類都是奇數(shù)的拆分的個數(shù)。

證明設 ，其中ni為奇數(shù)，ri為ni的重復次數(shù)。注意到rt可表示為斷言n=b020n1+b121n1+…+b020n2+b121n2+…

+b020ni+b121ni+…+b020nj+b121nj+…中取掉0項（bk=0），就構成n的各類互不相等的拆分。事實上

若s=t，顯見有ni≠nj；若s≠t（不妨設t＞s）,但ni=nj2t-s，這導致ni為偶數(shù)，與題設矛盾，故斷言為真。又上述構造過程的逆也成立。這就建立了兩種拆分間的雙射函數(shù)。

命題5

設Qn是n分為偶數(shù)個互不相等的類的拆分類,Qn′是n分為奇數(shù)個互不相等的類的拆分數(shù)，則

證明考慮把n分成奇數(shù)個互不相等的類的一個拆分：在該拆分的Ferrer圖中，用S表示最底層方塊的集合,用E表示最右邊45°線上的方塊集合（S和E有可能只包含同一方塊）,參見圖3.7.2。如果|S|≤|E|，則把S中的方塊移到前|S|行的最右端，得到圖3.7.3所示的新拆分。圖3.7.2奇數(shù)個類，|S|≤|E|圖3.7.3偶數(shù)個類，|S|＞|E|

若原來就是|S|>|E|，則把集合E中的全部方塊移到最底層，從而得一偶數(shù)個互不相等類的新拆分（且|S|≥|E|）。這種操作手續(xù)除以下兩種例外總是可行的。（1）S與E相交且|S|=|E|：S不能移到右方；（2）S與E相交且|S|=|E|+1：E無法移到下方。圖3.7.4兩種例外情況

在以上兩種情形下，令|E|=k，ε=0(圖3.7.4（i）的情形）或ε=1（圖3.7.4（ii）的情形）,

除去n滿足上式的情形外，其余的類不等奇拆分與類不等偶拆分間形成一雙射函數(shù)。3.8n的拆分數(shù)Pn的生成函數(shù)命題1

n的拆分數(shù)Pn的生成函數(shù)是證明只需證事實上，當|x|<1時，有

在xn的系數(shù)中，第一項確定n的一個拆分，即1+1+…+1+2+2+…+2+…+k+k+…+k=n

λ1

λ2

λk

最后，取a1=a2=…=1，即得上述公式。命題2Pnm的生成函數(shù)是命題3

n分成僅由奇數(shù)類構成的拆分數(shù)的生成函數(shù)是

命題4

n分成各類互不相等的拆分數(shù)的生成函數(shù)是G4(x)=(1+x)(1+x2)(1+x3)…

命題5

n分成互不相等的奇數(shù)類的拆分數(shù)的生成函數(shù)是命題6

G3(x)=G4(x)。(3.7節(jié)命題4)

證明事實上，命題7（Euler等式）(1-x)(1-x2)(1-x3)…=1+∑φ(n)xn=1-x-x2+x5+…是{φ(n)}的生成函數(shù)，其中證明由3.7節(jié)命題5，上述等式的展開式中，xn的系數(shù)顯然等于

例1

有1、2、3、4克的砝碼各一枚，問能稱出哪幾種重量？對能稱出的重量有幾種可稱量方案？

解

從G(x)展開式中x的冪次知，可稱出1~10克的重量，系數(shù)即為對應的稱量方案數(shù)。如對2x5項，即稱量5克的方案有兩種： 5=3+2=4+1

同樣，有

6=1+2+3=4+2，10=1+2+3+4

故稱出6克的方案數(shù)有兩種，稱出10克的方案數(shù)是唯一的。

例2

求用1角，2角，3角的郵票貼出不同數(shù)值的方案數(shù)。

解因郵票允許重復，故生成函數(shù)為

以x4為例，其系數(shù)為4，即4拆分成1、2、3之和的拆分數(shù)為4，拆分方案為4=1+1+1+1，4=1+1+2，4=2+2，4=1+3

例3

若有1克的砝碼3枚，2克的砝碼4枚，4克的砝碼2枚。問能稱出哪些重量？有幾種方案？解G(x)=(1+x+x2+x3)(1+x2+x4+x6+x8)(1+x4+x8)=(1+x+x2+2x3+2x4+2x5+2x6+2x7+2x8+2x9+x10+x11)

·(1+x4+x8)

=1+x+2x2+2x3+3x4+3x5+4x6+4x7+5x8+5x9+5x10+5x11

+4x12+4x13+3x14+3x15+2x16+2x17+x18+x19

觀察展開式各項中x的冪次及其系數(shù)即知答案。

例4

整數(shù)n拆分成1，2，3，…,m的和，并允許重復，求其生成函數(shù)。若其中m至少出現(xiàn)一次，其生成函數(shù)如何？

解當n允許重復地拆分成1，2，…，m的和時，其生成函數(shù)若拆分中m至少出現(xiàn)一次，其生成函數(shù)顯見G2(x)=G1(x)-(1-xm)·G1(x)=xm·G1(x)其組合意義是：n拆分成1,2,…,m的和的拆分數(shù)，減去n拆分成1,2,…,m-1的和的拆分數(shù)，即為至少出現(xiàn)一個m的拆分數(shù)。

例5

設有1、2、4、8、16、32克砝碼各一枚，問能稱出哪些重量？分別有幾種方案？

解

由生成函數(shù)知，用給定的砝碼能稱出從1克到63克的各種重量，且其方案都是唯一的。3.9整數(shù)n分為以h為最小類的拆分數(shù)

以Pn表示n的拆分數(shù)；Pmn表示n分成m個類的拆分數(shù)；Pn,h表示n分成以h為最小類的拆分數(shù)；Pmn,h表示n分成m個類且以h為最小類的拆分數(shù)。則顯見有

命題1

例考慮把6分成m個類，并以h為最小類的拆分。各拆分可用三元樹結構存貯,如圖3.9.1所示。圖3.9.1三元樹結構n-m=(a1-1)+(a2-1)+…+(am-1-1)+(h-1)而當h=1時，拆分n=a1+a2+…+am聯(lián)系著拆分n-1=a1+a2+…+am-1

命題2

當h＞1時 當h=1時，。

證明設h＞1，則適合a1≥a2≥…≥am=h的每個拆分n=a1+a2+…+am就聯(lián)系著如下的拆分：命題3Pn,h=Pn-h,h+Pn-h,h+1+…證明因為n=(n-h)+h,所以命題4

遞歸關系:當h＞1時當h=1時證明設h＞1，由命題3比較命題3，可得Pn,h=Pn-1,h-1-Pn-h,h-1