點算的奧秘:對稱群的循環式


在前面數節,筆者利用「群論」的概念介紹了「著色」問題及其求解方法。在求解「著色」問題的過程中,確 定「運動」集合G中各元素g的「循環式」是關鍵的一步,因為它決定了各元素的「循環類型」Z[g*]和G的「循 環指數」Z[G],而根據「波利亞模式定理」,我們可以利用Z[G]求取|F / G|和「波利亞模式列舉式」。

在下節,筆者將把「著色」問題的原理推廣應用到其他「點算組合學」問題,推廣「著色」問題的其中一個方 向是擴大G的定義。在前面數節,G的元素都是幾何圖形「組件」的「運動」。可是我們可以從另一個角度看這 些「運動」。從「群作用」的觀點看,G對某幾何圖形「組件」的「作用」相當於對這些「組件」進行「排列」 。舉例說,在《點算的奧秘:著色問題的基礎知識》中表1所載的各個「 一行式」便可以看成1、2、3、4這4個數字的「排列」方案。從表1可以看出,D4中不同元素對應著 不同的「排列」方案,例如v對應著2-1-4-3,r則對應著2-3-4-1。

請注意我們可以從兩個觀點看待「排列」方案。除了把2-1-4-3看成對1、2、3、4的排序外,我們還可以把它看 成集合X = {1, 2, 3, 4}上的一個函數(即把X映射到X的「一一對應關係」),這個函數把1、2、3、4分別映射 到2、1、4、3,用「一行式」寫出來就是[2 1 4 3]。把「排列」方案看成函數可更加顯明「排列」與「群作用 」之間的關係,因為「群作用」的實質也就是X上的函數。因此,以下筆者將採取函數的觀點來看待「排列」, 並把「排列」方案寫成「一行式」(或對應的「循環式」)。

由此可以推斷,「著色」問題中的集合G不必局限於由「幾何運動」組成的集合,而可以是由一般的「排列」方 案組成的集合。當然,並非任何由「排列」方案組成的集合都適合用於「著色」問題,關鍵在於集合中的元素 須構成一個「群」,即滿足「群」的定義。我們把由「排列」方案組成的群稱為「排列群」 (亦譯作「置換群」,Permutation Group)。

筆者無意介紹一般的「排列群」,只想集中介紹一種最重要的「排列群」-「對稱群」(Symmetric Group)。對於任何正整數r而言,一個「r階對稱群」(Symmetric Group of Order r)就是由r個元素的所有「排 列」方案組成的「群」,這個「群」在「抽象代數學」上一般記作Sr (註1)。由於對於r個元素而 言,應共有r!種「排列」方案,所以我們可以斷定|Sr| = r!。例如,假設我們用1、2 ... r代表 要排列的r個元素,那麼S3便是由下列3! = 6個「排列」方案組成的:

[1 2 3], [1 3 2], [2 1 3], [2 3 1], [3 1 2], [3 2 1]

容易證明,對任何正整數r而言,Sr的元素的確滿足「群」的定義,而且前面數節所曾介紹的「運 動」群D4和C4都是S4的「子群」。由此可見,Sr是較以往介 紹的「運動」群更具概括性的概念。

這裡有一點要說明的是,本節介紹的「對稱群」與以往介紹的「運動群」在表達形式方面有一個重要差別。在 前面數節,筆者使用特定的符號代表「運動群」的每個元素(例如用v代表某種「反射」運動),並用「一行式」 或「循環式」表達某「運動」作用後的結果(例如用[2 1 4 3]或(1 2)(3 4)來表達上述「反射」運動對正方形 上4個區域作用後的結果)。對於元素不多的「運動群」來說,為每個元素給定一個符號是可行的;但對「對稱 群」來說,這通常是不可行的,因為即使對於不很大的r來說,Sr都可能含有很多元素(例如 S4和S5便分別含有4! = 24和5! = 120個元素),如要為這麼多元素逐一給定一個符號 ,這將是費時失事的。因此對於「對稱群」Sr來說,我們一般只能用「一行式」或「循環式」來同 時代表Sr的某個元素以及該元素對{1, 2, ... n}作用後的結果。不過一般來說,「一行式」或「 循環式」的這種雙重身份不會造成歧義或理解上的困難,因此在本節和下節,筆者將沿襲此一習慣。

如前所述,一個「群」G中各元素的「循環式」對求解「著色」問題起著關鍵的作用,所以以下筆者將集中討論 Sr的「循環式」。我們特別關注的問題是,求Sr所含各種類型的「循環式」的數目。 不過在求解這個問題前,我們須先確定「循環式」的標準形式,這是因為基於「循環」的定義,一個長度為n的 (註2)「循環」可以有n種不同寫法。如果一個「循環式」由多個「循環」構成,它便可以有更多不同的寫法。 例如「循環式」(2 5)(1 3 4)便有2 × 3 = 6種不同寫法:

(2 5)(1 3 4); (2 5)(3 4 1); (2 5)(4 1 3); (5 2)(1 3 4); (5 2)(3 4 1); (5 2)(4 1 3)

可是上述6種寫法應被視為S5中的同一個元素。為了避免重複點算,我們規定一個「循環式」的標 準形式為,在它所含的各個「循環」中,排在第一位的元素應是在該「循環」中最小的一個數。在此規定下, 在上列6種寫法中,只有(2 5)(1 3 4)符合標準形式的規定。以下筆者在列出「循環式」時,都會寫成其標準形 式。在點算Sr的「循環式」數目時,我們只著眼於其標準形式。

現在,筆者分兩步找出Sr各種類型「循環式」的數目。首先,我們要確定Sr含有哪幾 種類型的「循環式」。由於Sr窮盡了把r個元素「排列」的一切可能性,所以Sr 的元素的「循環式」應包羅把正整數r「分割」為若干個非零部分的一切可能性。這裡我們看到了「對稱群循環 式」與「整數(無序)分割」問題之間的聯繫。事實上,我們可以借助《點算的 奧秘:整數分割問題》中介紹的「求p(r)的列舉型母函數」來找出Sr元素的所有「循環類型」 。試看以下例題。

例題1:列出S5元素的所有「循環類型」。

答1:上述網頁例題2的解答運用「求p(r)的列舉型母函數」求得5包含以下7種「分割」方案:

5; 2 + 3; 1 + 4; 1 + 2 + 2; 1 + 1 + 3; 1 + 1 + 1 + 2; 1 + 1 + 1 + 1 + 1

據此我們知道S5的元素包含以下7種「循環類型」:

(x x x x x); (x x)(x x x); (x)(x x x x); (x)(x x)(x x); (x)(x)(x x x); (x)(x)(x)(x x); (x)(x)(x)(x)(x) (註3)

例如S5便包含以下7個元素(尚有更多未列出):

(1 3 4 2 5); (2 5)(1 3 4); (2)(1 3 4 5); (2)(1 5)(3 4); (2)(5)(1 3 4); (2)(5)(1)(3 4); (2)(5)(1)(3)(4) □

接著,我們要確定在Sr中各種類型「循環式」的數目,例如在S5中有多少個元素具有 (x x)(x x x)的形式?我們把這個問題表述為:在Sr中共有多少個「循環式」具有以下「循環類型 」:這個「循環類型」包含n個「循環」,其中k1個「循環」的長度為1,k2個「循環」 的長度為2 ... kr個「循環」的長度為r,k1 ≥ 0,k2 ≥ 0 ... kr ≥ 0;k1 + 2k2 + ... rkr = r;k1 + k2 + ... kr = n?

以下筆者推導求解上述問題的公式。我們注意到,上述問題跟「集合(無序)劃分」問題有密切關係,因為把r個 數字劃歸n個「循環」類似於把r個元素劃歸n個「子集」。不過,這兩者仍有一個重要差別。在某一「子集」中 各個元素沒有次序之分,或者換句話說,把某一「子集」中的元素重新排序,所得仍為原來的「子集」。但是 如果我們把某一「循環」內的數字(撇除最小的那個數字)重新排序,便會得到一個新的「循環式」。請注意「 撇除最小的那個數字」這一點是非常重要的,因為我們在前面規定了「循環式」的標準形式是把每一「循環」 中最小的那個數字排在該「循環」的第一位,因此在重新排序時不能動最小的那個數字,否則所得結果便不是 「循環式」的標準形式。此外,由於在某一「循環」內數字的先後次序代表這些數字之間的映射關係,因此只 要我們打亂了某「循環」內數字(撇除最小的那個數字)的次序,所得結果必然代表一種新的映射關係,即一個 新的「循環式」。

綜合以上討論,給定某一「集合劃分」方案(假設有關元素為從1到r的整數),其中k1個「子集」含 有1個元素,k2個「子集」含有2個元素 ... kr個「子集」含有r個元素, k1 ≥ 0,k2 ≥ 0 ... kr ≥ 0;k1 + 2k2 + ... rkr = r;k1 + k2 + ... kr = n, 我們把每一個「子集」轉化為「循環」。轉化方法如下:假設某「子集」含有k個元素(1 ≤ k ≤ r),我 們首先把它寫成「循環」的標準形式,這是一個長度為k的「循環」。然後我們撇除「循環」中最小的那個數字 ,並對餘下的k − 1個數字進行全排列,這樣的全排列應共有(k − 1)!。我們對每一個「子集」都 這樣做,由於共有k1個「子集」含有1個元素,k2個「子集」含有2個元素 ... kr個「子集」含有r個元素,所以最終便可構造出以下數目的「循環式」:

 [(1 − 1)!]k1 [(2 − 1)!]k2 ... [(r − 1)!]kr
=(0!)k1 (1!)k2 ... [(r − 1)!]kr    (1)

舉例說,設有以下「集合劃分」方案:

{{6,8},{2,9},{3,4,10},{7,5,1}}

利用上述方法,我們可以構造以下[(2 − 1)!]2[(3 − 1)!]2 = 4個「循 環式」:

(6 8)(2 9)(3 4 10)(1 7 5); (6 8)(2 9)(3 4 10)(1 5 7);
(6 8)(2 9)(3 10 4)(1 7 5); (6 8)(2 9)(3 10 4)(1 5 7)

根據《點算的奧秘:集合劃分問題》中的公式(9),符合上述規定的「集 合劃分」方案共有

r! / [(k1)! (1!)k1 (k2)! (2!)k2 ... (kr)! (r!)kr]     (2)

個,從每一個這樣的「集合劃分」方案都可構造出上面公式(1)數目的「循環式」,因此我們所求的「循環式」 數目就是公式(1)乘以公式(2),即

 r! (0!)k1 (1!)k2 ... [(r − 1)!]kr / [(k1)! (1!)k1 (k2)! (2!)k2 ... (kr)! (r!)kr]
=r! / [(k1)! (1)k1 (k2)! (2)k2 ... (kr)! (r)kr]    (3)

例題2:試求S5各種類型「循環式」的數目。

答2:在例題1,我們已求得S5共有7種「循環類型」。現在我們應用公式(3)逐一求出這 7種類型「循環式」的數目。筆者把計算結果列於下表:

表1
「循環類型」「循環式」的數目
(x x x x x)5! / [1! (5)1] = 24
(x x)(x x x)5! / [1! (2)1 1! (3)1] = 20
(x)(x x x x)5! / [1! (1)1 1! (4)1] = 30
(x)(x x)(x x)5! / [1! (1)1 2! (2)2] = 15
(x)(x)(x x x)5! / [2! (1)2 1! (3)1] = 20
(x)(x)(x)(x x)5! / [3! (1)3 1! (2)1] = 10
(x)(x)(x)(x)(x)5! / [5! (1)5] = 1

把以上7個數字加起來便得到24 + 20 + 30 + 15 + 20 + 10 + 1 = 120,這個數剛好等於5!。由此可見,以上 點算方法沒有遺漏S5的任何一個元素。□

註1:嚴格地說,Sr只代表一個「集合」,而非「群」,因為「群」的定義須包含一個集合和該集 合上的運算。不過,在一般情況下,我們都把函數(不要忘記我們把「排列」看成函數)之間的運算定義為函數 的「複合」(Composition),所以在沒有歧義的情況下,我們可以用Sr代表「群」。

註2:我們把一個「循環」的「長度」定義為該「循環」所含元素的數目。

註3:根據前兩節,「循環類型」應用z1、z2等而非「括弧」來表達,例如這裡的第一 個「循環類型」便應表達為z5而非(x x x x x)。可是由於前兩節介紹的表達法在下節將要介紹的 「著色」問題的推廣應用中並不總能派上用場,而且這裡的「括弧」表達法較為直觀,所以在本節以及下節筆 者將使用「括弧」表達法。另請注意,這裡「括弧」中的x代表是代表各不相同的數字。



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