王中平

(重慶大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，重慶 401331)

?

生成函數(shù)在組合數(shù)學(xué)中的若干應(yīng)用*

王中平

(重慶大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，重慶 401331)

生成函數(shù)是組合數(shù)學(xué)中的一個重要理論工具，它在組合問題中的應(yīng)用既靈活又具有一定的廣泛性，它不僅可以用來推導(dǎo)或者證明各種有用的組合恒等式，還可以用來處理組合計數(shù)問題、整數(shù)分拆問題、遞推關(guān)系問題等。本文主要研究了生成函數(shù)在以上列舉的幾個典型的組合數(shù)學(xué)問題中的一些應(yīng)用，從中也能體現(xiàn)生成函數(shù)這一工具對我們處理組合數(shù)學(xué)問題的優(yōu)越性。

生成函數(shù)；組合恒等式；組合計數(shù)；整數(shù)分拆；遞推關(guān)系

1 生成函數(shù)相關(guān)介紹

生成函數(shù)又叫發(fā)生函數(shù)或者母函數(shù),它的提出巧妙地將離散數(shù)學(xué)與連續(xù)數(shù)學(xué)結(jié)合起來,為離散數(shù)學(xué)中特別是當中組合數(shù)學(xué)的許多問題提供了好的解決辦法,成為研究組合數(shù)學(xué)必不可少的工具之一。生成函數(shù)作為一種十分有用的方法，它的運用非常廣泛，它處理問題的思想也不復(fù)雜,其主要思路就是把離散的序列和相應(yīng)的冪級數(shù)聯(lián)系起來,通過對冪級數(shù)之間的運算，來得到相應(yīng)的離散序列之間的一些性質(zhì)及其相互關(guān)系等。

實際上，生成函數(shù)就是一種形式冪級數(shù)，所以有必要先來給出形式冪級數(shù)的定義：

定義1.1[1]形式冪級數(shù)是指形如

a0+a1x+a2x2+…

的表達式，其中的{an}是系數(shù)序列。

這里的形式冪級數(shù)的概念實質(zhì)上是二項式概念的推廣，并且當兩個形式冪級數(shù)的系數(shù)全部對應(yīng)相等時，就說這兩個形式冪級數(shù)相等。

下面我們給出發(fā)生函數(shù)的定義：

定義1.2[2]對于給定的實數(shù)或復(fù)數(shù)序列a0,a1,…,an,…,我們稱形式冪級數(shù)

為這個序列的生成函數(shù)，并且一般把這種形式的生成函數(shù)稱為普通型生成函數(shù)。

定義1.3[2]對于給定的實數(shù)或復(fù)數(shù)序列a0,a1,a2,…，an,…,我們稱形式冪級數(shù)

為序列{an}的指數(shù)型生成函數(shù)。

有時我們也將序列{an}的生成函數(shù)記為G{an}，并且上面定義中的序列{an}通常是由具有某種實際組合意義的正整數(shù)構(gòu)成。下面我們來介紹生成函數(shù)的重要運算性質(zhì)：

定理1.4[3]設(shè){ak},{bk}為兩個數(shù)列，則

(1)G{ak}±G{bk}=G{ak±bk}；

證明：

證畢。

一般來說, 普通型的生成函數(shù)比較適合處理組合數(shù)相關(guān)問題,指數(shù)型的生成函數(shù)比較適用于解決排列數(shù)相關(guān)問題，所以，我們在選用生成函數(shù)解決問題時,要根據(jù)所要處理的問題的特點和性質(zhì),有方向性地選擇某種類型的生成函數(shù)，以使問題更好地得到解決。

根據(jù)冪級數(shù)的性質(zhì),只要兩個冪級數(shù)的收斂半徑非零,就可以在某區(qū)間內(nèi)進行加、減、乘、除、求積分、求導(dǎo)等各種運算,而不需要去考慮級數(shù)的斂散性。因此,在后面的討論中,只要在某非零點收斂,我們就不再關(guān)心它的收斂域。

運用生成函數(shù)處理組合數(shù)學(xué)問題的一般思路可以簡要地概括為如下框圖：

由這個框圖可知,在運用生成函數(shù)處理問題時，需要解決以下兩個問題：

①如何由數(shù)列{an}求出其生成函數(shù)g(x)；

②怎樣把g(x)展開成所需要的級數(shù)，再通過對級數(shù)的運算來推得所要的結(jié)果。

2 生成函數(shù)在組合恒等式證明中的應(yīng)用

2.1 二項式系數(shù)恒等式的證明

二項式定理在組合數(shù)學(xué)中占有非常重要的地位，以二項展開式作為生成函數(shù)來推導(dǎo)或證明一些組合恒等式也是特別常見且重要的方法。其一般思路是，先觀察欲證恒等式兩邊的特點，然后構(gòu)造合適的生成函數(shù)，再通過比較等式兩端對應(yīng)項的系數(shù)，來得到要證的恒等式。

下面我們結(jié)合具體的例子來說明生成函數(shù)在證明二項式恒等式中的應(yīng)用：

例2.1： 求證：

析：觀察可知恒等式的左邊比較復(fù)雜，直接通過組合計數(shù)公式去化簡證明會有些困難。但是，通過觀察我們發(fā)現(xiàn)等式左端的規(guī)律性還是比較強，為此設(shè)法構(gòu)造以二項展開式為生成函數(shù)的函數(shù)模型，即設(shè)法構(gòu)造這樣的生成函數(shù)，它以等式左端作為確定項的系數(shù)，再對所構(gòu)造的生成函數(shù)進行化簡處理，看能否得到右端對應(yīng)的系數(shù)。

證明：我們構(gòu)造如下生成函數(shù)：

g(x)=(1+x)+2(1+x)2+3(1+x)3+…+n(1+x)n

兩端是同一生成函數(shù)對應(yīng)項的系數(shù)，所以即證得結(jié)論，證畢。

又如我們可以用生成函數(shù)證明Vandermonde恒等式。

例2.2: (Vandermonde恒等式)設(shè)α，β為非零實數(shù)，則

由結(jié)論的唯一性知，

證畢。

同理，還可以證明對任意的正整數(shù)p,q有如下組合恒等式：

小結(jié)：以二項展開式作為生成函數(shù)來證明組合恒等式，其方法是適當?shù)剡x取兩個或多個二項式，使它們的乘積中對應(yīng)項的系數(shù)恰為所要證的恒等式，或者經(jīng)過適當?shù)幕喬幚淼玫接C的恒等式。以二項展開式作為生成函數(shù)來證明一些組合恒等式是最為基礎(chǔ)的一類用生成函數(shù)證明組合恒等式的方法。

2.2 整數(shù)分拆恒等式的證明

在18世紀，Euler在研究正整數(shù)的分拆時首先使用了生成函數(shù)這一工具。19世紀初，Laplace在研究概率問題時，使得生成函數(shù)理論得到進一步發(fā)展與豐富。我們知道在整數(shù)分拆中也有許多恒等式，比如Euler恒等式、Rogers-Ramamujan 恒等式等，這些都是非常經(jīng)典的恒等式，此外還有很多各種各樣的分拆恒等式，它們在分拆理論中扮演著重要的角色，這些恒等式中的許多都可以用生成函數(shù)的方法來研究和證明。

下面先來介紹幾個有關(guān)整數(shù)分拆的生成函數(shù)理論：

定理2.1[4]假設(shè)有p種類型的對象，且每一類型i有ni個不可區(qū)分的對象，i=1，2，…，p.假如每一種類型的對象可以選擇任意多個，則選取n個不同的對象的方法總數(shù)由如下生成函數(shù)中的的xn系數(shù)給出：

g(x)=(1+x+x2+…+xn1)(1+x+x2+…+xn2)…(1+x+x2+…+xnp)

定理2.2[4]將正整數(shù)n分拆成若干個正整數(shù)的和，分拆的個數(shù)用p(n)表示，若將n分拆為1，2，3…的和，且每部分都不重復(fù)的方案數(shù)為an的生成函數(shù)可寫成：

g(x)=(1+x)(1+x2)(1+x3)…

若將n分拆為1，2，3，%…的和，允許分拆中各部分重復(fù)的方案數(shù)為bn的生成函數(shù)可寫成：

g(x)=(1+x+x2+…)(1+x2+x4+…)(1+x3+x6+…)…

下面舉一個例子來說明運用生成函數(shù)法來證明分拆恒等式所帶來的優(yōu)越性。

例2.1 已知正整數(shù)n的每部分只出現(xiàn)2,3或5次的分拆數(shù)記為p1(n),正整數(shù)n的每部分模12余±2，±3，6的分拆數(shù)記為p2(n),試證：p1(n)=p2(n).

證明：等式左邊用生成函數(shù)表示為

右邊用生成函數(shù)表示為

對左邊的生成函數(shù)進行化簡：

可以發(fā)現(xiàn)等式兩邊所對應(yīng)的生成函數(shù)相同，所以有p1(n)=p2(n)，證畢。

小結(jié)：用生成函數(shù)法證明整數(shù)分拆恒等式是相當常見的方法，當然證明這類恒等式有時也會用到其他一些證明方法，例如組合證明法，但不可否認的是，有時借助生成函數(shù)來證明會帶來很大的方便，能夠達到很好的效果。

2.3 其他類型的恒等式的證明

除了上面所討論的兩類很常見的組合恒等式，其實還有很多其他類型的組合恒等式，比如可重集上的組合恒等式，F(xiàn)ibonacci恒等式等，這些恒等式的證明也可以借助生成函數(shù)這一工具，這一節(jié)我們簡要介紹生成函數(shù)在可重集上的恒等式證明中的應(yīng)用，先看一個引理：

引理2.3[5]對于|x|<1的任何x，有

證明：由于對于|x|<1的任何x，有

取α=-n(n為正整數(shù)),由

即證得引理，證畢。

證明：假設(shè)ak表示從n個不同物體中允許重復(fù)地選取k個的方法數(shù)，由分析可知，序列{a0,a1,a2,…,ak,…}的生成函數(shù)為

由引理2.3可得，

所以得到

證畢。

3 生成函數(shù)在組合計數(shù)和整數(shù)分拆理論中的應(yīng)用

3.1 生成函數(shù)在組合計數(shù)理論中的應(yīng)用

組合計數(shù)是組合數(shù)學(xué)中非常重要的一部分內(nèi)容，我們從高中開始學(xué)習(xí)的排列組合數(shù)就是用來計算一些具體問題的方法數(shù)，并為概率論與數(shù)理統(tǒng)計的學(xué)習(xí)與研究打下基礎(chǔ)，兩者緊密結(jié)合。因此，很有必要對組合計數(shù)進行研究，而生成函數(shù)作為一個極其重要的工具，借助它來研究和處理一些組合計數(shù)問題，有時會起到意想不到的效果。

現(xiàn)在我們先看幾個問題：

例3.1： 一箱子內(nèi)裝有3個紅球，2個黑球，4個白球，這些球除顏色外都相同，現(xiàn)在從箱子中任意取3個球，問有多少種不同的取法數(shù)？

解答：作形式表達式

(1+x+x2+x3)(1+x+x2)(1+x+x2+x3+x4)

若每次從箱子中取出n個的可重復(fù)組合數(shù)用an表示，則數(shù)列{an}的生成函數(shù)可表示為：

所以，生成函數(shù)f(x)的展開式中x3的系數(shù)9即代表從箱子中任意取3個球的所有不同方法數(shù)。

例3.2: 現(xiàn)有1分，2分，5分的郵票，問能貼出哪些面值(這里以角為單位)的郵票？每種面值又有多少種貼法？

解答：用an表示用1分，2分，5分的郵票，貼出面值為n的郵票的不同貼法總數(shù)，因郵票可重復(fù)使用，所以數(shù)列{an}的生成函數(shù)為

f(x)=∑n≥0anxn=(1+x+x2+x3+…)(1+x2+x4+…)(1+x5+x10+…)=1+x+2x2+2x3+3x4+4x5+…

由生成函數(shù)的展開式可得:

x表示貼出面值為1分的郵票共有1種方案:1.

2x2表示貼出面值為2分的郵票共有2種方案:1+1,2.

2x3表示貼出面值為3分的郵票共有2種方案:1+1+1,1+2．

3x4表示貼出面值為4分的郵票共有3種方案:1+1+1+1,1+1+2,2+2．

……

所以從上面的生成函數(shù)就可以得出能貼出哪些面值的郵票，以及每種面值的郵票的貼法總數(shù)。

以上是在現(xiàn)實生活中會遇到的具體例子，通過運用生成函數(shù)去處理，我們發(fā)現(xiàn)解決過程簡單明了，并且易于掌握和運用。

3.2 生成函數(shù)在整數(shù)分拆理論中的應(yīng)用

整數(shù)分拆與組合數(shù)學(xué)中的很多實際問題都有關(guān)聯(lián)，即很多組合數(shù)學(xué)中的實際問題都可以看成是對某些整數(shù)按照給定的條件進行分拆，進而通過計算分拆的方法數(shù)來解決問題，而對于處理分拆問題，生成函數(shù)自然不失為一種非常有效的工具。

例3.3： 若有四種砝碼各一枚，它們分別是1克、2克、3克、4克的,問能秤出哪幾種重量? 有幾種對應(yīng)的方案?

解答：由分析計算可知，可以秤出的重量最少是1克,最多為10克，我們可以考慮將它轉(zhuǎn)化為整數(shù)分拆問題，即轉(zhuǎn)為計數(shù)將1到10的這10個數(shù)分別分拆成1、2、3、4的方法數(shù)。因此，可以考慮生成函數(shù):

g(x)=(1+x)(1+x2)(1+x3)(1+x4)

這里砝碼的克數(shù)用x的指數(shù)表示出來了，而對應(yīng)的方案數(shù)則由x的系數(shù)表示。

將生成函數(shù)展開得：

g(x)=1+x+x2+2x3+2x4+2x5+2x6+2x7+x8+x9+x10

通過生成函數(shù)，所要的結(jié)果就很清晰，例如，右端有2x6項,說明秤出6克的方案數(shù)有兩種,即6=1+2+3=2+4；又如x10項表示秤出10克的方案數(shù)僅有一種，即10=1+2+3+4.

例3.4： 求方程x1+x2+x3+x4=12,滿足0≤x1≤5,1≤x2≤4,3≤x3≤7,4≤x4≤6的整數(shù)解的個數(shù)。

析：由分析可知此問題也可認為是整數(shù)分拆問題,也就是把12分拆成滿足條件的4個整數(shù)的和的方法數(shù)問題。

解答：通過對問題的分析,構(gòu)建如下生成函數(shù):

g(x)=(1+x+…+x5)(x+x2+x3+x4)(x3+x4+…+x7)(x4+x5+x6)

g(x)的展開式中x12的系數(shù)a12即為所要求的滿足條件的解的個數(shù)?？梢越獾胊12=31即為所要的整數(shù)解個數(shù)。

小結(jié)：整數(shù)分拆問題是組合數(shù)學(xué)中一個十分重要而有趣的問題，而整數(shù)分拆問題研究中最重要的是討論和研究分拆函數(shù)的一些性質(zhì)，通過對分拆函數(shù)的運算和分析得到一些想要的結(jié)果。這其中生成函數(shù)則剛好成為一個十分有效的工具，所以分拆理論的研究很自然地會經(jīng)常用到生成函數(shù)法。從上面的例題中我們會發(fā)現(xiàn)，組合計數(shù)與整數(shù)分拆有很多關(guān)聯(lián)之處，許多整數(shù)分拆問題可以轉(zhuǎn)化為組合計數(shù)問題，當計數(shù)問題解決了，整數(shù)分拆問題也可以得到解答。

4 生成函數(shù)在遞推關(guān)系中的應(yīng)用

遞推關(guān)系是數(shù)學(xué)計算中用得特別多的一個工具,很多數(shù)學(xué)問題特別是組合數(shù)學(xué)問題都可以轉(zhuǎn)化成遞推關(guān)系問題，但是遞推關(guān)系問題的處理并沒有想象的容易，但是，如果能利用生成函數(shù)來求解遞推關(guān)系問題，可能會收到意想不到的效果，可見生成函數(shù)法是處理遞推關(guān)系問題的一種重要且行之有效的方法。

例4.1: 在n位十進制的數(shù)中，請問出現(xiàn)偶數(shù)個3的數(shù)有多少個？。

解：令an表示n位十進制數(shù)中出現(xiàn)偶數(shù)個3的數(shù)的個數(shù),bn表示n位十進制數(shù)中出現(xiàn)奇數(shù)個3的數(shù)的個數(shù)。

所以有an=9×10n-2+8an-1,其中a1=8，此關(guān)系即為關(guān)于序列{an}的遞推關(guān)系,求解此遞推關(guān)系是解決本問題的關(guān)鍵。我們可以考慮引進序列{an}的生成函數(shù)f(x),即:

f(x)=a1+a2x+a3x2+…,

(1)

所以，8xf(x)=8a1x+8a2x2+8a3x3+…

(2)

(1)式-(2)式得：(1-8x)f(x)=a1+(a2-8a1)x+(a3-8a2)x2+…

又因為an-8an-1=9×10n-2,a1=8，

所以

再將f(x)展開成如下形式的冪級數(shù)：

例4.2: 求遞推關(guān)系fn=5fn-1-6fn-2(n≥2)滿足初值f0=1,f1=-2的解.

解：先寫出fn對應(yīng)的生成函數(shù)f(x),并作如下變形：

f(x)=f0+f1x+f2x2+…+fnxn+…

-5xf(x)=-5f0x-5f1x2-5f2x3-…-5fn-1xn-…

6x2f(x)=6f0x2+6f1x3+6f2x4+…+6fn-2xn+…

注意到當n≥2時fn-5fn-1+6fn-2=0，將上面三式相加得到：

(1-5x+6x2)f(x)=f0+(f1-5f0)x=1-7x

由此便得到fn的生成函數(shù)為

為了得到fn的通項公式，我們繼續(xù)把f(x)展開成冪級數(shù)。這里用分解為部分分式的和的方法，寫成

易得待定系數(shù)A=5,B=-4.所以

=1-(5×2-4×3)x+…+(5×2n-4×3n) xn+…

所以得到，

fn=5×2n-4×3n

由上面的求解過程，我們可以得到下面的結(jié)論。

結(jié)論4.1: 設(shè)數(shù)列{fn}滿足如下遞推關(guān)系

fn+a1fn-1+…+akfn-k=0(n≥k).

初值為f0,f1,…,fK-1,則數(shù)列{fn}的生成函數(shù)為

將bn的求和表達式展開以后即為：

由bn的表達式可知，不僅能由初值確定常數(shù)bi，反之，若已知常數(shù)bi，也可唯一確定初值f0,f1,…,fK-1，因為當把上面的關(guān)系式看成是關(guān)于未知數(shù)f0,f1,…,fK-1的線性方程組時，其系數(shù)矩陣為對角元全為1的下三角矩陣。同時注意到f(x)是一個有理真分式，故上面的定理也是可逆的。即有下面的結(jié)論：

結(jié)論4.2: 設(shè)數(shù)列{fn}的生成函數(shù)為

則數(shù)列{fn}滿足如下遞推關(guān)系

fn+a1fn-1+…+akfn-k=0(n≥k).

①給定一個數(shù)列的遞推關(guān)系及其初值，如果這個遞推關(guān)系是線性齊次常系數(shù)的，那么其生成函數(shù)為有理真分式，又由數(shù)學(xué)分析中的結(jié)論可知它一定是可以展開成冪級數(shù)的，從而可求得fn的通項公式。

②假如已經(jīng)知道{fn}的生成函數(shù)為有理真分式，則一定可以找到{fn}的遞推關(guān)系和初值，并且這個遞推關(guān)系是線性齊次常系數(shù)的。

對于非線性齊次常系數(shù)遞推關(guān)系，有如下的結(jié)論：

結(jié)論4.3: 設(shè)數(shù)列{fn}滿足如下遞推關(guān)系

fn+a1fn-1+…+akfn-k=hn(n≥k).

初值為f0,f1,…,fK-1,則數(shù)列{fn}的生成函數(shù)為

最后我們用生成函數(shù)來推導(dǎo)Catalan數(shù)[6]Cn的表達式。

我們知道Catalan數(shù)Cn滿足下面的遞推關(guān)系：

初值為C1=1.若補充定義C0=0，則

所以f(x)=C(x)-x.

又f(x)=C2(x),故C2(x)=C(x)-x，解之得

又因為C0=0意味著C(0)=0，故要舍去上式C(x)的解中相加的那一個，即只取

再將C(x)作冪級數(shù)展開，得到

小結(jié)：通過利用生成函數(shù)求解遞推關(guān)系問題，原本不好處理的問題會變得更加容易表達和處理。可以說，生成函數(shù)是解決遞推關(guān)系問題的一個十分有效的工具，這里的關(guān)鍵點就是如何靈活地將遞推關(guān)系問題轉(zhuǎn)化為生成函數(shù)問題，有的時候可能生成函數(shù)并不好找，所以怎樣去觀察和發(fā)現(xiàn)其中可能有用的生成函數(shù)是關(guān)鍵的一步，因為這將為后面的處理過程帶來許多簡便。

5 總結(jié)

本文介紹了處理組合數(shù)學(xué)問題的一個極其重要的工具——生成函數(shù)，它在組合數(shù)學(xué)中的應(yīng)用很廣泛，我們主要研究了其在證明一些組合恒等式，解決一些組合計數(shù)問題、整數(shù)分拆問題、遞推關(guān)系問題中的應(yīng)用，其實它在處理其他一些問題中還有許多應(yīng)用，比如在概率統(tǒng)計計算、圖論、理論物理問題求解、計算機算法的復(fù)雜性分析等許多學(xué)科中都有著廣泛的應(yīng)用，對于這些應(yīng)用本文沒有涉及?？傊?，大量事例表明發(fā)生函數(shù)方法對組合數(shù)學(xué)中的許多問題的研究有著重要的意義,是研究組合數(shù)學(xué)的必不可少的工具,所以我們很有必要去學(xué)習(xí)和掌握它的基本理論知識，并能運用它來解決一些實際問題。

[1]柯召,魏萬迪.組合論(上冊)[M].北京:科學(xué)出版社,2010.

[2]盧光輝，孫世新，楊國武.組合數(shù)學(xué)及其應(yīng)用[M].北京：清華大學(xué)出版社，2014.

[3]馮榮權(quán),宋春偉.組合數(shù)學(xué)[M].北京:北京大學(xué)出版社,2015.

[4]George E.Andrews and Kimmo Eriksson.Ingeger partition[M].Cambridge: Cambridge University Press,2004.

[5]王天明.近代組合學(xué)[M].大連:大連理工大學(xué)出版社,2008.

[6]楊雅琴,李秋月,馬騰宇.組合數(shù)學(xué)[M].北京:國防工業(yè)出版社,2013.

Some Application of Generating Function in Combinatorics

WANG Zhong-ping

(College of Mathematics and Statistics, Chongqing University, Chongqing 401331,China)

Generating function is an important theory tool in combinatorics.Its application in combinatorial problem is flexible and extensive. It not only can be used to deduce or prove all kinds of useful combinatorial identities, but also can be used to solve combinatorial counting problem,integer partition problem,recursive relations problem,etc.This paper mainly study the application of generating function in several combinatorial problems of the above listed, it can also reflect the superiority of generating function, a tool for us deal with combinatorial mathematics problems.

Generating function;Combinatorial identities; Combinatorial counting;Integer partition; Recursive relation

2016-02-17

王中平(1988-)，男，江西贛州人，重慶大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院在讀碩士。主要研究方向：組合數(shù)學(xué)。

O174

A

1673-6125(2016)01-0001-07