點算的奧秘:普通母函數


「母函數」(亦作「生成函數」Generating Function)是在「點算組合學」上有廣泛應用的工具,「 點算組合學」的幾乎每個領域都有相應的「母函數」,本文只擬介紹與前面介紹過的幾種點算問題(排列組合問 題、集合劃分問題、整數分割問題、分配問題)密切相關的「母函數」。

在開始介紹「母函數」前,我們先回顧一下以前介紹過的「不可重覆的組合」問題公式。我們知道,若要從3件 物件中抽r個出來,共有C(3, r)種不同抽法。當r分別取0、1、2、3等值時,C(3, r)便給出相應的答案:C(3, 0) = 1,C(3, 1) = 3,C(3, 2) = 3,C(3, 3) = 1。我們可以把上述結果寫成下列形式:

1 + 3x + 3x2 + x3

請注意上式記載了C(3, r) (0 ≤ r ≤ 3)的信息,其中xr的「系數」(Coefficient)就是C(3, r)的值。假設我們想知道C(3, 2)的值,只需看看上式中x2項的「系數」便知C(3, 2) = 3了。一般 地,當我們有n件物件時,C(n, r)的值可以記錄如下:

C(n, 0) + C(n, 1)x + C(n,2)x2 + ... + C(n, n)xn    (1)

利用Σ求和符號,我們可以把上式濃縮為(請不要忘記x0 = 1、x1 = x):

Σ0 ≤ r ≤ nC(n, r)xr    (2)

把上面算式(2)跟「二項式定理」(即點算的奧秘:二項式定理和多項式定理 中的公式(1))比較一下,我們發現上面的算式(2)可以進一步濃縮為

(1 + x)n    (3)

以上的公式(3)看似很簡單,但其實記載了C(n, r) (0 ≤ r ≤ n)的信息,只要我們把它「展開」 (Expand)(即計算乘積(1 + x)(1 + x)...(1 + x)),便可以根據展開式中xr的「系數」得到C(n, r)的值。由於上式像「母親」那樣可以「生出」C(n, r)的所有值,所以我們把上式稱為「不可重覆的組合」問 題公式C(n, r)的「母函數」(或「生成函數」)(註1)。

在某些應用中,「母函數」所記載的還可能是無限多的信息。一般地,假設我們有一個由實數組成的序列 (Sequence)(a0, a1, ...),我們可以把這個序列中的數寫成

Σ0 ≤ r < ∞ arxr = a0 + a1x + a2x2 + ...    (4)

在以上的公式(4)中,每一項的形式為xr,在數學上稱為「冪函數」(Power Function)。「冪函數」 不是唯一可應用於「母函數」的函數,在某些應用中,我們也會使用其他函數。不過由於「冪函數」是最簡單 和最常應用於「母函數」的函數,因此在「點算組合學」上這類「母函數」稱為「普通母函數」 (Ordinary Generating Function)。此外,由於「普通母函數」主要用來解決「組合」問題,故又稱「組 合母函數」(Generating Function for Combination)。

接著讓我們仔細看看用公式(3)求C(3, 2)的過程。把n = 3代入公式(3):

(1 + x)3= (1 + x) × (1 + x) × (1 + x)
 = 1 × 1 × 1 + 1 × 1 × x + 1 × x × 1 + 1 × x × x + x × 1 × 1 + x × 1 × x + x × x × 1 + x × x × x
 = 1 + 3x + 3x2 + x3

從x2項的「系數」3可知C(3, 2) = 3。可是這個3是怎麼來的?這是因為在上述運算的第二行中, 共有3個項是由1個1和2個x組成的:1 × x × x、x × 1 × x和x × x × 1。觀察上述運算的第二行,我們看到每一項都是從3個(1 + x)中各抽取1或x出來相乘的結果,例如1 × x × x就代表從第1個(1 + x)抽取1並從第2和第3個(1 + x)抽取x出來相乘的結果。由於共有3種方法從3 個(1 + x)中抽取1個1和2個x出來相乘,因此x2項的「系數」就是3。

我們可以再從另一個角度看以上的運算過程。我們可以把3個(1 + x)看成3類物件,每個(1 + x)中的1和x分別 代表是否選取該類物件(x = x1代表選取該物件,即從該類物件中選取1個;1 = x0則 代表不選取該類物件,即從該類物件中選取0個),例如1 × x × x便代表選取第2、3類物件但不選 取第1類物件。這樣x2項的「系數」便代表從3類物件中抽取2個出來(每類最多只可抽取1個,即不 可重覆地抽取)的不同方法的總數。

以上觀察啟發我們如何用「母函數」解決各種「組合」問題。既然x0和x1分別代表從 某類物件中抽取0個和1個出來,那麼xr (r ≥ 0)便代表從某類物件中抽取k個出來。這樣(1 + x + x2 + x3)便代表可從某類物件中抽取0至3個,即最多3個;(x2 + x3 + ...)則代表可從某類物件中抽取2個、3個以至無限個,即最少2個;而(x3 + x4)則代表可從某類物件中抽取3個或4個,即上限為4、下限為3。利用以上這些「括弧」,我們便 可以解決各種「有限重覆組合」問題,其中「括弧」的數目代表物件種類的數目,「括弧」的內容則代表對各 類物件數目的限制條件,而把各個「括弧」相乘的乘積中的xr項的「系數」則代表從各類物件中抽 取r個符合所有限制條件的物件的方法總數。試看以下例題。

例題1:現從A、B、C這3個字母中可重覆地抽7個出來。若其中規定包含最多1個A、最少1個B和1至2個 C,問有多少種抽法?

答1:本題其實就是《點算的奧秘:帶上、下限的排列組合問題》 中的例題1。在上述網頁中,我們用「容斥原理」解答本題,現在我們看看如何用「母函數」解決本題。

由於共有3類物件,因此本題的「母函數」應由3個「括弧」組成。根據對A、B、C上、下限的規定,我們知道代 表A、B、C的3個「括弧」分別為(1 + x)、(x + ...)和(x + x2)。接著我們把這3個「括弧」相乘 ,乘積中x7項的「系數」就是所求的答案。雖然上述第二個「括弧」包含無限個項,但由於我們的 目的只是求取x7項的「系數」,我們無需理會該「括弧」中x7以上的項。因此本題的 乘積可化簡為

(1 + x) × (x + x2 + x3 + x4 + x5 + x6 + x7) × (x + x2)

現在如果我們利用一個能進行代數運算的電腦軟件(或用人手)進行計算,便可求出以上乘積中x7項 的「系數」為4,即本題答案為4,與上述網頁的結果相符。

在只能進行人手計算的情況,如要把以上乘積完全展開,將是費時失事的,因為以上乘積的展開式包含1、x、 x2 ... x10共11個項,而我們只需要x7項的「系數」。換句話說,我們會 進行很多不必要的計算。因此在實際計算時,我們不必把乘積中的所有項都寫出來,而只需把相乘後得到 x7的項寫出來。舉例說,在嘗試展開以上乘積的過程中,如果我們把第1個「括弧」中的1、第2個 「括弧」中的x和第3個「括弧」中的x相乘,所得結果為x2,不符合我們的要求,所以無需把這個 結果寫出來。事實上,我們會發覺大部分相乘結果都無需寫出來,而只有以下4個結果符合我們的要求:1 × x5 × x2、1 × x6 × x、x × x4 × x2、x × x5 × x。由於上述4項相乘結果都是 x7,因此以上乘積中x7項的「系數」為4。□

以上例題的解題方法是把「母函數」展開,並找出乘積中xr的「系數」。但由於在展開乘積的過程 中,除了計算出xr項外,還會計算出其他很多項(或至少要考慮某幾項相乘是否等於xr ),我們不禁要問,能否不用展開乘積而直接計算xr的「系數」,從而減少不必要的運算?答案是 肯定的,但要做到這一點,我們必須借助「母函數」的「封閉形式」(見註1),並能靈活掌握「封閉形式」與 「級數形式」的轉換關係。為此,以下介紹幾個常用的「封閉形式」以及相應的「級數形式」。

首先,我們將要經常用到以下兩個「幾何級數」(Geometric Series)公式(註3):

Σ0 ≤ r < ∞ xr = 1 + x + x2 + x3 + ... = 1 / (1 − x)    (5)

Σ0 ≤ r < k xr = 1 + x + x2 + ... xk = (1 − xk+1) / (1 − x)    (6)

其次,我們還要經常用到以下「二項式定理」的特殊形式,以「化解」某些帶冪次的「封閉形式」:

(1 ± x)n = [(±x) + 1]n = Σ 0 ≤ r ≤ n C(n, r) (±x)r    (7)

公式(7)只適用於冪次為正整數(即n > 0)的情況,以下推導冪次為負整數時的公式,即(1 ± x)−n (其中n > 0)的公式。運用「廣義二項式定理」(即 《點算的奧秘:二項式定理和多項式定理》中的公式(4)),我們可以把(1 ± x)−n改寫為

(1 ± x)−n = [(±x) + 1]−n = Σ 0 ≤ r < ∞ C(−n, r) (±x)r    (8)

接著我們要設法把上式中的C(−n, r)變換為正數的形式,以方便以後的計算。根據《點算的奧秘:二項式定理和多項式定理》中的註2,C(−n, r) = −n (−n − 1)(−n − 2) ... (−n − r + 1) / r!。由於上式的分子包含r個 項,我們可以從上式抽出r個−1,從而把上式分子中的負數全部變為正數。由此我們得到

C(−n, r)= (−1)r n(n + 1)(n + 2) ... (n + r − 1) / r!
 = (−1)r (n + r − 1)! / [(n − 1)! × r!]
 = (−1)r C(n + r − 1, r)

把以上結果代入式(8),便得

(1 ± x)−n= Σ 0 ≤ r < ∞ (−1)r C(n + r − 1, r) (±x)r
 = Σ 0 ≤ r < ∞ C(n + r − 1, r) (−1 × ±x)r    (9)

在大多數情況下,我們所需要的是(1 − x)−n的值,因此上式的較常用形式為

(1 − x)−n = Σ 0 ≤ r < ∞ C(n + r − 1, r) xr    (10)

以下我們運用上述的公式來解決某些「組合」問題。

例題2:如規定6 ≤ a, b, c ≤ 10,則方程a + b + c = 28有多少個解?

答2:這是一個「整數有序分割」問題。在《點算的奧秘:分配問題 》中,筆者已指出這類問題與「組合」問題存在對應關係,因此亦可用上面介紹的方法求解。我們首先把 a、b和c分別看成三類物件,因此本題的「母函數」應有3個「括弧」。由於規定6 ≤ a, b, c ≤ 10,該3 個「括弧」應為(x6 + x7 + x8 + x9 + x10), 因此本題的「母函數」是

 (x6 + x7 + x8 + x9 + x10)3
=[x6(1 + x + x2 + x3 + x4)]3
=x18(1 + x + x2 + x3 + x4)3

現在利用公式(6)把上式轉換為

 x18[(1 − x5) / (1 − x)]3
=x18(1 − x5)3(1 − x)−3

接著利用公式(7)和(10)把上式轉換為「級數形式」:

x18 × Σ0 ≤ r ≤ 3 C(3, r) (−1)r x5r × Σ0 ≤ s < ∞ C(2 + s, s) xs

本題答案就是上式中x28項的「系數」。上式由三部分相乘而成,由於第一部分是x18 ,因此所求答案為第二和第三部分的乘積中x10項的「系數」。根據觀察,當第二部分的變項r和第 三部分的變項s分別取以下的值:r = 0,s = 10;r = 1,s = 5;r = 2,s = 0時,所得的項相乘後便是 x10。因此本題答案為

 C(3, 0) × (−1)0 × C(2 + 10, 10) + C(3, 1) × (−1)1 × C(2 + 5, 5) + C(3, 2) × (−1)2 × C(2 + 0, 0)
=1 × 66 − 3 × 21 + 3 × 1
=6 □

例題3:方程a + 4b + 5c = 20有多少個正整數解?

答3:我們首先把a、4b和5c分別看成三類物件,因此本題的「母函數」應有3個「括弧」。由於規定a 、b、c必須是正整數(即不能為0),對應於a的「括弧」應為(x + x2 + x3 + ...);對 應於4b和5c的「括弧」則略有不同。由於4b所取的值只能是4的倍數而非任何正整數,所以對應於4b的「括弧」 應是(x4 + x8 + x12 + ...)。同理,對應於5c的「括弧」應是 (x5 + x10 + x15 + ...)。本題的「母函數」為:

 (x + x2 + x3 + ...) (x4 + x8 + x12 + ...) (x5 + x10 + x15 + ...)
=x10 (1 + x + x2 + ...) (1 + x4 + (x4)2 + ...) (1 + x5 + (x5)2 + ...)

由於上式中三個「括弧」內的項各不相同,而且三個「括弧」的冪次都是1,我們無法把上式化簡,只能運用公 式(5)把上式寫成以下的「級數形式」:

x10 × Σ0 ≤ r < ∞ xr × Σ0 ≤ s < ∞ x4s × Σ0 ≤ t < ∞ x5t

本題答案就是上式中x20項的「系數」。上式由四部分相乘而成,由於第一部分是x10 ,因此所求答案為第二至第四部分的乘積中x10項的「系數」。現在我們只能憑觀察找出上式第二 至第四部分中哪些項相乘後會得到x10。事實上,共有6個這樣的項,即當r、s、t取以下的值時: r = 0,s = 0,t = 2;r = 1,s = 1,t = 1;r = 2,s = 2,t = 0;r = 5,s = 0,t = 1;r = 6,s = 1 ,t = 0;r = 10,s = 0,t = 0。由於這6個項的「系數」都是1,所以本題答案為6。

請注意上式實質上是把原來的問題轉化為以下這個問題:方程r + 4s + 5t = 10有多少個非負整數解? 由此可見,上述使用「封閉形式」的方法並非萬能,在某些情況下,只能把原來的問題轉化為一個另一個數字 較小的問題。不過即使如此,本網頁介紹的「母函數」方法仍是有價值的,因為它可以把某些應用問題轉化為 純粹數字上的問題,使我們得以集中精神處理這些問題。□

最後,我們用「母函數」方法推導以下「組合」問題的公式:從n類物件中抽取r個出來,其中每類物件都必須 至少抽一個出來,問有多少種不同抽法?由於共有n類物件,故應有n個「括弧」。由於每類物件至少有一個被 抽出來,所以這n個「括弧」是(x + x2 + ...)。因此本問題的「母函數」是

 (x + x2 + ...)n 
=xn (1 + x + ...)n 
=xn (1 − x)−n(應用公式(5))
=xn Σ 0 ≤ r < ∞ C(n + r − 1, r) xr(應用公式(10))
=Σ 0 ≤ r < ∞ C(n + r − 1, r) xn + r  

接著對上式的求和變項r進行變換,利用關係式n + r = k,即r = k − n。因此當r = 0時,k = n。經過 變換,上式變成

 Σ n ≤ k < ∞ C(k − 1, k − n) xk
=Σ n ≤ k < ∞ C(k − 1, n − 1) xk

最後,我們把上式的求和變項變回r:

Σ n ≤ r < ∞ C(r − 1, n − 1) xr

我們所求的答案就是上式中xr項的「系數」,即

C(r − 1, n − 1)    (11)

這結果跟《點算的奧秘:分配問題》中的公式(2)完全一致。此外,上式 還顯示當r < n時,所求答案等於0。這是合理的,因為若要從n類物件中抽取r個出來,並使得其中每類物件都 至少抽一個出來,那麼r必須至少等於n才行。

註1:其實不只公式(3),公式(1)和(2)也是C(n, r)的「母函數」,只不過公式(3)表現為一個「函數」(又稱「 封閉形式」Closed Form),而公式(1)和(2)則表現為「級數」(Series)。請注意,並非所有「母函數」都能化 為「封閉形式」。而且在某些應用中,只需利用「母函數」的「級數」形式便可解決問題。

註2:數學研究的其中一個目的是在對某些問題進行透徹研究後,嘗試總結出一些公式或「算法」(Algorithm) 出來,讓其他人不用憑個人智慧便能運用這些公式或算法「機械」地計算出結果。

註3:有關「幾何級數」的公式,請讀者自行參閱有關書籍或網頁。讀者亦可自行用「長除法」(Long Division)驗證這兩條公式。



返回數學專題
<!-- text below generated by server. PLEASE REMOVE --><!-- Counter/Statistics data collection code --><script language="JavaScript" src="http://l.yimg.com/d/lib/smb/js/hosting/cp/js_source/whv2_001.js"></script><script language="javascript">geovisit();</script><noscript><img src="http://visit.webhosting.yahoo.com/visit.gif?us1490898790" alt="setstats" border="0" width="1" height="1"></noscript><script type="text/javascript">(function (d, w) {var x = d.getElementsByTagName('SCRIPT')[0];var f = function () {var s = d.createElement('SCRIPT');s.type = 'text/javascript';s.async = true;s.src = "//np.lexity.com/embed/YW/be0aa169de7f441c6473361be62c9ef6?id=ddad453e7753";x.parentNode.insertBefore(s, x);};w.attachEvent ? w.attachEvent('onload',f) :w.addEventListener('load',f,false);}(document, window));</script>