組合數(shù)學(xué)（第二版）母函數(shù)及其應(yīng)用

母函數(shù)及其應(yīng)用2.1母函數(shù)2.2母函數(shù)的性質(zhì)2.3指數(shù)型母函數(shù)2.4正整數(shù)的分拆

在第一章中,已經(jīng)解決了部分排列組合方案的計(jì)數(shù)問題.但對(duì)于不盡相異元素的部分排列和組合,用第一章的方法是比較麻煩的(參見表2.0.1).若改用母函數(shù)方法,問題將顯得容易多了.其次,在求解遞推關(guān)系的解、整數(shù)分拆以及證明組合恒等式時(shí),母函數(shù)方法是一種非常重要的手段.

2.1母函數(shù)

定義2.1.1對(duì)于數(shù)列{an},稱無窮級(jí)數(shù)為該數(shù)列的普通型母函數(shù),簡(jiǎn)稱普母函數(shù)或母函數(shù),同時(shí)稱{an}為G(x)的生成數(shù)列.

【例2.1.1】有限數(shù)列C(n,r),r=0,1,2,…,n的普母函數(shù)是(1+x)n.

【例2.1.2】無限數(shù)列{1,1,…,1,…}的普母函數(shù)是

說明

(1)an的非零值可以為有限個(gè)或無限個(gè);

(2)數(shù)列{an}與母函數(shù)一一對(duì)應(yīng),即給定數(shù)列便得知它的母函數(shù);反之,求得母函數(shù)則數(shù)列也隨之而定;

(3)這里將母函數(shù)只看作一個(gè)形式函數(shù),目的是利用其有關(guān)運(yùn)算性質(zhì)完成計(jì)數(shù)問題,故不考慮“收斂問題”,即始終認(rèn)為它是收斂的,而且是可“逐項(xiàng)微分”和“逐項(xiàng)積分”的.

表2.1.1是一些常用的母函數(shù),它們的證明只要利用解析函數(shù)展開成冪級(jí)數(shù)的方法即可得到.

定理2.1.1組合的母函數(shù):設(shè)S={n1·e1,n2·e2,…,nm·em},且n1+n2+…+nm=n,則S的r可重組合的母函數(shù)為

其中,r可重組合數(shù)為xr之系數(shù)ar,r=0,1,2,…,n.

定理2.1.1的最大優(yōu)點(diǎn)在于:

(1)將無重組合與重復(fù)組合統(tǒng)一起來處理;

(2)使處理可重組合的枚舉問題變得非常簡(jiǎn)單.

推論6設(shè)S={n1·e1,n2·e2,…,nm·em},且n1+n2+…+nm=n,要求元素ei至少出現(xiàn)ki

次,則S的r可重組合的母函數(shù)為

【例2.1.3】設(shè)有2個(gè)紅球,1個(gè)黑球,1個(gè)白球,問:

(1)共有多少種不同的選取方法.試加以枚舉.

(2)若每次從中任取3個(gè),有多少種不同的取法.

【例2.1.4】有18張戲票分給甲、乙、丙、丁4個(gè)班(不考慮座位號(hào)),其中,甲、乙兩班最少1張,甲班最多5張,乙班最多6張;丙班最少2張,最多7張;丁班最少4張,最多10張.可有多少種不同的分配方案?

【例2.1.5】從n雙互相不同的鞋中取出r只(r≤n),要求其中沒有任何兩只是成對(duì)的,共有多少種不同的取法?

這實(shí)際上是一種二次分配問題.即將r個(gè)相同的球放入n個(gè)不同的盒子,第i個(gè)盒子最多放ti個(gè)球,而該盒子又分為ni個(gè)相異的格子,每個(gè)格子最多只能放一個(gè)球,故還需要進(jìn)行二次分配.如果第i個(gè)盒子中放進(jìn)了ri個(gè)球,那么,對(duì)該盒子而言,二次分配時(shí)的方案數(shù)為.

例如,設(shè)甲、乙、丙3個(gè)班分別有30、28、22名學(xué)生,現(xiàn)把5本相同的書分給甲、乙、丙3個(gè)班,再發(fā)到個(gè)人手上,每人最多發(fā)一本.考慮將分給某班的某本書發(fā)給該班的同學(xué)A與將其發(fā)給同學(xué)B被認(rèn)為是不同的分法,而且甲、乙兩班最少1本,甲班最多5本,乙班最多6本,丙班最少2本,最多9本,問共有多少種不同的分配方案.

【例2.1.6】甲、乙、丙3人把n(n≥3)本相同的書搬到辦公室,要求甲和乙搬的本數(shù)一樣多,問共有多少種分配的方法.

解本問題即組合問題:從集合S={∞·e1,∞·e2,∞·e3}中可重復(fù)地選取n個(gè)元素,但要求e1與e2的個(gè)數(shù)一樣多,求不同的選取方案數(shù).

設(shè)想當(dāng)n=1時(shí),其分法只有1種,即甲和乙都分0本,丙分1本.當(dāng)n=2時(shí),其分法有2種:甲和乙都分0本(丙分2本)或甲和乙都分1本(丙分0本).當(dāng)n=3時(shí),也是2種分法.

當(dāng)n=4或5時(shí),分法為3種:即甲和乙都分0本、1本或2本

一般情形,甲分k本,乙也必須分k本,丙就只能分n-2k本.考慮將分配過程分為3步實(shí)現(xiàn).第一步先選出2k本書,第二步將選出的書分給甲、乙各一半,第三步將剩下的書全分給丙.由于第二步屬于二次分配,且只有一種分法,故可以將甲和乙視為一人,從而把問題轉(zhuǎn)換為:將n本相同的書分給兩個(gè)人,其中一人分得偶數(shù)本,求分配方法數(shù).顯然,本問題的母函數(shù)為

【例2.1.7】證明組合等式

證本例是母函數(shù)的另一種應(yīng)用.意圖說明普母函數(shù)除了能用于解決組合的求值問題之外,還能用來證明很多組合等式.

(3)因?yàn)?/p>

2.2母函數(shù)的性質(zhì)

由于母函數(shù)與它的生成數(shù)列之間是一一對(duì)應(yīng)的,因此,若兩個(gè)母函數(shù)之間存在某種關(guān)系,則對(duì)應(yīng)的生成數(shù)列之間也必然存在相應(yīng)的關(guān)系.反之亦然.利用這類對(duì)應(yīng)關(guān)系,常常能幫助我們構(gòu)造出某些指定數(shù)列的母函數(shù)的有限封閉形式.特別地,還能得到一些求和的新方法.設(shè)數(shù)列{ak}、{bk}、{ck}的母函數(shù)分別為A(x)、B(x)、C(x),且都可逐項(xiàng)微分和積分

2.3指數(shù)型母函數(shù)

但是,注意到n集的r無重排列數(shù)和r無重組合數(shù)之間有如下關(guān)系:

從而有

定義2.3.1對(duì)于數(shù)列{ak}={a0,a1,a2,…},把形式冪級(jí)數(shù)

稱為數(shù)列{ak}的指數(shù)型母函數(shù),簡(jiǎn)稱為指母函數(shù),而數(shù)列{ak}則稱為指母函數(shù)Ge(x)的生成序列.

說明

(1)ak的非零值可以為有限個(gè)或無限個(gè).

(2)數(shù)列{ak}與母函數(shù)一一對(duì)應(yīng),即給定數(shù)列便得知它的指母函數(shù);反之,求得指母函數(shù)則數(shù)列也隨之而定.

(3)這里將指母函數(shù)只看做一個(gè)形式函數(shù),目的是利用其有關(guān)運(yùn)算性質(zhì)完成計(jì)數(shù)問題,故不考慮“收斂問題”,即始終認(rèn)為它是收斂的,而且是可“逐項(xiàng)微分”和“逐項(xiàng)積分”的.

(4)相應(yīng)于同一數(shù)列{ak},一般G(x)≠Ge(x).

定理2.3.1設(shè)重集S={n1·e1,n2·e2,…,nm·em},且n1+n2+…+nm=n,則S的r可重排列的指母函數(shù)為

其中,r可重排列數(shù)為xr/r!之系數(shù)ar,r=0,1,2,…,n.

【例2.3.1】盒中有3個(gè)紅球,2個(gè)黃球,3個(gè)藍(lán)球,從中取4個(gè)球,排成一列,問共有多少種不同排列方案.

所以,從中取4個(gè)球的排列方案有70種.

類似于組合問題,令

即對(duì)全部排列方案進(jìn)行分類枚舉.可以看出,取1個(gè)球的3種排列方案為紅、黃、藍(lán)各分別取1個(gè).取2個(gè)球的9種排列方案為:紅紅、黃黃、藍(lán)藍(lán)、紅黃、黃紅、紅藍(lán)、藍(lán)紅、黃藍(lán)、藍(lán)黃.其它情形依此類推.

這里需要說明的是:

(1)在例2.1.3中,利用普母函數(shù)可以將組合的每一種情況都枚舉出來,但是對(duì)排列問題,指母函數(shù)卻做不到,只能對(duì)排列進(jìn)行分類枚舉.正如例2.3.1這樣,項(xiàng)ryb的系數(shù)6說明紅、藍(lán)、黃球各取一個(gè)時(shí),有6種排列方案,但每一種方案具體是什么,則無法表示出來了.

推論1若S={e1,e2,…,en},則r無重排列的指母函數(shù)為

推論2若S={∞·e1,∞·e2,…,∞·en},則r無限可重排列的指母函數(shù)為

排列數(shù)為nr

推論3

S={n1·e1,n2·e2,…,nm·em},元素ei至少取ki個(gè)(ki≥0),則有

推論4S={n1·e1,n2·e2,…,nm·em

},令r=n,即得全排列數(shù)

【例2.3.2】五個(gè)數(shù)字1,1,2,2,3能組成多少個(gè)四位數(shù)?

由a4=30知能組成30個(gè)四位數(shù).同時(shí)還知道能組成3個(gè)一位數(shù),8個(gè)兩位數(shù),18個(gè)三位數(shù)等.

【例2.3.3】求1,3,5,7,9五個(gè)數(shù)字組成的n位數(shù)的個(gè)數(shù)(每個(gè)數(shù)字可重復(fù)出現(xiàn)),要求其中3,7出現(xiàn)的次數(shù)為偶數(shù),1,5,9出現(xiàn)的次數(shù)不加限制.

【例2.3.4】把上例的條件改為要求1、3、7出現(xiàn)的次數(shù)一樣多,5和9出現(xiàn)的次數(shù)不加限制.求這樣的n位數(shù)的個(gè)數(shù).

解設(shè)滿足條件的數(shù)有bn個(gè),與例2.1.6的分配問題類似,即將n個(gè)不同的球放入標(biāo)號(hào)為1、3、5、7、9的5個(gè)盒子,其中盒子1、3、7中的球一樣多.考慮把此3個(gè)盒子視為一個(gè)大盒子,大盒子中分為3個(gè)小盒子.問題即轉(zhuǎn)化為將n個(gè)不同的球放入A、B、C這3個(gè)不同的盒子,其中盒子A里球的個(gè)數(shù)應(yīng)為3k(k≥0),且A中的球第二次被分到3個(gè)不同的小盒子中,每個(gè)盒子恰好放入k個(gè)球,有種分法.所以,本問題的指母函數(shù)為

【例2.3.5】在例2.1.5中,若把所取出的r只鞋再排成一列,問共有多少種結(jié)果.

解此問題即是從集合S={e11,e12,e21,e22,…,en1,en2}的n類共2n個(gè)元素中不重復(fù)地取出r個(gè)元素排成一列,且同一類元素ei1,ei2不能同時(shí)出現(xiàn)(1≤i≤n).因此,其r個(gè)元素?zé)o重排列的指母函數(shù)應(yīng)為

即不同的排列共有

從分配角度看問題,就是將r個(gè)不同的球放入n個(gè)不同的盒子,每個(gè)盒子最多放一個(gè)球,而且每個(gè)盒子中有兩個(gè)相異的格子,故還需要進(jìn)行二次分配.如果某個(gè)盒子中放進(jìn)一個(gè)球,那么,二次分配時(shí)有兩種可選的方案.

2.4正整數(shù)的分拆

定義2.4.1將一個(gè)正整數(shù)n分解成k個(gè)正整數(shù)之和稱該分解是n的一個(gè)k分拆,并稱ni

為分量.

此外,按照對(duì)諸ni

是否要考慮順序,將分拆分為兩類.例如5的兩個(gè)4分拆:

若考慮ni

間的順序,這兩個(gè)分拆被認(rèn)為是不同的,這樣的分拆稱為有序分拆.否則,不考慮順序,這時(shí)可把右端按大小重新排列且看作是同一分拆,稱為無序分拆.

2.4.1有序分拆

求n的k有序分拆的個(gè)數(shù),相當(dāng)于求一次不定方程(2.4.1)全體正整數(shù)解的組數(shù),可對(duì)每個(gè)分量ni加以條件限制,例如1≤ni≤ri(i=1,2,…,k),于是可得如下結(jié)果.

定理2.4.1對(duì)于n的k有序分拆

其k有序分拆數(shù)數(shù)列{qk(n)}的母函數(shù)是

推論若對(duì)n的k有序分拆的各分量ni

沒有限制,則其k有序分拆數(shù)數(shù)列{qk(n)}的母函數(shù)是且qk(n)=C(n-1,k-1).

2.4.2無序分拆

由前面的定義可以看出,在n的分拆中,如果不考慮各分量的順序,為討論方便起見,可把分拆后的各項(xiàng)數(shù)值從大到小加以排列,即有

滿足以上條件的每一組正整數(shù)解(n1,n2,…,nk)就代表了一個(gè)n的k無序分拆,簡(jiǎn)稱分拆,其分拆數(shù)記作pk(n),n1稱為最大分項(xiàng).

把n分拆為最大分項(xiàng)等于k,其分拆數(shù)相當(dāng)于求不定方程

的整數(shù)解的組數(shù).即整數(shù)n由1,2,…,k允許重復(fù)且k至少出現(xiàn)一次的所有(由條件式(2.4.4)限制的)組合數(shù),其母函數(shù)為

其中展開式中xn

的系數(shù)即為n的最大分項(xiàng)等于k的分拆個(gè)數(shù).

若最大分項(xiàng)小于或等于k,其分拆數(shù)相當(dāng)于解不定方程

其分拆數(shù)列的母函數(shù)為

其中展開式中xn

的系數(shù)即為n的最大分項(xiàng)不超過k的分拆個(gè)數(shù).

2.4.3弗雷斯(Ferrers)圖

一個(gè)從上而下的k層格子,設(shè)mi為第i層的格子數(shù),當(dāng)mi≥mi+1(i=1,2,…,n-1),即上層的格子數(shù)不少于下層的格子數(shù)時(shí),稱之為Ferrers圖.如圖2.4.1所示.圖2.4.1共軛Ferrers圖

Ferrers圖具有以下性質(zhì):

(1)每一層至少有一個(gè)格子;

(2)Ferrers圖與式(2.4.3)說明的無序分拆是一一對(duì)應(yīng)的,其中的對(duì)應(yīng)關(guān)系是:第1層的格子數(shù)對(duì)應(yīng)分項(xiàng)n1,第2層的格子數(shù)對(duì)應(yīng)分項(xiàng)n2,……,依此類推.圖2.4.1(a)就代表20的一種分拆,即20=7+5+5+2+1.

(3)將圖形“轉(zhuǎn)置”,即把行與列對(duì)調(diào)所得的圖仍然是Ferrers圖,稱為原Ferrers圖的共軛圖(圖2.4.1中的(b)是(a)的共軛圖),或者說這兩個(gè)圖是一對(duì)共軛的Ferrers圖.若某個(gè)Ferrers圖與其共軛圖形狀相同,則稱其是自共軛的.

定理2.4.2

(1)n的所有k分拆的個(gè)數(shù)等于把n分拆成最大分項(xiàng)等于k的所有分拆數(shù);

(2)把n分拆成最多不超過k個(gè)數(shù)之和的分拆數(shù)等于把n分拆成最大分項(xiàng)不超過k的所有分拆數(shù).

推論正整數(shù)n分拆成互不相同的若干個(gè)奇數(shù)的和的分拆數(shù),等于有n個(gè)格子的自共軛的Ferrers圖的個(gè)數(shù).

證設(shè)

構(gòu)造一Ferrers圖,其第一行、第一列都是n1+1個(gè)格子,對(duì)應(yīng)于2n1+1,第二行、第二列都是n2+1個(gè)格子,對(duì)應(yīng)于2n2+1,依此類推.由此所得的Ferrers圖是自共軛的.反過來也一樣.例如

對(duì)應(yīng)的Ferrers圖如圖2.4.2所示.圖2.4.2n分拆為不同的奇數(shù)及其對(duì)應(yīng)的自共軛的Ferrers圖

2.4.4分拆數(shù)的估計(jì)

對(duì)于n的k無序分拆,當(dāng)k任意時(shí)(k=1,2,…,n),n的所有分拆的個(gè)數(shù)稱作n的分拆數(shù),記作p(n),即

定理2.4.3正整數(shù)n的全部分拆總數(shù)數(shù)列{p(n)}的母函數(shù)是

當(dāng)n較大時(shí),計(jì)算p(n)是非常困難的,例如

下面給出p(n)的漸進(jìn)公式和估值不等式.

定理2.4.4關(guān)于p(n)的計(jì)算,有

其中[x]表示將x四舍五入取整.

定理2.4.5設(shè)函數(shù)Q(n,m)表示正整數(shù)n的最大分項(xiàng)n1≤m的所有分拆數(shù),則有

定理2.4.5實(shí)質(zhì)上是函數(shù)Q(n,m)的遞歸定義,其原因如下:

(1)顯然有Q(1,n)=Q(m,1)=1;

(2)因?yàn)樽畲蠓至縩1實(shí)際上不能大于n,故m>n時(shí),Q(n,m)=Q(n,n);

(3)由于在n的所有分拆中,其1分拆只有一個(gè),即n=n1,而其它的分拆都是n1≤n-1;

(4)因?yàn)閷?duì)于正整數(shù)n,最大分項(xiàng)為m的分拆數(shù)由以下兩部分組成:一個(gè)是以m作為第一分項(xiàng),其余分項(xiàng)之和等于n-m,且最大分項(xiàng)n2不超過m的分拆數(shù)Q(n-m,m);另一個(gè)是最大分項(xiàng)n1≤m-1的分拆數(shù)Q(n,m-1).

2.4.5應(yīng)用

【例2.4.1】設(shè)有1克、2克、3克、4克的砝碼各一枚,若要求各砝碼只能放在天平的一邊.問能稱出哪幾種重量?有哪幾種可能方案?

解這是典型的正整數(shù)分拆問題.比如說可以稱6克重的物品,使用的砝碼可以是1克、2克、3克的三個(gè)砝碼放在一起,也可以是2克和4克的兩個(gè)砝碼放在一起來稱.即當(dāng)最大分項(xiàng)不超過4時(shí),6的無序不重復(fù)分拆只有兩種

首先,將整數(shù)n分拆為最大分項(xiàng)不超