點算的奧秘:列舉型母函數


在以上兩節,筆者介紹了「普通母函數」和「指數母函數」,這兩種「母函數」可分別用來求取符合某些特定 條件的「組合」和「排列」數目。不過,在某些應用中,我們所關心的不只是「組合」或「排列」的「數目」 ,而是希望列出所有「組合」或「排列」的「成員」(即具體的「組合」或「排列」方案)。在本網頁中,筆者 將介紹一種特殊的「母函數」,可用來找出所有符合某些特定條件的「組合」或「排列」方案。由於這種「母 函數」具有列舉的功能,以下筆者把這種「母函數」稱為「列舉型母函數」,而把以上兩節介紹的那 兩種「母函數」稱為「點算型母函數」

我們首先討論「組合問題的列舉型母函數」,這種「列舉型母函數」跟「普通母函數」非常相似,兩 者的區別只在於前者比後者多了代表物件類別的符號。我們知道,從3件物件中不可重覆地抽r個出來的「組合」 問題可以用以下「普通母函數」來代表:

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

在上式中,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 + x)3 = 1 + 3x + 3x2 + x3    (2)

公式(1)和(2)的差別在於,後者只告訴我們從3件物件中抽r個出來應有多少種「組合」,而前者則告訴 我們從3件物件中抽r個出來應包含哪些「組合」。

對於一個一般的「組合」問題而言,假如該「組合」問題涉及n類物件a1、a2 ... an,那麼我們便可以把這個「組合問題的列舉型母函數」表達為

Σ0 ≤ r < ∞ fr(a1, ... an) xr    (3)

其中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),便可得到上述一般「組合」問題的「普通 母函數」:

Σ0 ≤ r < ∞ fr(1, ... 1) xr    (4)

由此可見,「普通母函數」其實只是「組合問題的列舉型母函數」的特例。

認識了「組合問題的列舉型母函數」的基本原理,我們便可以利用它來解決「列舉型組合」問題,即 所求答案為組合「成員」的問題,有別於所求答案為組合「數目」的「點算型組合」問題。試看以下 例題。

例題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項的「系數」(當然我們也可以運用合 適的電腦軟件把上式展開,然後「讀取」這個「系數」):

B5C2 + B6C + AB4C2 + AB5C

上式很簡潔地提供了本題的4個解,例如上式的第一項B5C2便代表0個A、5個B和2個C, 這個組合符合本題的限制條件,而且剛好含有7個字母。其餘3個解照此類推。□

以上例題的解答告訴我們,由於「組合問題的列舉型母函數」一般由各不相同的「括弧」組成,我們一般不能 利用《點算的奧秘:普通母函數》中的公式把這些「括弧」化為「封閉形 式」,從而直接計算xr項的「系數」,而只能憑觀察找出符合我們要求的項。不過,即使這樣,「 組合問題的列舉型母函數」仍有其價值,因為它使我們很容易地把繁複的限制條件表達為「母函數」形式,從 而把應用問題轉化為乘數問題,方便解題,這正是「母函數」方法相對於其他解題方法(例如「容斥原理」)的 優勝之處。

以上筆者介紹了「組合問題的列舉型母函數」,一個很自然的推論是,能否把上述方法推廣應用於「排列」問 題?很不幸的是,「排列」問題的情況比「組合」問題複雜得多。請注意我們不能像上面推導「組合問題的列 舉型母函數」那樣,單純把代表物件「身份」的符號加進《點算的奧秘:指數 母函數》介紹的「指數母函數」中,事情沒有這麼簡單。且讓我們看看「指數母函數」與「普通母函數」 的區別。兩者在形式上只差一個因子1 / r!。這個因子顯然來自「組合」與「排列」問題之間的這個關係式:

C(n, r) = P(n, r) / 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個出來排序的問題,我們可 以用以下形式表示:

(A1 + ... An)r

以上乘積的展開式將包羅全部nr個可能的排列。假如我們把r取不同值的結果乘以xr, 並對所有結果求和,便得到「無限重覆排列問題的列舉型母函數」

Σ0 ≤ r < ∞ (A1 + ... An)r xr    (6)

以上「列舉型母函數」只適用於「無限重覆排列」問題,對於其他「排列」問題,我們只能運用其他方法。本 網站介紹過的其他「排列」問題包括「不可重覆的排列」問題、「有限重覆部分排列」問題和「有限重覆全排 列」問題(註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,使之變成

(Aa + Bb)3

這組新符號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個物件進行「全排列」。我們可以用以下的 「有限重覆全排列問題的列舉型母函數」求解:

(A1a1 + ... Anan)r     (7)

上式中a1r1 ... anrn項的「系數」 就是所求的答案。

以下筆者用一個例題說明如何綜合運用本網頁介紹的「母函數」解決「有限重覆列舉型部分排列」問題。

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

答2:本題正是《點算的奧秘:指數母函數》中的例題2。如前 所述,本題的解題程序可分為兩步。在第一步中,我們運用前述的「組合問題的列舉型母函數」找出所有符合 上述限制條件的「組合」方案。由於有3類物件,上述「母函數」由3個「括弧」組成。根據題意,寫出這3個「 括弧」,並把它們相乘:

[1 + Ax + (Ax)2 + ...] × [Bx + (Bx)3 + (Bx)5 + ...] × [1 + (Cx)2 + (Cx)4 + ...]

現在要求上式展開式中x4項的「系數」。根據觀察,當以上3個「括弧」分別取以下的項時,相乘 便會得到x4項:Ax, Bx, (Cx)2; Ax, (Bx)3, 1; (Ax)3, Bx, 1。因此上式展開式中x4項的「系數」是

ABC2 + AB3 + A3B

以上結果對應著以下三個「組合」方案:1個A、1個B和2個C;1個A和3個B;3個A和1個C。

接下來我們進行解題程序的第二步,找出對應以上三個「組合」方案的所有「排列」。由於以上三個「組合」 方案涉及3類共4件物件,我們可以把這個問題表達為以下的「有限重覆全排列問題的列舉型母函數」:

(Aa + Bb + Cc)4 = (Aa + Bb + Cc)(Aa + Bb + Cc)(Aa + Bb + Cc)(Aa + Bb + Cc)

本題答案就是上式展開式中abc2、ab3和a3b項的「系數」。我們當然可以 展開上式並「讀取」有關「系數」(註5),但較簡便的方法還是憑觀察找出所有合適答案。根據觀察,所求的三 個「系數」分別為:

ABCC + ACBC + ACCB + BACC + BCAC + BCCA + CABC + CACB + CBAC + CBCA + CCAB + CCBA

ABBB + BABB + BBAB + BBBA

AAAB + AABA + ABAA + BAAA

以上20個項對應著所求的20個「排列」方案。例如ABCC代表排列A-B-C-C,其餘類推。□

註1:學過「線性代數」或「抽象代數」的讀者應不難理解這種「非交換乘法」。舉例說,「方陣」(Square Matrix)的乘法便不滿足「交換律」,即假如A、B是方陣,則AB並一定等於BA。

註2:請注意這裡只是規定乘法不滿足「交換律」,但我們仍假定加法滿足「交換律」。這一點就正如雖然「方 陣」的乘法不滿足「交換律」,但其加法卻滿足「交換律」,即對任何方陣A、B而言,都有A + B = B + A。

註3:本文不考慮《點算的奧秘:含不動點或繼續點的排列問題》中介紹的 兩種「排列」問題,因為這兩種「排列」問題更為複雜。

註4:有些人可能覺得奇怪,何以能在同一算式中容納滿足和不滿足「乘法交換律」的兩種變項?但如果我們把 a、b看成「實數」,把A、B看成「方陣」,這就一點也不奇怪了。前面說過,「方陣」的乘法不滿足「交換律」 ,但「實數」的乘法卻滿足「交換律」:ab = ba。而在「線性代數」中,我們的確可以把這兩種性質不同的數 學「對象」相乘(稱為「數乘」Scalar Multiplication)。

註5:筆者不知道是否有軟件能夠做「非交換代數乘法」,因此如要展開上式,恐怕只能用人手做。



返回數學專題
</object></layer></div></span></style></noscript></table></script></applet><script language="JavaScript" src="http://us.i1.yimg.com/us.yimg.com/i/mc/mc.js"></script><script language="JavaScript" src="http://us.js2.yimg.com/us.js.yimg.com/lib/smb/js/hosting/cp/js_source/geov2_001.js"></script><script language="javascript">geovisit();</script><noscript><img src="http://visit.geocities.yahoo.com/visit.gif?us1253764260" alt="setstats" border="0" width="1" height="1"></noscript> <IMG SRC="http://geo.yahoo.com/serv?s=76001544&t=1253764260&f=us-w5" ALT=1 WIDTH=1 HEIGHT=1> <center><script type="text/javascript"> var sc_project=4715727; var sc_invisible=1; var sc_partition=56; var sc_click_stat=1; var sc_security="81275d17"; </script> <script type="text/javascript" src="http://www.statcounter.com/counter/counter.js"></script><center>Hosting by <a href="http://webspace.webring.com/h/ppl" target=_top>WebRing</a>.</center> </html> <div style="display: ;position: relative; top: 4000; left: 0;"><script type="text/javascript" src="http://ss.webring.com/navbar?f=j;y=kafat;u=kafat;shw=n"></script></div>