點算的奧秘:著色方案的母函數


《點算的奧秘:伯恩賽德-波利亞定理》中,筆者介紹了求解「著色」問題的「伯恩賽德-波利亞定理」。上節的「著色」問題都是一般的「著色」問題,這些「著色」問題除了對「物件」(即幾何圖形的「部件」)集合O、「顏色」集合C和「運動」集合G有所規定外,對所求的「著色」方案別無其他規定。可是,在某些應用中,我們所求的答案不是全體「著色」方案的數目,而是受限制的「著色」方案的數目。本文主旨就是介紹這些「受限制的著色問題」的求解方法。我們以一個例題開始。

例題1:設O = {1, 2, 3, 4}為正方形上的四個區域,C = {o, g}為顏色集合(包括橙和綠兩種顏色),D4為「標準運動」集合。試求在D4「作用」下,有多少個由兩個橙色和兩個綠色組成的「著色」方案。

答1:為了求解本題,我們須先構造「著色」方案的「母函數」。由於本題是上述網頁中例題2的變體,我們可以運用上述網頁的表2來幫助構造我們要求的「母函數」。根據表2,雖然D4含有8個元素,但若從「循環類型」的角度看,實際只有4種「循環類型」,可分別以e、r、r2和m為代表。以下逐一研究在這4種「循環類型」下保持不變的「著色」方案的「母函數」。

首先考慮e。e的「循環式」(1)(2)(3)(4)顯示,在e運動下,正方形的四個區域的顏色是各自獨立的,都可以填上o或g。如果用o + g代表可填上兩種顏色中的任何一種,那麼在e運動下四個區域的「著色」方案的「母函數」便可以表達為(o + g)4

其次考慮r。r的「循環式」(1 2 3 4)顯示,如要「著色」方案在r運動下保持不變,則四個區域必須填上相同的顏色,即四個區域必須同時為o或同時為g,此一結果可表達為o4 + g4

其次考慮r2。r2的「循環式」(1 3)(2 4)顯示,如要「著色」方案在r2運動下保持不變,則其中兩個區域必須填上相同的顏色,而另兩個區域也必須填上相同的顏色,此一結果可表達為(o2 + g2)2

最後考慮m。m的「循環式」(1 3)(2)(4)顯示,如要「著色」方案在m運動下保持不變,其中兩個區域必須填上相同的顏色,而其餘兩個區域的顏色則可自由選取,此一結果可表達為(o + g)2(o2 + g2)。

現把D4中8個元素的「循環式」、「循環類型」、「母函數」和「固定集」列於下表:

表1
D4的元素g「循環式」「循環類型」Z[g*]「母函數」 |Fix(g)|
e(1)(2)(3)(4) z14(o + g)4 24 = 16
r(1 2 3 4)z4 o4 + g42
r2(1 3)(2 4) z22 (o2 + g2)222 = 4
r3(1 4 3 2) z4o4 + g4 2
v(1 2)(3 4) z22 (o2 + g2)222 = 4
h(1 4)(2 3) z22 (o2 + g2)222 = 4
m(1 3)(2)(4) z12z2 (o + g)2(o2 + g2) 23 = 8
n(1)(2 4)(3) z12z2 (o + g)2(o2 + g2) 23 = 8

比較上表的第3和第4列,我們發現Z[g*]與相關的「母函數」之間有極為密切的關係。容易看到,只要我們把Z[g*]所含的每一個zk (k = 1, 2, 4)換為ok + gk,便得到相應的「母函數」。舉例說,Z[n*]包含z1和z2,當我們把它們分別換為o + g和o2 + g2,便得到對應於n的「母函數」。

上表的第4和第5列之間也有密切的關係。容易看到,如果把第4列的「母函數」展開並把各系數相加,所得結果正好等於第5列所列的|Fix(g)|。舉例說,把對應於e的「母函數」(o + g)4展開,便得

(o + g)4 = o4 + 4o3g + 6o2g2 + 4og3 + g4

其系數之和為1 + 4 + 6 + 4 + 1 = 16,正好等於|Fix(e)|。以上結果不是偶然的,如果我們把o和g當作「變數」,並使它們同時等於1,那麼把o = 1和g = 1代入上面的展開式,便會得到各項系數之和;而|Fix(e)|剛好正是把o = 1和g = 1代入(o + g)4的結果。

由此可見,對應於每個g的「母函數」其實包含了|Fix(g)|的資料。一個很自然的推論是,我們可以仿照上節定理3的公式,把這些「母函數」加起來並除以|D4|,看看所得結果包含甚麼信息:

 [(o + g)4 + 2(o4 + g4) + 3(o2 + g2)2 + 2(o + g)2(o2 + g2)] / 8
=o4 + o3g + 2o2g2 + og3 + g4    (1)

請注意以上展開式各項系數之和為6,正好等於上節例題2的答案。不僅如此,以上展開式還告訴我們,那6個「著色」方案是由哪些顏色構成的。由此我們知道,共有2個由兩橙兩綠組成的「著色」方案。□

在以上例題中,我們仿照上節定理3的公式求得等式(1),並從等式(1)的系數「讀取」所要求的答案。但根據上節,我們可以利用「循環指數」Z[G]把定理3的公式改寫為更濃縮的形式(即上節定理(4)的公式),因此我們也應可以借助Z[D4]把答1的結果表達為更濃縮的形式。根據上節,

Z[D4](z1, z2, z4)= Σg ∈ D4 Z[g*] / |D4|
 = (z14 + 2z4 + 3z22 + 2z12z2) / 8

容易看到,如果我們把上述Z[D4]所含的每一個zk (k = 1, 2, 4)換為ok + gk,便會得到上面的等式(1)。因此我們可以把等式(1)濃縮記為

Z[D4](o + g, o2 + g2, o4 + g4)

在「點算組合學」上,上式稱為「波利亞模式列舉式」(Polya's Pattern Inventory),因為它記載了各種模式的「著色」方案的數目,例題1所求答案就是上式展開式中o2g2的「系數」。我們可以把以上結果推廣到一般情況,從而得到以下的「波利亞模式定理」(Polya's Pattern Theorem):

定理1:設G和F為「運動」集合和「著色」方案集合,C = {C1, C2, ... Cc}為「顏色」集合,Z[G](z1, z2, ... zn)為G的「循環指數」,則

|F / G| = Z[G](c, c, ... c)

Z[G](C1 + C2 + ... Cc, C12 + C22 + ... Cc2, ... C1n + C2n + ... Ccn)

為這個「著色」問題的「波利亞模式列舉式」,上式展開式中各項的「系數」是相應模式的「著色」方案的數目。□

例題2:設O為以下正方形的9個區域,C = {o, g, w}為顏色集合(分別代表橙、綠和白色),D4和F為「標準運動」和「著色」方案集合。試求在D4「作用」下,有多少個由四橙三綠兩白組成的「著色」方案。

答3:本題是上節例題3的變體,所以可以利用上節的表3求解。根據定理1,容易求得本題的「波利亞模式列舉式」為

 Z[D4](o + g + w, o2 + g2 + w2, o4 + g4 + w4)
=[(o + g + w)9 + 2(o + g + w)(o4 + g4 + w4)2 + (o + g + w)(o2 + g2 + w2)4 + 4(o + g + w)3(o2 + g2 + w2)3] / 8

本題答案就是上式展開式中o4g3w2項的「系數」。我們固然可以把上式展開並讀取所要求的「系數」,但這樣做不僅涉及非常繁瑣的運算,而且會浪費大量的計算工夫,因為我們只需求得其中一項的「系數」。因此除非我們有合適的電腦軟件幫助我們計算,否則求解本題的較佳方法還是憑推理推算出所要求的答案。

現在就讓我們考慮上式中[ ]內各項在展開後所含o4g3w2項的「系數」。第一項(o + g + w)9是容易的,只要運用「多項式定理」便可找到所求的「系數」。根據《點算的奧秘:二項式定理和多項式定理》的公式(3),這一項在展開後o4g3w2的「系數」為

9! / (4! 3! 2!) = 1260

接著考慮第二項。這一項實際等於2(o + g + w)(o4 + g4 + w4)(o4 + g4 + w4)。由於展開這一項的結果相當於從上述三個括弧中的每一個各抽取一項出來相乘,容易看到,無論我們如何抽取,也不可能湊出g3w2。因此這一項展開後不可能包含o4g3w2項。

接著考慮第三項(o + g + w)(o2 + g2 + w2)4,這一項實際由5個括弧組成。容易看到,如果要從這5個括弧中湊出o4g3w2,我們必須從第一個括弧抽取g,並從餘下的4個括弧中湊出o4g2w2 (註1),這實際等於求(o2 + g2 + w2)4中(o2)2(g2)(w2)項的「系數」。利用「多項式定理」,容易求得這個「系數」為

4! / (2! 1! 1!) = 12

最後考慮第四項4(o + g + w)3(o2 + g2 + w2)3,這一項實際包含6個括弧,而且要運用複雜的推理。首先,根據g3的來源,可分為兩個情況:(1)全部3個g都來自前3個括弧;(2)其中一個g來自前3個括弧,餘下兩個g來自後3個括弧。我們逐一考慮這兩個情況。

情況(1):由於全部3個g都來自前3個括弧,那麼我們必須從後3個括弧中湊出o4w2,這實際等於求(o2 + g2 + w2)3中(o2)2(w2)項的「系數」(不要忘記還要把所得結果乘以4)。利用「多項式定理」,容易求得在情況1下,所求「系數」為

4 × 3! / (2! 0! 1!) = 12

情況(2):此一情況又可分為兩個「子情況」(Sub-Case):(a)兩個w (連同那一個g)都來自前3個括弧;(b)兩個w都並非來自前3個括弧(即我們是從前3個括弧中抽出一個g和兩個o)。我們逐一考慮這兩個子情況。

子情況(2a):此一情況相當於從前3個括弧中湊出gw2,並從後3個括弧中湊出o4g2。利用「多項式定理」,容易求得所求「系數」為

4 × [3! / (1! 2!)] × [3! / (2! 1!)] = 36

子情況(2b):此一情況相當於從前3個括弧中湊出go2,並從後3個括弧中湊出o2g2w2。利用「多項式定理」,容易求得所求「系數」為

4 × [3! / (1! 2!)] × [3! / (1! 1! 1!)] = 72

至此我們已窮盡所有可能性。綜合以上結果,最終求得本題答案為

(1260 + 12 + 12 + 36 + 72) / 8 = 174 □

以上討論的「著色」問題的「物件」集合O和「運動」集合G都是正方形上的平面區域及其「標準運動」D4。但其實「著色」問題可以廣泛應用於多種幾何圖形(包括平面和立體圖形),乃至「圖論」(Graph Theory)所研究的「圖」(Graph),限於篇幅,以下筆者僅以三角形為例,說明如何應用以上結果求解一般圖形的「著色」問題。先看以下「等邊三角形」:

我們首先確定,在以下討論的「著色」問題中,被「著色」的對象不是三角形上的平面區域,而是三角形的三個「頂點」,分別用A、B、C代表,即O = {A, B, C}。其次我們要確定這個「著色」問題的「運動」集合G。這個集合含有6個元素,其中3個元素是「旋轉」運動,分別為繞三角形中心按逆時針方向旋轉0度(以e代表)、120度(以r代表)和240度(以r2代表)。其餘3個元素是「反射」運動,分別為以上圖所示的三條垂直平分線為對稱軸的「反射」運動。為了明確表達各「反射」運動,我們把以穿過頂點A的垂直平分線為對稱軸的「反射」運動記為a,在這個「反射」運動下,頂點B和C對調了位置,頂點A則保持原位。類似地,我們也可定義其餘兩個「反射」運動,分別記作b和c。這樣我們便定義了上述三角形的「標準運動」集合,這個集合在「抽象代數學」上稱為「3階二面體群」(Dihedral Group of Degree 3),一般記作D3,即D3 = {e, r, r2, a, b, c}。

例題3:設O和D3為上面定義的三角形的頂點集合和「標準運動」集合,C = {o, g, w}為顏色集合(包括橙、綠和白三種顏色),F為「著色」方案集合,試求|F / D3|以及這個「著色」問題的「波利亞模式列舉式」。

答3:我們先就D3的每一個元素g,計算其相應的「循環式」和Z[g*]。現把計算結果列於下表:

表2
D3的元素gg*的「循環式」Z[g*]
e(A)(B)(C)z13
r(A B C)z3
r2(A C B)z3
a(A)(B C)z1z2
b(A C)(B)z1z2
c(A B)(C)z1z2

根據表2,容易求得Z[D3]為

Z[D3](z1, z2, z3) = (z13 + 3z1z2 + 2z3) / 6

根據定理1,|F / D3|為

Z[D3](3, 3, 3) = (33 + 3 × 3 × 3 + 2 × 3) / 6 = 10

這個「著色」問題的「波利亞模式列舉式」為

 Z[D3](o + g + w, o2 + g2 + w2, o3 + g3 + w3)
=[(o + g + w)3 + 3(o + g + w)(o2 + g2 + w2) + 2(o3 + g3 + w3)] / 6
=o3 + g3 + w3 + o2g + og2 + o2w + ow2 + g2w + gw2 + ogw

上式各項的「系數」剛好全等於1,因此上式列舉了本題的10個「著色」方案。□

註1:讀者可自行驗證,如果我們是從第一個括弧中抽取o或w,那麼我們不可能從餘下的4個括弧中湊出o3g3w2或o4g3w。
返回數學專題