群論與魔方:排列的表示法與運算


筆者在《群論與魔方:群論基礎知識》中指出,可以把魔方群RUBIK的元素(即對魔方的各種操作)看成對魔方54個小面的排列,從而把RUBIK看成排列群S54的子群。把魔方的操作處理成排列可幫助了解魔方的奧秘,因此本章將介紹與排列有關的幾個重要課題,包括排列的表示法、排列的複合和求逆運算,以及「對換」和排列「奇偶性」的概念。

兩行式與循環式

給定集合X,X的一個「排列」就是把X中元素排序的某個可能方案。舉例說,如果X = {A, B, C},那麼ACB和BCA就是X的兩個不同排列。在數學上,排列也可被看成X上的一個「雙射」(Bijection),即「一一到上函數」(One-one Onto Function)(註1)。為了突出排列作為一種特殊函數的性質,我們可以把排列表達為「兩行式」(Two Line Notation),例如前述的兩個排列ACB和BCA便可以表示為

在上式中,第一行和第二行分別代表「定義域」和「對應域」(對於任何「雙射」而言,它的「定義域」和「對應域」必然等同),每一列的上下對應關係代表函數關係,例如左面的「兩行式」便代表把A映射為A,把B映射為C,把C映射為B。根據組合數學,X若包含n個元素,則X共有n!個排列。

「兩行式」固然有直觀易明的優點,但在記寫上卻頗為費勁,因為每次都要寫出兩行內容重覆(僅在次序上可能不同)的元素。因此,數學家又創造出一種較簡便的記法,稱為「循環式」(Cycle Notation)。「循環式」的特點是僅用一行元素表達排列,該行元素由一或多個括弧組成。不同括弧中的元素各自獨立,彼此之間沒有映射關係;但在每個括弧中左右相鄰的任意兩個元素之間則具有映射關係,即居於左邊的元素映射到居於右邊的元素。此外,還規定每個括弧中居於最右的元素映射到居於最左的元素(因此每個括弧實際上是一個圓圈,最右和最左的元素實際上是相鄰的)。舉例說,前述的兩個排列ACB和BCA便可以表示為

(A)(BC)            (ABC)

請注意在上面第一個「循環式」中,(A)自成一個括弧,這代表把A映射為A;(BC)則表示把B映射為C,並把C映射為B (請記著每個括弧實際上是一個圓圈,所以C既在B的右邊,也在B的左邊)。

對於「循環式」,有兩點須作說明。首先,由於各個括弧各自獨立而每個括弧實際上是圓圈,在寫出「循環式」時,各個括弧可以任意次序排列,而每個括弧可以隨意以任何一個元素作為開始。例如上面兩個「循環式」便可以分別改寫為

(CB)(A)            (BCA)

其次,為盡量簡化寫法,我們約定「循環式」中任何只包含一個元素的括弧都可以略去不寫。這也就是說,我們約定任何沒有在「循環式」中寫出來的元素都各自組成一個括弧。舉例說,上面第一個「循環式」便可以改寫為

(CB)

反過來看,當我們看到以上這個「循環式」沒有寫出A時,便可推斷A自成一個括弧。

當然,當我們想寫出「恆等排列」(Identity Permutation)(即把每個元素映射為自身的排列)的「循環式」時,由於這個「循環式」的所有括弧都只包含一個元素,如果把所有括弧都略去不寫,我們的「循環式」將會是空的,所以我們又約定,對於「恆等排列」,它的「循環式」可表達為任意一個元素組成的括弧。舉例說,對於前述的X = {A, B, C}來說,它的「恆等排列」便可以表達為以下三種「循環式」中的任何一種:

(A)            (B)            (C)

排列的複合和求逆運算

由於排列是一種函數,我們可以對排列進行複合,這種複合跟上一章討論的對稱變換的複合具有相同的原理。我們可以利用「循環式」進行複合運算,其方法是把要進行複合的排列的「循環式」並排寫出來(先進行的排列寫在左邊,後進行的排列寫在右邊),然後逐個元素從左到右追蹤它們的映射結果,並把追蹤結果寫成「循環式」。

以下用一個例子說明上述運算過程。設X = {A, B, C, D, E, F},我們想求(ABCDEF)與(BACEF)進行複合的結果。首先把這兩個「循環式」並排寫出來(其中「•」代表複合運算):

(ABCDEF) • (BACEF)

我們可以從任意一個元素開始運算,故假設從A開始:第一個排列把A映射為B,第二個排列則把B映射為A,所以複合的結果就是把A映射為A。由此可知在複合結果中(A)自成一個括弧。接著計算B的映射結果:第一個排列把B映射為C,第二個排列則把C映射為E,所以複合的結果就是把B映射為E。接著計算E的映射結果:第一個排列把E映射為F,第二個排列則把F映射為B,所以複合的結果就是把E映射為B。由此可知在複合結果中(BE)自成一個括弧。接著計算C的映射結果:第一個排列把C映射為D,第二個排列不包含D,故知該排列把D映射為D,所以複合的結果就是把C映射為D。接著計算D的映射結果:第一個排列把D映射為E,第二個排列則把E映射為F,所以複合的結果就是把D映射為F。最後計算F的映射結果:第一個排列把F映射為A,第二個排列則把A映射為C,所以複合的結果就是把F映射為C。由此可知在複合結果中(CDF)自成一個括弧。綜合以上結果,便可得

(ABCDEF) • (BACEF) = (BE)(CDF)     (1)

請注意在上式右端我們無需把(A)寫出來。

正如每一個函數有其「逆函數」一樣,每一個排列也有其「逆排列」(Inverse Permutation)。給定任何排列的「循環式」,只需把該式中每個括弧中元素的排列次序顛倒過來,便可求得該排列的「逆排列」。舉例說,設X = {A, B, C, D, E, F},並有排列(ABC)(DEF)。只需把ABC和DEF分別變為CBA和FED,便可求得原來排列的逆排列,即

[(ABC)(DEF)]−1 = (CBA)(FED)

如要驗證上述求逆運算所得結果正確,可進行以下運算:

(ABC)(DEF) • (CBA)(FED) = (CBA)(FED) • (ABC)(DEF) = (A)

排列複合運算的一個性質

接著我們來看排列複合運算的一個性質,這個性質在下一章中將有重要應用。回顧(1)所示的複合運算,我們發現在運算過程中,每一個元素在進行複合的兩個排列中有時作為映射的「輸入項」(Input),有時作為映射的「輸出項」(Output)(註2)。事實上,對於任何排列複合運算,我們有以下性質。

排列複合運算性質:設X1和X2為集合X的兩個排列,那麼在計算X1 • X2的過程中,X中每一個元素在X1和X2中都會恰好作為「輸入項」一次,並恰好作為「輸出項」一次。

為理解上述性質,我們把(1)重新寫為「兩行式」的形式:

在每個「兩行式」中,上面一行的元素就是「輸入項」,而下面一行的元素就是「輸出項」。由於排列具有「雙射」的性質,所以在每個「兩行式」中,每個元素恰好出現於上、下兩行各一次。由於第一個「兩行式」的「輸出項」是作為第二個「兩行式」的「輸入項」,所以在上述運算中,A、B、C、D、E、F中的每一個在上列兩個「兩行式」中必會恰好作為「輸入項」一次,並恰好作為「輸出項」一次,由此驗證了上述「排列複合運算性質」。容易看到任何排列複合運算都必然具備上述性質。

對換與奇偶性

在「循環式」中,剛好包含兩個元素的括弧具有特殊的地位,稱為「對換」(Transposition)。容易證明,任何排列的「循環式」都可改寫成一系列「對換」的複合。舉例說,(ABC)(DEF)便有以下改寫方案(以下略去複合運算符「•」):

(ABC)(DEF) = (AB)(AC)(DE)(DF)     (2)

讀者可自行驗證上式是正確的。一般地,設有「循環式」(A1A2...An)(B1B2...Bm)...(Z1Z2...Zk),其中不包含只有一個元素的括弧,而且A1...An、B1...Bm、Z1...Zk中沒有兩個是相同的元素,那麼我們有

(A1A2...An)(B1B2...Bm)...(Z1Z2...Zk) = (A1A2)...(A1An)(B1B2)...(B1Bm)(Z1Z2)...(Z1Zk)     (3)

上式是把任何「循環式」改寫成對換複合的標準方案,但不是唯一的方案。事實上,一個「循環式」有多種改寫方案。舉例說,上述的(ABC)(DEF)便有以下改寫方案:

(ABC)(DEF) = (AB)(AC)(DE)(AF)(DA)(AF)     (4)

雖然給定某一「循環式」,其改寫方案並不唯一,但所有改寫方案所含「對換」的數目必然全是奇數,或者全是偶數(證明從略),例如上述(ABC)(DEF)的兩種改寫方案便分別包含4個和6個「對換」,而4和6都是偶數。

由此我們可以定義排列的「奇偶性」(Parity)。對於任何排列,如果可以把其「循環式」改寫成奇數個對換的複合,那麼該排列稱為「奇排列」(Odd Permutation),否則就是「偶排列」(Even Permutation)。根據這個定義,前述的(ABC)(DEF)是一個「偶排列」。

從直觀上說,「對換」代表把兩個元素對調位置。因此,把某個排列寫成「對換」的複合,就等於把該排列重新理解為一系列對調位置的結果。舉例說,(ABC)(DEF)本來代表原來排第一的元素跑到第二位置,原來排第二的元素跑到第三位置,原來排第三的元素跑到第一位置...,這個排序結果可以直觀地表達成:

ABCDEF → CABFDE

但根據(2),上述排序結果亦可透過一系列對調位置達成,即排第一、第二位的元素先對調位置,接著排第一、第三位的元素對調位置,然後排第四、第五位的元素對調位置,最後排第四、第六位的元素對調位置。上述四步對調位置的結果也可以直觀地表達成:

ABCDEF→ BACDEF
 → CABDEF
 → CABEDF
 → CABFDE

請注意以上兩個結果是一致的,由此驗證了(2)的正確性。本章所述的很多概念在魔方上有很廣泛的應用,這將留待下一章再作介紹。

註1:設F為從「定義域」(Domain) X映射到「對應域」(Codomain) Y的函數,我們說F是「一一」(One-one)的,當且僅當對X中任何兩個元素x和y,如果x ≠ y,則F(x) ≠ F(y)。F是「到上」(Onto)的,當且僅當對Y中任何元素y而言,都有X中元素x使得F(x) = y。

註2:設F把A映射為B,我們說A是F的「輸入項」(即作為「定義域」的元素),B是F的「輸出項」(即作為「對應域」的元素)。



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