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


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

設有「物件」集合O和「顏色」集合C,並容許O作「運動」(「運動」集合用G表示),現要用C中元素對O中元素著色,並把「著色」方案表達為從O映射到C的函數(「著色」方案集合用F表示)。如果我們把任何兩個可在某「運動」下互相轉換的「著色」方案視作相同,那麼不同的「著色」方案數目便等於在G「作用」下F的「軌道」數目|F / G|。

根據以上定義,求解「著色」問題就是求|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[g*(x)] = g • Stab(x)

只要我們證明了上述的函數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)存在「一一對應關係」。我們可以把這個結果概括為

|Orb(x)| = |L(x)|    (1)

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

|G| = |G:Stab(x)| × |Stab(x)|    (2)

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

|G| = |Orb(x)| × |Stab(x)|    (3) □

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

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

Orb([o g o g]) = {g**[o g o g],其中g ∈ D4} = {[o g o g]g*−1,其中g ∈ D4}

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

[o g o g] r*−1 = [o g o g] [4 1 2 3] = [g o g o]

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

Orb([o g o g]) = {[o g o g], [g o g o]}

接著求

Stab([o g o g]) = {g ∈ D4: g**([o g o g]) = [o g o g]} = {g ∈ D4: [o g o g] g*−1 = [o g o g]}

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

[o g o g] (r2*)−1 = [o g o g] [3 4 1 2] = [o g o g]

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

Stab([o g o g]) = {e, r2, m, n}

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

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

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

|F / G| = Σf ∈ F |Stab(f)| / |G|

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

Σf ∈ Orb(k) |Stab(f)| = |G|    (4)

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

Σf ∈ Orb(k) |Stab(f)| = Σf ∈ Orb(k) |G| / |Orb(f)|
 = Σf ∈ Orb(k) |G| / |Orb(k)|
 = |Orb(k)| × |G| / |Orb(k)|
 = |G|

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

Σf ∈ F |Stab(f)| = |F / G| × |G|

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

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

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

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

表1
fStab(f)|Stab(f)|
[o o o o]{e, r, r2, r3, v, h, m, n} 8
[o o o g]{e, m}2
[o o g o]{e, n}2
[o o g g]{e, v}2
[o g o o]{e, m}2
[o g o g]{e, r2, m, n}4
[o g g o]{e, h}2
[o g g g]{e, n}2
[g o o o]{e, n}2
[g o o g]{e, h}2
[g o g o]{e, r2, m, n}4
[g o g g]{e, m}2
[g g o o]{e, v}2
[g g o g]{e, n}2
[g g g o]{e, m}2
[g g g g]{e, r, r2, r3, v, h, m, n} 8

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

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

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

Fix(g) = {f ∈ F: g**(f) = f}

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

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

|F / G| = Σg ∈ G |Fix(g)| / |G|

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

Σf ∈ F |Stab(f)| = Σg ∈ G |Fix(g)|    (5)

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

{(f, g),其中f ∈ F,g ∈ G,g**(f) = f}

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

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

{(g, f),其中g ∈ G,f ∈ F,g**(f) = f}

這個集合由「有序對」(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種可供選擇的顏色,所以共有21 = 2個「著色」方案在r運動下保持不變,即|Fix(r)| = 2。

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

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

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

表2
D4的元素gg*的「循環式」|Fix(g)|
e(1)(2)(3)(4)24 = 16
r(1 2 3 4)21 = 2
r2(1 3)(2 4)22 = 4
r3(1 4 3 2)21 = 2
v(1 2)(3 4)22 = 4
h(1 4)(2 3)22 = 4
m(1 3)(2)(4)23 = 8
n(1)(2 4)(3)23 = 8

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

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

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

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

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

Z[G] = Σg ∈ G Z[g*] / |G|

舉例說,利用上面的表2,容易求得Z[D4]為

Z[D4] = (z14 + 2z4 + 3z22 + 2z12z2) / 8

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

Z[D4](2, 2, 2) = (24 + 2 × 2 + 3 × 22 + 2 × 22 × 2) / 8 = 6

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

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

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

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

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

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

表3
D4的元素gg*的「循環式」Z[g*]
e(1)(2)(3)(4)(5)(6)(7)(8)(9)z19
r(1 7 9 3)(2 4 8 6)(5)z1z42
r2(1 9)(2 8)(3 7)(4 6)(5)z1z24
r3(1 3 9 7)(2 6 8 4)(5)z1z42
v(1 3)(2)(4 6)(5)(7 9)(8)z13z23
h(1 7)(2 8)(3 9)(4)(5)(6)z13z23
m(1)(2 4)(3 7)(5)(6 8)(9)z13z23
n(1 9)(2 6)(3)(4 8)(5)(7)z13z23

根據表3,容易求得Z[D4]為

Z[D4](z1, z2, z4) = (z19 + 2z1z42 + z1z24 + 4z13z23) / 8

根據定理4,本題答案為

Z[D4](3, 3, 3) = (39 + 2 × 3 × 32 + 3 × 34 + 4 × 33 × 33) / 8 = 2862 □


註1:「一一對應關係」(亦稱「雙射」Bijection)、「一對一」(亦稱「內射」Inijection)和「到上」(亦稱「滿射」Surjection)是「集合論」中有關函數的三種性質。根據「集合論」,如果一個函數具有「一對一」和「到上」這兩種性質,那麼它就是一個「一一對應關係」。有關上述這些性質的標準定義,請參考有關書籍或網址。

註2:請注意我們用g*來代表g對幾何圖形「組件」的「群作用」,g**則代表g對「著色」方案的「群作用」。這裡顯示我們可以用g*的資料來計算g**所產生的結果。

註3:容易看到這4個「著色」方案為:[o o o o], [o g o g], [g o g o]和[g g g g]。讀者可自行驗證,在r2運動下保持不變。

註4:有些讀者可能質疑,既然在計算|Fix(g)|時,我們只需知道g*所含「循環」的數目,而無需理會各個「循環」的長度,那麼在寫出Z[g*]時,根本無需區分z1、z2等,只需把它們統統寫成z便行了。這樣做不是更簡便嗎?筆者要指出,對於解答基本的「著色」問題來說,我們的確無需理會g*所含「循環」的長度;但對於較複雜的「著色」問題,「循環」長度卻是解題必要的資料。在下一節筆者會介紹這些較複雜的「著色」問題,屆時讀者便會看到Z[g*]的重要用途。

返回數學專題