在以上兩節,筆者介紹了「普通母函數」和「指數母函數」,這兩種「母函數」可分別用來求取符合某些特定條件的「組合」和「排列」數目。不過,在某些應用中,我們所關心的不只是「組合」或「排列」的「數目」,而是希望列出所有「組合」或「排列」的「成員」(即具體的「組合」或「排列」方案)。在本網頁中,筆者將介紹一種特殊的「母函數」,可用來找出所有符合某些特定條件的「組合」或「排列」方案。由於這種「母函數」具有列舉的功能,以下筆者把這種「母函數」稱為「列舉型母函數」,而把以上兩節介紹的那兩種「母函數」稱為「點算型母函數」。
我們首先討論「組合問題的列舉型母函數」,這種「列舉型母函數」跟「普通母函數」非常相似,兩者的區別只在於前者比後者多了代表物件類別的符號。我們知道,從3件物件中不可重覆地抽r個出來的「組合」問題可以用以下「普通母函數」來代表:
在上式中,x (= x1)和1 (= x0)代表是否抽取某一物件。請注意這種表達法沒有包含各個物件「身份」的信息。為了加入此一信息,我們可以把代表物件「身份」的符號加進「母函數」中。舉例說,假設前述的3件物件分別為a、b和c。那麼我們可以把是否抽取a表達為ax (= (ax)1)和1 (= (ax)0),b和c的情況照此類推。這樣我們便得到以下的「列舉型母函數」:
  | (1 + ax) × (1 + bx) × (1 + cx) |
= | 1 + (a + b + c)x + (ab + bc + ac)x2 + abcx3    (1) |
請注意上式包含了上述「組合」問題的各個「組合」方案的信息。例如x2項的「系數」便包含了從a、b和c這3件物件中不可重覆地抽取2個出來的所有「組合」方案:ab、bc和ac。請注意如果我們把a、b和c看成變數,並把a = 1、b = 1和c = 1代入上式,便會重新得到《點算的奧秘:普通母函數》所介紹的「普通母函數」:
公式(1)和(2)的差別在於,後者只告訴我們從3件物件中抽r個出來應有多少種「組合」,而前者則告訴我們從3件物件中抽r個出來應包含哪些「組合」。
對於一個一般的「組合」問題而言,假如該「組合」問題涉及n類物件a1、a2 ... an,那麼我們便可以把這個「組合問題的列舉型母函數」表達為
其中fr(a1, ... an)代表a1 ... an的某個函數,這個函數會隨著r取不同的值而變化。舉例說,對於前面的公式(1)而言,f1(a, b, c) = a + b + c,f2(a, b, c) = ab + bc + ac。
當我們把a1 = 1 ... an = 1代入公式(3),便可得到上述一般「組合」問題的「普通母函數」:
由此可見,「普通母函數」其實只是「組合問題的列舉型母函數」的特例。
認識了「組合問題的列舉型母函數」的基本原理,我們便可以利用它來解決「列舉型組合」問題,即所求答案為組合「成員」的問題,有別於所求答案為組合「數目」的「點算型組合」問題。試看以下例題。
例題1:現從A、B、C這3個字母中可重覆地抽7個出來。若其中規定包含最多1個A、最少1個B和1至2個C,問有哪幾種抽法?
答1:本題正是《點算的奧秘:普通母函數》中的例題1。類似該題的解答,本題的「母函數」也是由3個「括弧」組成,不過現在我們的「括弧」須為「列舉型母函數」的形式,即
  | [1 + Ax] × [Bx + (Bx)2 + (Bx)3 + ...] × [Cx + (Cx)2] |
= | BCx2 × [1 + Ax] × [1 + Bx + (Bx)2 + ...] × [1 + Cx] |
有些讀者看到這裡,可能以為接下來我們應利用《點算的奧秘:普通母函數》中的公式(5)和(6)把上式中後面3個「括弧」化為「封閉形式」,例如把[1 + Bx + (Bx)2 + ...]化為1 / (1 − Bx)。可是由於上式中後面3個「括弧」的內容各不相同,這樣做沒有甚麼好處,反而令上式變得更複雜。因此接下來我們只能憑觀察找出上式展開式中x7項的「系數」。
由於上式開首已有一個x2項,我們只需找出後面3個「括弧」中哪些項相乘會得到x5項。根據觀察,當上式中後3個「括弧」取以下的項時,便符合我們的要求:1, (Bx)4, Cx; 1, (Bx)5, 1; Ax, (Bx)3, Cx; Ax, (Bx)4, 1。把以上這些項分別與上式開首的BCx2相乘後再相加,便得到上式展開式中x7項的「系數」(當然我們也可以運用合適的電腦軟件把上式展開,然後「讀取」這個「系數」):
上式很簡潔地提供了本題的4個解,例如上式的第一項B5C2便代表0個A、5個B和2個C,這個組合符合本題的限制條件,而且剛好含有7個字母。其餘3個解照此類推。□
以上例題的解答告訴我們,由於「組合問題的列舉型母函數」一般由各不相同的「括弧」組成,我們一般不能利用《點算的奧秘:普通母函數》中的公式把這些「括弧」化為「封閉形式」,從而直接計算xr項的「系數」,而只能憑觀察找出符合我們要求的項。不過,即使這樣,「組合問題的列舉型母函數」仍有其價值,因為它使我們很容易地把繁複的限制條件表達為「母函數」形式,從而把應用問題轉化為乘數問題,方便解題,這正是「母函數」方法相對於其他解題方法(例如「容斥原理」)的優勝之處。
以上筆者介紹了「組合問題的列舉型母函數」,一個很自然的推論是,能否把上述方法推廣應用於「排列」問題?很不幸的是,「排列」問題的情況比「組合」問題複雜得多。請注意我們不能像上面推導「組合問題的列舉型母函數」那樣,單純把代表物件「身份」的符號加進《點算的奧秘:指數母函數》介紹的「指數母函數」中,事情沒有這麼簡單。且讓我們看看「指數母函數」與「普通母函數」的區別。兩者在形式上只差一個因子1 / r!。這個因子顯然來自「組合」與「排列」問題之間的這個關係式:
可是這個因子只告訴我們「組合」與「排列」問題之間在「數量」上有甚麼關係,而沒有告訴我們兩者的「成員」有甚麼關係。由此可見,我們不可能以簡單的方法把「指數母函數」轉化為「排列問題的列舉型母函數」。
這是否代表我們沒有其他方法構造「排列問題的列舉型母函數」?筆者認為,我們至少可以構造「無限重覆排列問題的列舉型母函數」,但須先對我們慣常接觸的乘法系統作出一些修改。由於在通常的乘法下,乘積AB和BA (這裡依照慣常做法,把×號省去)被視為相同的「對象」,但在「排列」問題下,A-B與B-A卻被視為不同的排列;假如我們想用乘積代表排列,就必須把通常的乘法重新理解為一種「非交換運算」(Non-commutative Operation),即不滿足「交換律」的乘法(註2)。在這種乘法下,AB和BA是兩個不同的乘積,不能相加(註1)。不過我們仍可定義「冪次」(Power),但只限於相鄰的幾個相同的數的乘積,例如可以把AAABB寫成A3B2,或把(A + B)(A + B)寫成(A + B)2;但卻不能把ABABA寫成A3B2,因為我們不能隨意調換乘積中A、B的次序。
在「非交換乘法」下,我們可以把「無限重覆排列」問題表達為若干個項相加的和的冪次。舉例說,從2類物件(用A和B代表)中可重覆地抽3個出來排序的問題便可以表達為以下形式:
  | (A + B)3 |
= | (A + B)(A + B)(A + B) |
= | AAA + AAB + ABA + ABB + BAA + BAB + BBA + BBB    (5) |
請注意以上的展開式剛好包羅全部23 = 8個可能的排列。
一般地,對於從n類物件(用A1 ... An代表)中可重覆地抽r個出來排序的問題,我們可以用以下形式表示:
以上乘積的展開式將包羅全部nr個可能的排列。假如我們把r取不同值的結果乘以xr,並對所有結果求和,便得到「無限重覆排列問題的列舉型母函數」:
以上「列舉型母函數」只適用於「無限重覆排列」問題,對於其他「排列」問題,我們只能運用其他方法。本網站介紹過的其他「排列」問題包括「不可重覆的排列」問題、「有限重覆部分排列」問題和「有限重覆全排列」問題(註3),其中「不可重覆的排列」問題可以被視為「有限重覆部分排列」問題的特例,因為「不可重覆」實際等同於「上限為1」。此外,在《點算的奧秘:帶上、下限的排列組合問題》中,筆者曾經指出,我們可以把「有限重覆部分排列」問題(「帶上、下限的排列」問題是「有限重覆部分排列」問題的特例)的解題程序分解為「組合」和「全排列」兩個步驟。雖然以上解題程序是就「點算型排列」問題而言,但類似的原理亦適用於「列舉型排列」問題,即「有限重覆列舉型部分排列」問題的解題程序可分為兩步,在第一步中我們首先找出所有符合給定限制條件的「組合」,這一步可用前面介紹的「組合問題的列舉型母函數」解決;在第二步中我們逐一找出這些「組合」的「有限重覆全排列」。
由此可見,解決其他「列舉型排列」問題的關鍵在於解決「有限重覆列舉型全排列」問題,即給定一組可能有重覆的物件,我們如何找出這些物件的所有「全排列」方案?舉例說,如何找出2個A和1個B的所有「全排列」方案?回顧一下上面的算式(5),便能發現該展開式其實包含了2個A和1個B的全部3! / (2! × 1!) = 3個「全排列」方案:A-A-B、A-B-A和B-A-A。不僅如此,該展開式還包含了其餘3組「排列」方案(3個A;3個B;1個A和2個B)。由此可見,前面介紹的「無限重覆排列問題的列舉型母函數」其實已包含了「有限重覆列舉型全排列」問題的解答,只不過它所提供的信息超過我們所需要的。現在我們的問題是,如何篩選我們所需要的信息?
筆者認為,我們不妨在前面算式(5)的(A + B)3中加入一組新的符號a和b,使之變成
這組新符號a和b跟原有的A和B不同,它們滿足「乘法交換律」(註4)。這樣上式便同時包含了「排列」和「組合」的信息,前者由A、B體現,後者則由a、b體現。其中a、b的作用是把對應於某一「組合」方案的所有「排列」聚在一起。現在讓我們把上式展開,得到
  | (Aa + Bb)3 |
= | AAAa3 + (AAB + ABA + BAA)a2b + (ABB + BAB + BBA)ab2 + BBBb3 |
上式中a2b項的「系數」就是2個A和1個B的所有「全排列」方案。
一般地,設有n類共r個物件,其中A1共有r1個...An共有rn個,並且r1 + ... rn = r,現要把這r個物件進行「全排列」。我們可以用以下的「有限重覆全排列問題的列舉型母函數」求解:
上式中a1r1 ... anrn項的「系數」就是所求的答案。
以下筆者用一個例題說明如何綜合運用本網頁介紹的「母函數」解決「有限重覆列舉型部分排列」問題。
例題2:利用A、B和C可以排成哪些含4個字母的字符串,使得該字符串含有奇數個B和偶數個C?
答2:本題正是《點算的奧秘:指數母函數》中的例題2。如前所述,本題的解題程序可分為兩步。在第一步中,我們運用前述的「組合問題的列舉型母函數」找出所有符合上述限制條件的「組合」方案。由於有3類物件,上述「母函數」由3個「括弧」組成。根據題意,寫出這3個「括弧」,並把它們相乘:
現在要求上式展開式中x4項的「系數」。根據觀察,當以上3個「括弧」分別取以下的項時,相乘便會得到x4項:Ax, Bx, (Cx)2; Ax, (Bx)3, 1; (Ax)3, Bx, 1。因此上式展開式中x4項的「系數」是
以上結果對應著以下三個「組合」方案:1個A、1個B和2個C;1個A和3個B;3個A和1個C。
接下來我們進行解題程序的第二步,找出對應以上三個「組合」方案的所有「排列」。由於以上三個「組合」方案涉及3類共4件物件,我們可以把這個問題表達為以下的「有限重覆全排列問題的列舉型母函數」:
本題答案就是上式展開式中abc2、ab3和a3b項的「系數」。我們當然可以展開上式並「讀取」有關「系數」(註5),但較簡便的方法還是憑觀察找出所有合適答案。根據觀察,所求的三個「系數」分別為:
以上20個項對應著所求的20個「排列」方案。例如ABCC代表排列A-B-C-C,其餘類推。□
註1:學過「線性代數」或「抽象代數」的讀者應不難理解這種「非交換乘法」。舉例說,「方陣」(Square Matrix)的乘法便不滿足「交換律」,即假如A、B是方陣,則AB並一定等於BA。