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


《點算的奧秘:伯恩賽德-波利亞定理》中,筆者介紹了求解「著色」 問題的「伯恩賽德-波利亞定理」。上節的「著色」問題都是一般的「著色」問題,這些「著色」問題除了對「 物件」(即幾何圖形的「部件」)集合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。


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