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

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

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

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

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

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

3.6分配問(wèn)題

3.7整數(shù)n分為m個(gè)類的(無(wú)序)拆分?jǐn)?shù)Pmn

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

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

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

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

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

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

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

命題1

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

證明令f(n,k)表示Zn={1,2,…,n}中不含相繼整數(shù)的k元子集的個(gè)數(shù)。設(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}之間構(gòu)成一雙射函數(shù)。注意到j(luò)1=i1-1≥0∧jk=ik-k≤n-k

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

命題2

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

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

(3.1.5)

(2)證明注意到對(duì)任一級(jí)數(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）直接由遞推關(guān)系式（3.1.1）不難推得(3.1.7)(3.1.8)·

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

F0

1;F1

1；№3對(duì)k=0,n/2

打印F0,F1；

F0

F0+F1;F1

F1+F0;

№4結(jié)束?！?/p>

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

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

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

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

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

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

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

可證，形式冪級(jí)數(shù)的形式導(dǎo)數(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

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

定義3

設(shè)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

設(shè)則(2)證明

據(jù)假設(shè)知例2設(shè)

(3)證明由假設(shè)

等式左端相加,顯見(jiàn)為 。等式右端相加,得故例3

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

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

例5

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

與組合問(wèn)題有關(guān)的計(jì)數(shù)常使用尋常生成函數(shù)。

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

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

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

推論1

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

推論2

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

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

推論3

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

推論4

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

推論5

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

推論6

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

推論7

設(shè)多重集S={r1·e1,r2·e2,…,rm·em}，且r1+r2+…+rm=n，則S中的每個(gè)元素ei至少出現(xiàn)ki(i=1,2,…,m)次的r可重組合數(shù)cr對(duì)應(yīng)序列{cr}的生成函數(shù)為其組合數(shù)cr為G(x)展開(kāi)式中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è)不定方程 的解組數(shù)目為ck，本例中m=4,k=20。注意到對(duì)ki(i=1,2,3,4)的限制，序列{ck}對(duì)應(yīng)的生成函數(shù)為G(x)=(1+x2+x4)(x+x3+x5)(x6+x7)(x8+x9)由G(x)展開(kāi)式中x20的系數(shù)知題給不定方程解組數(shù)目為c20=6。

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

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

例3

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

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

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

例4

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

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

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

1：一個(gè)球都不取，僅有一種方案；

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

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

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

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

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

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

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

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

例6

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

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

解法1

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

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

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

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

命題1

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

由多項(xiàng)式系數(shù)的組合學(xué)意義知，(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

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

推論2

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

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

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

解

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

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

推論3

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

推論4

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

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

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

上式之Pk可以簡(jiǎn)寫(xiě)成

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

B(x)=ebx,bi≡bi

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

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

證明記Ef(x)=f(x+1)為移位算子，If(x)=f(x)為恒等算子，Δf(x)=f(x+1)-f(x)為差分算子，不難證得Δ=E-I。于是由此可見(jiàn)此式兩邊算子施于f(1)，即得所證。Bernoulli求和公式一般用于f(x)為多項(xiàng)式的場(chǎng)合，此時(shí)f(x)的高階差分等于零。如對(duì)f(x)=x3,逐次計(jì)算Δ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應(yīng)用求和公式即得

推論5

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

推論6

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

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

例3

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

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

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

例6

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

解令ak表示這種染色數(shù)，并定義a0為1。則ak等于三色多重集（每種顏色重復(fù)次數(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可見(jiàn),［x］n是第一類Stirling數(shù)skn的尋常生成函數(shù)，［x］n是|skn|的尋常函數(shù)。兩類Stirling數(shù)是溝通xn,［x］n,［x］n這三種首項(xiàng)為1的多項(xiàng)式的橋梁。3.5Catalan數(shù)列與Stirling數(shù)列的生成函數(shù)

定義1

空集或有限點(diǎn)集T，滿足：

(1)有一特定結(jié)點(diǎn)r稱為“根”；

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

二叉樹(shù)（或二元樹(shù)）的計(jì)數(shù)問(wèn)題。例如，3個(gè)結(jié)點(diǎn)可有5棵不同的二叉樹(shù),如圖3.5.1所示。圖3.5.1二叉樹(shù)

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

例2

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

解令hn表示將n+1(n≥2)邊凸多邊形進(jìn)行三角形剖分的方案數(shù)，則當(dāng)n=1時(shí)，h1=1，當(dāng)n≥3時(shí)，任取多邊形一邊記作e，其兩端點(diǎn)一端記為v1，一端記為vn+1，余點(diǎn)依次相鄰標(biāo)記如圖3.5.2所示?，F(xiàn)以v1，vn+1及任意頂點(diǎn)vk+1(k=1,2,…,n-1)構(gòu)作一三角形，該三角形將凸多邊形分為F1,F2兩個(gè)區(qū)域。其中，F(xiàn)1由k+1邊凸多邊形圍成，其三角形剖分方案數(shù)為hk，F(xiàn)2由n-k+1邊凸多邊形圍成，其三角形剖分方案數(shù)為hn-k，由乘法原理知 。易證當(dāng)n=5時(shí)，可求得圖3.5.2余點(diǎn)依次相鄰標(biāo)記圖3.5.3凸6邊形的14個(gè)剖分方案3.5.2Stirling數(shù)列的生成函數(shù)為醒目起見(jiàn)，把第一類與第二類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!,并對(duì)n求和有（3.5.1）式（3.5.1）若記,則故（3.5.1）式可改寫(xiě)如下：因?yàn)镾0(t)=1，Sk(0)=0，所以這就證明了序列{S1(n,k)}的指數(shù)型生成函數(shù)為(2)據(jù)2.10節(jié)中命題3有

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

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

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

例如，對(duì)S2(n,k)，n=5，k=3，n-k=2，n1+n2+…+nk=2的所有有序非負(fù)整數(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ù)學(xué)中三種典型的數(shù)列，實(shí)際應(yīng)用中許多組合計(jì)數(shù)結(jié)果都與它們相同或相似。3.6分配問(wèn)題3.6.1盒子不相同的分配問(wèn)題命題1

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

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

…

xi個(gè)球放入ei，即ei被選取xi次，xi≤ni；

…

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

e2…e2

…

ei…ei

…

em…em

x1個(gè)x2個(gè)xi個(gè)xm個(gè)

且x1+x2+…+xm=n,0≤xi≤ni,i=1,2,…,m。以上放法僅與ei的出現(xiàn)次數(shù)有關(guān)，而不考慮ei的順序。因此，滿足命題條件的分配問(wèn)題可歸結(jié)為多重集S={n1·e1,n2·e2,…,ni·ei,…,nm·em}的n-可重組合問(wè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

若各盒容量限制為非負(fù)偶數(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個(gè)不同的球，m個(gè)不同的盒子，各盒的容量ni(ni≥0,i=1,2,…,m)。則其分配序列的指數(shù)型生成函數(shù)為

證明將n個(gè)不同的球放入m個(gè)不同的盒子（盒子加有編號(hào)），每次不同的放法可按如下方式記錄。用b1,b2,…,bn表示n個(gè)不同的球，用e1,e2,…,em表示m個(gè)不同的盒子。b1b2…bn——n個(gè)不同的球已按某種順序排好j1j2…jn——各球所占盒子的編號(hào)(反映于下標(biāo))其中ji∈{1,2,…,m}(i=1,2,…,n)。對(duì)球的分配不同，排列j1j2…jn也就不同；反之，不同的排列j1j2…jn對(duì)應(yīng)了球的不同分配。而這種排列正是m個(gè)元素的n-可重排列。其中每個(gè)元素的重復(fù)次數(shù)分別是n1,n2,…,nm。從而問(wèn)題歸結(jié)為集合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ù)為顯見(jiàn)其分配方案數(shù)為mn。

推論4

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

推論5

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

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

把剩余的n-k個(gè)球不加限制地放到m-r個(gè)盒中，據(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個(gè)以上的空盒，則其分配方案數(shù)為證明空盒數(shù)s≥r，與非空盒數(shù)m-s取法對(duì)應(yīng)羅列如下：空盒數(shù)s=r,r+1,…,m-1，m

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

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

（2）

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

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

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

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

·1+k2

·2+…+ks

·s

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

命題3

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

證明對(duì)n個(gè)球按分類情況分別考慮如下：對(duì)1k1：

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

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

…

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

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

命題4

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

推論

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

命題5

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

命題6

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

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

定義1

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

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

2 2,1+13,3,2+1,1+1+14,4,3+1,2+22+1+1,1+1+1+1命題1遞歸關(guān)系:

證明只證第一式。設(shè)E是將n分成不多于k個(gè)類的拆分的集合。屬于E的每個(gè)拆分可看成是一個(gè)k元組（其分量用0補(bǔ)足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個(gè)類的拆分的集合E′。因此（1）（2）對(duì)a′∈E′

a∈E

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

m=123456

n=11

211

3111

41211

512211

6133211

·

求拆分三角的算法:

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

№2對(duì)k=1,n,做

P(k,1)

1;P(k,k)

1;

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

P（2，2）；

№4對(duì)i=3,n,做

№4.1對(duì)j=2,i-1,做

S

0;n1

i-j;n2

min(j,n1);

對(duì)t=1,n2,S

S+P(n1,t);

P(i,j)

S;

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

№5結(jié)束。

命題2

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

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

定義a*=(a*1,a*2,…,a*a1)為a=(a1,a2,…,ak)的共軛拆分，其中a*1是a的基數(shù)不小于i的類的個(gè)數(shù)。上例中，不小于4的類有4個(gè)，故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。與共軛拆分對(duì)應(yīng)的Ferrer圖顯見(jiàn)可由原拆分的Ferrer圖繞對(duì)角線旋轉(zhuǎn)而得。易證由n的拆分的集合E到共軛拆分的集合E*間存在一雙射函數(shù)。與此同時(shí)，也建立了n分為以k為最大類的拆分的集合與n分為k個(gè)類的拆分的集合間的雙射函數(shù)。

定義2

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

命題3

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

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

命題4

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

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

+b020ni+b121ni+…+b020nj+b121nj+…中取掉0項(xiàng)（bk=0），就構(gòu)成n的各類互不相等的拆分。事實(shí)上

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

命題5

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

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

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

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

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

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

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

λ1

λ2

λk

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

n分成僅由奇數(shù)類構(gòu)成的拆分?jǐn)?shù)的生成函數(shù)是

命題4

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

命題5

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

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

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

例1

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

解

從G(x)展開(kāi)式中x的冪次知，可稱出1~10克的重量，系數(shù)即為對(duì)應(yīng)的稱量方案數(shù)。如對(duì)2x5項(xiàng)，即稱量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ù)。

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

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

例3

若有1克的砝碼3枚，2克的砝碼4枚，4克的砝碼2枚。問(wèn)能稱出哪些重量？有幾種方案？解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

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

例4

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

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

例5

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

解

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

以Pn表示n的拆分?jǐn)?shù)；Pmn表示n分成m個(gè)類的拆分?jǐn)?shù)；Pn,h表示n分成以h為最小類的拆分?jǐn)?shù)；Pmn,h表示n分成m個(gè)類且以h為最小類的拆分?jǐn)?shù)。則顯見(jiàn)有

命題1

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

命題2

當(dāng)h＞1時(shí) 當(dāng)h=1時(shí)，。

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

遞歸關(guān)系:當(dāng)h＞1時(shí)當(dāng)h=1時(shí)證明設(shè)h＞1，由命題3比較命題3，可得Pn,h=Pn-1,h-1-Pn-h,h-1