點算的奧秘:指數母函數


《點算的奧秘:普通母函數》中,筆者介紹了形如

Σ0 ≤ r < ∞ arxr

的「母函數」。這種「母函數」主要用來解決「組合」問題,為了解決「排列」問題,我們需要引入另一種「 母函數」,即使用另一種函數來代替上式中的xr。事實上,如果我們用xr / r!取代上 式中的xr,便可得到一種新的「母函數」,稱為「指數母函數」(Exponential Generating Function)。由於這種「母函數」主要用來解決「排列」問題,故又稱「排列母函數」 (Generating Function for Permutation)。

「指數母函數」的有用之處在於,我們可以使用與「普通母函數」完全對應的方法來解決「排列」問題。在介 紹「普通母函數」時,筆者曾指出我們可以把「普通母函數」中的xr看成代表從某類物件中抽取k 個出來。現在我們同樣可以把「指數母函數」中的xr / r!看成代表從某類物件中抽k個出來排列。 舉例說,(1 + x + x2/2! + x3/3!)(註1)便代表可從某類物件中抽0至3個(即最多3個) 出來排列;(x2/2! + x3/3! + ...)則代表可從某類物件中抽2個、3個以至無限個(即 最少2個)出來排列;而(x3/3! + x4/4!)則代表可從某類物件中抽3個或4個(即上限為4 個、下限為3個)出來排列。

以下筆者將使用「指數母函數」重新推導各種「排列」問題的計算公式,從而顯示「指數母函數」對「排列」 問題的適用性。首先考慮「不可重覆的排列」問題:從n件物件中不可重覆地抽r個出來排列,問有多少種不同 排法?由於共有n件物件,故本問題的「母函數」應包含n個「括弧」。由於每件物件最多只可抽1個,因此每個 「括弧」的形式均為(1 + x),即本問題的「母函數」為

(1 + x)n = (x + 1)n = Σ0 ≤ r ≤ nC(n, r) xr

上式右端是用「二項式定理」展開(x + 1)n的結果。由於現在我們要求的是「指數母函數」,我們 要設法把xr變為xr / r!。利用在《點算的奧秘:排列 和組合基本公式》介紹的關係式P(n, r) = r! × C(n, r),我們可以把上式變為

(1 + x)n = Σ0 ≤ r ≤ nP(n, r) xr / r!

根據「母函數」的定義,我們所求的答案就是上式中xr / r!項的「系數」,即P(n, r)。可是 P(n, r) = n! / (n − r)!不正就是我們在《點算的奧秘:排列和組合基 本公式》中推導的「(不可重覆)排列」問題的公式嗎?由此可見,利用「指數母函數」,我們獲得應有的 結果。

接著讓我們考慮「有限重覆全排列」問題:設有n類物件,第1類物件共有r1個...第n類物件共有 rn個,並且r = r1 + ... rn。現要將全部r個物件排序,問有多少種排法 ?由於共有n類物件,故本問題的「母函數」應包含n個「括弧」。由於第i類(1 ≤ i ≤ n)物件共有 ri個,所以第i個「括弧」應是(1 + x + x2/2! + x3/3! + ... xri/ri!)。因此本問題的「指數母函數」為

(1 + x + ... xr1/r1!) × (1 + x + ... xr2/r2!) × ... (1 + x + ... xrn/rn!)    (1)

上式的展開式不易求得,因為各個「括弧」的內容不一。但是由於我們要「將全部r個物件排序」,我們只需求 上式展開式中xr / r!項的「系數」。由於xr是上式中的最高次項,只有一個可能途徑 得到這個項,就是把各個「括弧」的最高次項相乘。把這些最高次項相乘後,便得到

 (xr1/r1!) × (xr2/r2!) × ... (xrn/rn!)
=xr / (r1! × r2! × ... rn!)

為了把上式轉化為我們希望的xr / r!形式,我們對上式的分子和分母同時乘以r!,得到

r! / (r1! × r2! × ... rn!) × xr / r!

由此得到「有限重覆全排列」問題的計算公式為

r! / (r1! × r2! × ... rn!)

上式跟《點算的奧秘:有限重覆的排列組合問題》中的相關公式完全一致 。

除了推導出以上公式外,我們還可利用上面的「指數母函數」(公式(1))來解答某些「有限重覆排列」問題。試 看以下例題。

例題1:利用3個A、2個B和1個C可以排成多少個含4個字母的字符串(String)?

答1:在《點算的奧秘:有限重覆的排列組合問題》中,筆者曾 介紹與本題類似的「密西西比」問題。不過,「密西西比」問題是把MISSISSIPPI中的11個字母進行「全排列」 ,而本題則只是從AAABBC中抽取4個字母出來進行「部分排列」,因此本題可稱為「廣義密西西比」問題。根據 上述網頁,「密西西比」問題相當於「有限重覆全排列」問題,因此本題相當於「有限重覆部分排列」問題, 即「上、下限皆為有限整數的排列」問題,其中n = 3、r1 = 3、r2 = 2、 r3 = 1、r = 6。把以上參數代入公式(1),便得到本題的「指數母函數」:

(1 + x + x2/2! + x3/3!) × (1 + x + x2/2!) × (1 + x)

本題答案就是上式展開式中x4/4!項的「系數」。為了求得這個「系數」,我們可以使用合適的電 腦軟件展開以上算式,或者憑觀察找出以上4個「括弧」中哪些項相乘會得到x4,然後把所有情況 加起來。根據觀察,第1至第3個「括弧」應分別取以下的項:x, x2/2!, x; x2/2!, x, x; x2/2!, x2/2!, 1; x3/3!, 1, x; x3/3!, x, 1。

把以上5個組合相乘然後相加,便得到

x4/2! + x4/2! + x4/(2!2!) + x4/3! + x4/3! = 19x4/12 = 38x4/4!

以上結果顯示本題答案為38。□

在以上計算中,我們必須憑觀察找出哪些項相乘會得到x4,而不能直接計算x4/4!項的 「系數」,這是因為對於「指數母函數」而言,我們沒有一條類似《點算的奧 秘:普通母函數》中公式(6)那樣的公式可以用來把1 + x + x2/2! + ... xk/k! 化為「封閉形式」。因此我們可以說,「有限重覆排列」問題比「有限重覆組合」問題較難解。

以上討論的「排列」問題只限於不可重覆或重覆次數為有限整數的「排列」問題,接下來我們要討論重覆次數 不是有限數的「排列」問題。對於這類「排列」問題,我們可以應用「母函數」的「封閉形式」進行運算。我 們首先考慮「無限重覆部分排列」問題:從n類物件中可重覆地抽r個出來排列,問有多少種不同排法?由於共 有n類物件,故本問題的「母函數」應包含n個「括弧」。由於每件物件的重覆次數不限,因此每個「括弧」的 形式均為(1 + x + x2/2! + x3/3! + x4/4! + ...)。學過「微積分」的 讀者應知道以上這個「無窮級數」就是「指數函數」(Exponential Function) ex的「馬克勞林展 開式」(Maclaurin's Expansion)(註2),即

Σ0 ≤ r < ∞ xr / r! = 1 + x + x2/2! + x3/3! + ... = ex    (2)

請注意,ex亦可寫作exp(x),其中e = 2.71828...是高等數學上經常要用到的無理數。利用公式 (2),便可以把「無限重覆部分排列」問題的「指數母函數」寫成

(1 + x + x2/2! + x3/3! + ...)n = enx

現在再次運用公式(2)把上式改寫為

enx= Σ0 ≤ r < ∞ (nx)r / r!
 = Σ0 ≤ r < ∞ nr xr / r!

根據「母函數」的定義,我們所求的答案就是上式中xr / r!項的「系數」,即「無限重覆部分排 列」問題的公式為

nr

上式跟《點算的奧秘:無限重覆的排列組合問題》中的相關公式完全一致 。

在以上計算中,我們使用了一個「封閉形式」(即公式(2))。跟「普通母函數」一樣,「封閉形式」將有助簡化 對「母函數」的運算。從公式(2),我們可以推導出以下這些「封閉形式」:

Σ1 ≤ r < ∞ xr / r! = x + x2/2! + x3/3! + ... = ex − 1    (3)

Σ2 ≤ r < ∞ xr / r! = x2/2! + x3/3! + ... = ex − 1 − x    (4)

此外,我們還可以利用以下兩個運算:

 (ex + e−x) / 2
=(1 + x + x2/2! + x3/3! + x4/4! + ... 1 − x + x2/2! − x3/3! + x4/4! + ...) / 2
=(2 + 2x2/2! + 2x4/4! + ...) / 2
=1 + x2/2! + x4/4! + ...
  
 (ex − e−x) / 2
=(1 + x + x2/2! + x3/3! + x4/4! + ... − 1 + x − x2/2! + x3/3! − x4/4! + ...) / 2
=(2x + 2x3/3! + 2x5/5! + ...) / 2
=1 + x3/3! + x5/5! + ...

從而得到兩個有用的「封閉形式」(註3):

Σ0 ≤ r < ∞ x2r / (2r)! = 1 + x2/2! + x4/4! + ... = (ex + e−x) / 2    (5)

Σ0 ≤ r < ∞ x2r+1 / (2r+1)! = x + x3/3! + x5/5! + ... = (ex − e−x) / 2    (6)

利用以上的公式(2)-(6),我們便可以用「母函數」方法解決一系列「有限重覆排列」問題。

例題2:利用A、B和C可以排成多少個含4個字母的字符串,使得該字符串含有奇數個B和偶數個C?

答2:由於有3類物件,本題的「母函數」由3個「括弧」組成。根據題意,這3個「括弧」應分別為(1 + x + x2/2! + ...)、(x + x3/3! + x5/5! + ...)和(1 + x2/2! + x4/4! + ...)。把這3個「括弧」相乘,並應用公式(2)、(5)和(6),我們得 到

 ex × (ex − e−x) / 2 × (ex + e−x) / 2
=(e3x − e−x) / 4
=0 ≤ r < ∞ (3x)r / r! − Σ0 ≤ r < ∞ (−x)r / r!] / 4
=Σ0 ≤ r < ∞ [(3r − (−1)r) / 4] xr / r!

本題答案就是上式中x4/4!項的「系數」,即(34 − (−1)4) / 4 = 20。□

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

答3:本題其實就是《點算的奧秘:帶上、下限的排列組合問題》 中的例題3,現在我們用「母函數」方法來重新解本題。由於有3類物件,本題的「母函數」由3個「括弧」 組成。根據題意,這3個「括弧」應分別為(1 + x + x2/2! + x3/3!)、(x + x2/2! + x3/3! + ...)和(1 + x + x2/2! + ...)。對於第二和第三個「 括弧」,我們可以應用公式(2)和(3)把它們化為「封閉形式」,但對於第一個「括弧」,卻沒有現成的公式把 它化簡。因此我們只能得到以下乘積:

 (1 + x + x2/2! + x3/3!) × (ex − 1) × ex
=(1 + x + x2/2! + x3/3!) × (e2x − ex)
=(1 + x + x2/2! + x3/3!) × [Σ0 ≤ r < ∞ (2x)r / r! − Σ0 ≤ r < ∞ xr / r!]
=(1 + x + x2/2! + x3/3!) × Σ0 ≤ r < ∞ (2r − 1) xr / r!

本題答案就是上式中x4/4!項的「系數」。可是由於上式包含了(1 + x + x2/2! + x3/3!),我們必須逐一考慮這個「括弧」中各項與後面的乘積。因此上式中的x4/4!項 為

 1 × (24 − 1) x4/4! + x × (23 − 1) x3/3! + x2/2! × (22 − 1) x2/2! + x3/3! × (21 − 1) x
=15x4/4! + 7x4/3! + 3x4/(2!2!) + x4/3!
=15x4/4! + 28x4/4! + 18x4/4! + 4x4/4!
=65x4/4!

由此得知本題答案為65,即前述網頁例題3的同一答案。□

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

 (x + x2/2! + ...)n 
=(ex − 1)n(應用公式(3))
=Σ0 ≤ k ≤ n C(n, k) (−1)k ex(n−k)(應用「二項式定理」)
=Σ0 ≤ k ≤ n C(n, k) (−1)k Σ0 ≤ r < ∞ (n − k)r xr / r!(應用公 式(2))
=Σ0 ≤ r < ∞0 ≤ k ≤ n (−1)k C(n, k) (n − k)r] xr / r! 

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

Σ0 ≤ k ≤ n (−1)k C(n, k) (n − k)r    (7)

上述結果跟《點算的奧秘:分配問題》中的公式(1)完全一致。請注意如 把上式除以n!,便得到「點算組合學」上所稱的「第二類斯特林數」(Stirling Number of the Second Kind)。在「點算組合學」上,有這麼一條定理(證明從略),當r < n時,「第二類斯特林數」等於0。 這即是說,當r < n時,上式等於0。這是合理的,因為若要從n類物件中抽r個出來排序,並使得其中每類物件 都至少抽一個出來,那麼r必須至少等於n才行。

註1:請不要忘記x0 = 1,x1 = x,0! = 1,1! = 1。

註2:「指數母函數」的名稱就是來自「指數函數」。

註3:其實,「普通母函數」也有相應的「封閉形式」:
Σ0 ≤ r < ∞ x2r = 1 + x2 + x4 + ... = 1 / (1 − x2)

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



返回數學專題
<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>