在前面數節,筆者利用「群論」的概念介紹了「著色」問題及其求解方法。在求解「著色」問題的過程中,確定「運動」集合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個「排列」方案組成的:
容易證明,對任何正整數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種不同寫法:
可是上述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種「分割」方案:
據此我們知道S5的元素包含以下7種「循環類型」:
例如S5便包含以下7個元素(尚有更多未列出):
接著,我們要確定在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) |
舉例說,設有以下「集合劃分」方案:
利用上述方法,我們可以構造以下[(2 − 1)!]2[(3 − 1)!]2 = 4個「循環式」:
根據《點算的奧秘:集合劃分問題》中的公式(9),符合上述規定的「集合劃分」方案共有
個,從每一個這樣的「集合劃分」方案都可構造出上面公式(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種類型「循環式」的數目。筆者把計算結果列於下表:
「循環類型」 | 「循環式」的數目 |
---|---|
(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代表「群」。