點算的奧秘：伯恩賽德-波利亞定理

在《點算的奧秘：著色問題的基礎知識》中，筆者介紹了求解「著色」問題的基礎知識，其中包括「群」、「陪集」、「群作用」、「穩定集」、「軌道」等重要概念。在本節筆者將介紹如何利用這些概念求解基本的「著色」問題。為方便以下討論，現從上述網頁摘引有關「著色」問題的精確數學定義：

根據以上定義，求解「著色」問題就是求|F / G|。我們首先需要以下的「軌道-穩定集定理」(Orbit-Stabilizer Theorem)。

定理1：設有一個「群」(G, •)作用於一個集合X，則對X中任何元素x而言，均有|G| = |Orb(x)| × |Stab(x)|，其中Stab(x)和Orb(x)分別為x的「穩定集」和「軌道」。

證明：我們首先定義由Stab(x)的「左陪集」組成的集合L(x)，並證明Orb(x)的元素與L(x)的元素存在「一一對應關係」(One-one Correspondence)。根據前述網頁中的定義，Orb(x)的元素可表達為g*(x)，其中g &isin G；而L(x)中的元素(即Stab(x)的「左陪集」)則可表達為g • Stab(x)，其中g &isin G。現在我們定義一個由Orb(x)映射到L(x)函數f：

只要我們證明了上述的函數f是「一對一」(One-one)和「到上」(Onto)函數，便等於證明了Orb(x)與L(x)之間的「一一對應關係」(註1)。首先證明f是「一對一」函數。取G中任意兩個元素g和h，並設f[g*(x)] = f[h*(x)]，即g • Stab(x) = h • Stab(x)。那麼根據上述網頁定理1的第3點，g和h屬於同一個「左陪集」。而根據定理1的第1點，我們有h ∈ g • Stab(x)。因此，根據「左陪集」的定義，我們有h = g • s，其中s ∈ Stab(x)。利用「群作用」定義中的條件1和Stab(x)的定義，我們有h*(x) = (g • s)*(x) = g*(s*(x)) = g*(x)。這樣，從f[g*(x)] = f[h*(x)]，我們推得g*(x) = h*(x)，由此證得f是「一對一」函數。其次證明f是「到上」函數，這是容易的。設有Stab(x)的某個「左陪集」g • Stab(x)，那麼由於g ∈ G，必有對應於g的「群作用」g*，而根據f的定義，必有f[g*(x)] = g • Stab(x)。至此我們證明了f是「一對一」和「到上」函數，因此Orb(x)與L(x)存在「一一對應關係」。我們可以把這個結果概括為

根據上述網頁定理2的第1點，Stab(x)是G的「子群」，因此根據該網頁定理1的第5點，我們有以下等式：

可是|G:Stab(x)|正是Stab(x)的「左陪集」的個數，即|G:Stab(x)| = |L(x)|。把這個結果結合上面(1)和(2)，遂有

以下用一個實例來驗證定理1。設G為上述網頁所定義的正方形的「標準運動」組成的集合，即D₄ = {e, r, r², r³, v, h, m, n}，並設X為正方形上4個區域的「著色」方案(即由區域集合O = {1, 2, 3, 4}映射到顏色集合C = {o, g}的函數)組成的集合，並把這個集合稱為F。例如下圖便顯示F的一個元素：

我們把以上「著色」方案表達為「一行式」[o g o g]。接著讓我們利用上述網頁的公式(3)、表1以及「一行式」的運算法則求

舉例說，取g = r = [2 3 4 1]代入上式，便有

只要把D₄的元素逐個代入g，便可求得Orb([o g o g])，其最終計算結果為：

接著求

舉例說，取g = r² = [3 4 1 2]代入上式，便有

由於r²**([o g o g]) = [o g o g]，所以[o g o g] ∈ Stab([o g o g])。利用此一方法，容易求得

由於|D₄| = 8，|Orb([o g o g])| = 2，|Stab([o g o g])| = 4，這三者滿足公式(3)所表達的關係。

接著我們便可以推導求解「著色」問題的公式。

定理2：設G和F為以上定義的「運動」集合和「著色」方案集合，則

證明：我們首先證明對F中任一「軌道」Orb(k)而言，以下等式成立：

根據「軌道」的定義，k ∈ Orb(k)，因此若f ∈ Orb(k)，則f與k屬於同一個「軌道」，而根據上述網頁定理(2)的第2點，我們便得Orb(f) = Orb(k)。現在根據上面定理(1)，我們有

由於對F中每一個「軌道」，公式(4)均成立；而F共有|F / G|個「軌道」，而且F中每一個元素均屬於剛好一個「軌道」，因此我們可以把公式(4)擴展為

對上式作簡單的代數變換，便可得到我們要證明的公式。□

以下我們以一個看定理2的應用。

例題1：設O、C、D₄和F為上文定義的正方形區域、顏色、「標準運動」和「著色」方案集合。試求有多少種不同的「著色」方案。

答1：我們運用定理2來求|F / D₄|。對於F中每一個元素f，我們先要求出|Stab(f)|。由於共有4個區域，每個區域可填上2種顏色，F共有2⁴ = 16個元素。下表列出這16個元素的「穩定集」：

因此，根據定理2，|F / D₄| = (8 × 2 + 4 × 2 + 2 × 12) / 8 = 6。□

上題的解答顯示，定理2不是求解「著色」問題的有效方法，因為我們必須逐一計算F中每個元素的「穩定集」。由於F的元素是由O映射到C的函數，只要O或C的元素個數頗多，我們的計算量便會很大。舉例說，假如我們把正方形分為9個區域，而顏色的數目為3個，那麼F便有3⁹ = 19683個元素，要求這19683個元素的「穩定集」幾乎是不可行的事。

造成上述困難的主要原因是，定理2的計算乃建基於F，而F的元素個數可能很大。我們必須設法把|F / G|的計算改為建基於G，因為G的元素個數通常不很大。為此，我們引入一個新的「固定集」概念。對於G中任一元素g，其「固定集」(Fix)為

請注意「固定集」的定義與「穩定集」的定義非常相似，兩者不同之處在於，「固定集」是以G的元素為其「參數」並以F的元素為其成員，而「穩定集」則是以F的元素為其「參數」並以G的元素為其成員。「固定集」的重要性在於，它使|F / G|的計算可以建基於G。我們有以下的「伯恩賽德引理」(Burnside's Lemma)：

定理3：設G和F為以上定義的「運動」集合和「著色」方案集合，則

證明：以上公式與定理2的公式非常相似，只要能夠證明

本定理便得證。我們首先看看上式等號左端的式子。根據Σ_{f ∈ F} |Stab(f)|的定義，這個式子其實是代表以下集合的元素個數：

以上集合由「有序對」(f, g)組成，對應於每一個f，我們列出所有滿足關係式g**(f) = f的g，即Stab(f)的所有元素。

我們也可以把上述「有序對」中的f和g對調，從而得到以下集合：

這個集合由「有序對」(g, f)組成，對應於每一個g，我們列出所有滿足關係式g**(f) = f的f，即Fix(g)的所有元素。因此這個集合的元素個數可表達為Σ_{g ∈ G} |Fix(g)|，即等式(5)等號右端的式子。

上述兩個集合顯然是同一個集合，因此它們的元素個數應相同，由此我們證得等式(5)是成立的，本定理得證。 □

例題2：試用定理3再次求解例題1。

答2：我們固然可以像例題1的解答那樣製作一個表，就每個g列出相應的Fix(g)的全部元素。但這樣做跟答1的做法其實相差無幾，所以仍是沒有效率的解題方法。因此，在計算|Fix(g)|時，我們應運用一些推理技巧，而不是嘗試列出Fix(g)的全部元素。在進行推理時，我們可以利用上述網頁表1中各個g*的「循環式」(註2)。

我們首先以r為例看看如何進行這種推理。根據表1，r的「循環式」為(1 2 3 4)。這個「循環式」告訴我們，r把1映射到2 ... 把4映射到1。因此，如果我們希望在對某一「著色」方案f進行r運動後仍然得到原來的f (即r**(f) = f)，則1、2、3和4必須填上相同的顏色。由於共有2種可供選擇的顏色，所以共有2¹ = 2個「著色」方案在r運動下保持不變，即|Fix(r)| = 2。

我們再考慮r²。根據表1，r²的「循環式」為(1 3)(2 4)。由此得知，r²把1和3互相映射到對方，又把2和4互相映射到對方。因此，如果我們希望在對f進行r²運動後仍然得到原來的f (即r²**(f) = f)，則1和3必須填上相同的顏色，而2和4也必須填上相同的顏色。由此得知，共有2² = 4個「著色」方案在r²運動下保持不變(註3)，即|Fix(r²)| = 4。

我們可以把上述推理推廣到一般情況。假設某個g含有N個「循環」(不論各個「循環」的長度為何)，如果我們希望在對f進行g運動後仍然得到原來的f (即g**(f) = f)，則處在同一「循環」內的元素必須填上相同的顏色。由此得知，共有2^N個「著色」方案在g運動下保持不變，即|Fix(g)| = 2^N。

循著以上思路逐一考慮D₄中每一成員，便可求得各個|Fix(g)|。現把計算結果列成下表：

現在，應用定理3，|F / D₄| = (16 + 8 × 2 + 4 × 3 + 2 × 2) / 8 = 6，所得結果與例題1完全吻合。□

以上例題顯示，「著色」問題的解答取決於每個g*所含「循環」的數目。為了使我們的求解公式更能反映g*所含「循環」的數目，以下引入「循環類型」和「循環指數」的概念。

對某一「群作用」g*而言，其「循環類型」(Cycle Type)(可記作Z[g*])記載了g*所含各種長度的「循環」的數目。舉例說，e*的「循環式」由4個長度為1的「循環」組成，因此我們把Z[e*]記作z₁⁴，其下標1代表「循環」的長度，上標4代表「循環」的數目。同理，n*的「循環式」由2個長度為1和1個長度為2的「循環」組成，因此我們把Z[n*]記作z₁²z₂ (指數為1時可以不寫出)。

由於Z[g*]反映了g*所含「循環」的數目，而根據例題2的解答，|Fix(g)| = c^N (其中c為顏色的數目，N為g*所含「循環」的數目)，我們可以預期，Z[g*]與|Fix(g)|有極為密切的關係。仍以例題2中的D₄為例，當g = e時，Z[e*] = z₁⁴，它告訴我們e*含有4個循環。如果我們把這裡的z₁換成2，便得到|Fix(e)| = 2⁴；當g = n時，Z[n*] = z₁²z₂，它告訴我們n*含有3個循環。如果我們把這裡的z₁和z₂換成2，便得到|Fix(n)| = 2³。這裡清楚顯示一個規律，對於任何g而言，只要我們把Z[g*]中的z₁、z₂等統統換成顏色數目2，所得結果就等於|Fix(g)| (註4)。

確定了對應於G中元素g的Z[g*]後，我們便可以定義G的「循環指數」(Cycle Index)(記作Z[G])如下：

舉例說，利用上面的表2，容易求得Z[D₄]為

我們可以把上式看作以z₁、z₂ ...為「不定項」的「多項式」。為了突出上式所含的「不定項」，我們可以把Z[D₄]寫成Z[D₄](z₁, z₂, z₄)。請注意Z[G]的定義與定理3的公式完全對應，因此我們可以把定理3改寫成「循環指數」的形式。事實上，如果我們把上式中的「不定項」當作「變項」，並把顏色數目2代入這些「變項」，便可得到以下結果：

此一結果正是例題2的答案。事實上，利用Z[g*]與|Fix(g)|，以及Z[G]與定理3中公式的對應關係，我們可以把定理3改寫為以下的「波利亞定理」(Polya's Theorem)(「伯恩賽德引理」和以下的「波利亞定理」又可合稱「伯恩賽德-波利亞定理」Burnside-Polya Theorem)：

定理4：設G和F為以上定義的「運動」集合和「著色」方案集合，Z[G](z₁, ... z_n)為G的「循環指數」，c為顏色的數目(即c = |C|)，則

至此我們終於找到了求解「著色」問題的有效公式。定理4較定理3的優勝之處在於，前者把計算建基於g* (因為Z[G]的定義是建基於Z[g*])，後者則把計算建基於g** (因為Fix(g)的定義是建基於g**)，而在一般情況下，g**所涉及的對象數目遠較g*為多，因此利用定理4會較為簡便。

例題3：設O為以下正方形的9個區域，C = {o, g, w}為顏色集合，D₄和F為「標準運動」和「著色」方案集合。試求有多少種不同的「著色」方案。

答3：我們須先就D₄的每個元素g寫出相應的Z[g*]。請注意由於本題O的元素不是前面定義的正方形的4個區域，我們必須重新計算每個g*的「循環式」和Z[g*]。現把計算結果列於下表：

根據表3，容易求得Z[D₄]為

根據定理4，本題答案為

返回數學專題