圖解Pólya計數法

Posted By Mr. Thursday

不知道各位閱讀一篇blog的時候都是什麼樣子的時間?剛吃飽飯?剛做完劇烈運動?還是深夜還沒睡覺的時候?也許各位只有10分鐘左右的注意力可以閱讀這篇文章,但是數學相關的內容常常需要很多血液在大腦才能了解,在各位讀者大腦缺血的狀態下,硬是要大家腦充血,實在是有點殘酷。
不過這篇文章有另外一個嘗試,就是使用圖解的方式,讓大家可以用比較輕鬆的方式了解還滿有難度的Pólya計數法。各位讀者不必學過很難的定理,只要會「加法」、「乘法」、以及對三度空間有一些些想像力,就可以了解!願意試試看嗎?讓我們往下繼續閱讀吧!
開始之前先把Pólya本尊以及他發明的公式列在下面,今天的目標就是讓各位經鬆了解這個公式,甚至一輩子都不會忘記喔!

————————————————————————————————————————————–

加法原理和乘法原理

不知道各位是否還記得中學時候學到的排列組合。在這部分我們稍微有些直覺上的複習。首先讓我們注意到如果今天有一個瓷磚,然後我們有兩種顏色,但是瓷磚一次只能上一種顏色,那麼有幾種著色法呢? 我想大家應該都會回答是兩種。譬如說下面這張圖:

問號代表一個還沒上色的瓷磚。右手邊代表這兩種可能的著色方法:紅色、「或是」藍色。

接下來讓我們推廣到兩個瓷磚的時候。如果有兩種顏色 (紅色、藍色),分別塗在兩個瓷磚上面,總共有幾種著色呢?讓我們視覺化這個問題的答案:

所以我們可以看到,有四種著色方法。在繼續討論之前,我們想做一件事,就是跨越「符號化」的鴻溝。首先,上面四種著色方法,我們如果用中文來唸,分別就是:「紅紅」、「紅藍」、「藍紅」、「藍藍」。如果我們用英文來代表呢?紅色是Red,所以用字母R來代表,藍色是Blue,所以用B來代表,那麼剛才四種著色方法,用英文字母來表示,就變成RR、RB、BR、BB了!

跨越符號化的鴻溝之後,我們要開始進入這一段的重點:加法原理和乘法原理。

我想各位應該都知道加法,譬如說 1+1 = 2。各位也應該都知道乘法,譬如說3*9 = 27。

那麼加法和乘法,和排列組合有什麼關係呢?我想可以用下面這種對應:

「或者」(OR) 的關係:用加法表示

「並且」(AND) 的關係:用乘法表示

拿上面兩個瓷磚著色個數為例,第一個瓷磚可以著上紅色「或者」藍色,第二個瓷磚可以著上紅色「或者」藍色。然後對每一個著色方法來說,是第一塊瓷磚是顏色X「並且」第二塊瓷磚是顏色Y,算是一種著色方法。所以要用R和B來表示這四種著色方法,我們可以套用數學的加法和乘法寫成:

(第一塊瓷磚是紅色或是藍色) 而且 (第二塊瓷磚是紅色或是藍色)

= (R+B) * (R+B)

= RR + RB + BR + BB

第一個括號裡面的R+B就是代表著第一塊瓷磚可以著上紅色(R)「或者」藍色(B),第二個括號表示第一塊瓷磚可以著上紅色(R)「或者」藍色(B)。中間相乘代表第一塊瓷磚是某某顏色「並且」第二塊瓷磚是某某顏色的時候,算成一種「著色方法」。

接下來要從「符號化」的鴻溝,跨越「數量化」的鴻溝。數學把世界上的東西符號化之後,大部分專注在「量」的資訊上面。像上面的例子,我們用符號RR, RB, BR, BB列出用紅色和藍色,來塗兩塊瓷磚,有哪幾種著色方法。如果只專注在「量」的資訊,也就是說,我們只想知道有「幾種」著色法,而不用全部的著色法全部唸出來,那麼答案是 4 種。

那麼上面的乘法原理和加法原理產生的式子,要怎麼套用呢?只要把R和B,分別換成數字1就可以了:

(1 + 1) * (1 + 1)

= 2 * 2 = 4

就是答案「4種」了!

所以我們跨越了「符號化」和「數量化」的鴻溝,並且了解了加法可以代表「或者」,乘法可以代表「並且」的關係。在繼續下去之前,我們先從兩塊瓷磚推廣成三塊瓷磚的著色個數:

如果先用中文唸,我們會知道三塊瓷磚用紅色和藍色來塗,會有「紅紅紅」(小叮噹?)、「紅紅藍」、…、「藍藍藍」,用英文念就是RRR, RRB, …, BBB。用加法原理和乘法原理來計算就是:

(第一塊瓷磚是紅色或是藍色) 而且 (第二塊瓷磚是紅色或是藍色) 而且 (第三塊瓷磚是紅色或是藍色)

= (R+B) * (R+B) * (R+B)

= RRR + RRB + RBR + RBB + BRR + BRB + BBR + BBB

把R和B代換成數字1,就可以得到著色的「個數」這個「量化」的資訊:

(1+1) * (1+1) * (1+1)

= 2 * 2 * 2 = 8

所以總共有8種著色方法,數一下上面那張圖,的確是8種著色方法!

最後附帶一提,如果一個數字乘很多次,數學裡面為了表達方便,會用「次方」來表示,譬如說10個數字2相乘,全部寫出來是2*2*2*2*2*2*2*2*2*2,寫的手好酸,所以有一個記號,在網頁上通常寫成2^10,來代表數字2相乘了10次這件事情。所以

2^10 = 2*2*2*2*2*2*2*2*2*2

OK。到目前為止,大家應該頭腦都還算清楚。有些可能中學就學過,大家都知道。不過接下來的東西,其實就是用這一段最基本的東西慢慢延伸,慢慢了解,所以到後面,還是會用到這一段提到的幾把刷子喔!

1. 加法原理和乘法原理

2. …

Pólya計數法想要解決的問題

Pólya計數法最主要想要解決的,就是一個物體用k種顏色有幾種不等價的著色法。看到「不等價」似乎有些不了解,讓我們先舉個例子:

上圖是一個正立方體,總共有六個面:上、下、左、右、前、後。如果我們用剛才提到的加法原理和乘法原理,表示量化的資訊,也就是用紅色和藍色來塗,有幾種著色方法,那麼就是有:

2 * 2 * 2 * 2 * 2 * 2 = 2^6 = 64種著色方法。

如果用英文符號來表示出每一種組合,就是

(R+B)*(R+B)*(R+B)*(R+B)*(R+B)*(R+B)

= RRRRRR+RRRRRB+…+BBBBBB

接下來,讓我們做個表示方法的變換,我們把一個正立方體的六個面的著色問題,轉換成六個瓷磚的著色問題,這兩個問題的答案會是一樣的。而剛才上面64種著色方法,如果不用RRRRRR這種符號來代表某一種著色,而是直接畫在六塊瓷磚上面,會變成像是下面這張圖:

最左上角就是RRRRRR(紅紅紅紅紅紅),六個面都塗紅色的這一組著色法,右下角就是BBBBBB(藍藍藍藍藍藍),六個面都塗藍色的這一組著色法。中間就是其他62種著色法。

說到這邊,Pólya計數法到底想解決什麼問題呢?剛才提到了「等價」,指的是說如果我們回到剛才正立方體那一張圖,一個正立方體,可以沿著不同的旋轉軸,在三度空間裡面旋轉。在旋轉的過程中,我們會發現,有時候旋轉一下,某一種著色會變成另一種著色,也就是說,透過某個旋轉的過程,某一種著色方法其實和另一種著色方法「等價」。

舉個具體的例子,下面這個正立方體,上、下兩面的顏色先不管,中間的前後左右四個面,分別是紅藍紅藍(RBRB)的排列。如果我把正立方體沿著圖中的軸線逆時針旋轉,那麼中間的前後左右四個面,會變成藍紅藍紅(BRBR)。

也就是說,透過逆時針旋轉90度,在原先64種著色方法裡面,居然至少有兩種方法,是「等價」的,在原來64種方法裡面,這兩種著色被視為不一樣的著色,但是在三度空間裡面如果讓正立方體自由旋轉,我們會發現某些旋轉,像是圖裡面逆時針90度的旋轉,會讓原本算成兩次的著色方法,變成只能算一次的著色方法。

讓我們用剛才跨越鴻溝的時候一樣,用中文唸一次,先把正立方體的六個面做個編號:

如果上下兩面都塗紅色,那麼剛才那張圖就是「紅紅藍紅藍紅」(RRBRBR),逆時針旋轉之後,顏色變成「紅藍紅藍紅紅」(RBRBRR)。在原來的64種組合裡面(RRRRRR+RRRRRB+…+BBBBBB),RRBRBR和RBRBRR這兩種著色是不一樣的,視為兩種著色法。如果現在我們想要計算,各種旋轉(旋轉90度、180度、270度等等)之後,等價的著色只算是一種著色,那麼會有幾種著色法?

稍微思考之後,我們可以確定,在上面那個例子裡面,答案一定會少於64種對吧?可是確切的數字是多少呢?答案是10種。

怎麼算出10種呢?就是用Pólya計數法,如果只要算量化的答案,那麼就是用Burnside定理就好。感覺困難嗎?其實也不困難,只要繼續往下看圖,並且準備好剛才的兩把刷子–加法原理和乘法原理–就可以囉!

1. 加法原理和乘法原理

2.  Pólya計數法想要解決的問題

3. …

在三度空間想像立方體旋轉

在正式接觸Pólya計數法之前,因為我們使用了正六面體的例子,而Pólya計數法需要把三度空間裡面每一種可能的對稱旋轉(可以造成兩種著色變成一種的旋轉方式)全部都列出來,才能代入他的公式,因此我們要先列出,在三度空間裡面,各種對稱的正六面體旋轉,總共有24種,約略可分成四大類,一一列舉如下:

第一類:不轉

這一類的旋轉個數只有1個

第二類:穿過兩個面面中點的旋轉軸旋轉

這一類可以分成三個子類,如果三度空間的三個方向分別是X, Y, Z,那麼下圖就是沿著z軸,穿過兩個面的中點的旋轉軸。每次旋轉可以轉90度、180度、和270度,所以有三種旋轉

Y軸方向也是同樣有90度、180度、和270度三種旋轉,X軸也是。

所以這一類總共有 3 + 3 + 3 = 9種旋轉。

第三類:邊邊的中點連線為旋轉軸的旋轉

第三類有6種旋轉,分別是六對對邊的中點連線作為旋轉軸,但是因為每個旋轉軸來說,只有180度這一次旋轉,所以就剛剛好6種旋轉,把旋轉軸畫在下面:

第四類:點點相連為選轉軸的旋轉

第四類是八個頂點,兩兩為一對,總共有四個旋轉軸,但是這四個選轉軸因為每次可以旋轉120度或者是240度,所以這一類總共有8種旋轉。旋轉軸示意圖如下:

為什麼這一類的旋轉軸,會有120度和240度兩種旋轉呢?各位可以這麼想,正立方體上面有八個頂點,兩個頂點是旋轉軸的連線,剩下六個頂點,分成兩組,一組各三個頂點,這三個頂點在旋轉的時候,剛好會依次循環到彼此的位置上面,因此360度給3個頂點區分,就是依次可以旋轉360/3 = 120度了。下面這張示意圖就把剩下六個點,三個標成咖啡色,三個標成淺藍色,代表旋轉過程中會交替循環位置的三個點。至於怎麼確定在途中這個座標軸的旋轉下,那三個點會交替循環位置?可以用這三個點相鄰的的邊和面,做輔助的比對,就會相信真的是這樣子了!

把不相關的線條去掉之後大家可能會比較明白:

所以總共有幾種旋轉呢?總共是24種旋轉!24 = 1(不轉) + (3+3+3)(3個座標軸方向,面面中點為旋轉軸,分別轉90, 180, 270度) + 6 (邊邊中點為選轉軸,正立方體12個邊總共有6對邊,每個對邊形成的旋轉軸只有180度這一種對稱旋轉) + (4+4) (正立方體8個頂點,點點相連為旋轉軸,總共有4個旋轉軸,每個旋轉軸只有120度和240度兩種旋轉)

開始頭昏了嗎?希望上面的示意圖有所幫助!正立方體這個例子,也剛好是比較不容易想的例子,因為三度空間的對稱旋轉在這邊有些複雜,後面也會提到這部分可能是Pólya計數法的困難點和延伸修改的地方。

1. 加法原理和乘法原理

2.  Pólya計數法想要解決的問題

3. 在三度空間想像立方體旋轉

4. …

應用Pólya計數法算出不等價的著色法

接下來,我們終於要開始使用Pólya計數法的公式了!

第一行就是公式,第二行是展開。這些G和f和C的符號是什麼意思呢?讓我們用中文唸一遍,不等價的顏色個數,等於(C(f1)+C(f2)+…+C(fn))除以|G|。

那|G|是什麼呢?G代表我們剛才列了24種旋轉,把他集中起來,變成一個集合,我們看到G,就好像看到剛才列出來的24種旋轉方法一樣。

那|G|是什麼呢?|G|就是代表G這個集合裡面,有多少個循環。有點昏頭了,重講一次。假設第一個旋轉用f1代表,第二個旋轉方式用f2代表,第24個旋轉用f24來代表,那麼我們看到G,就好像看到了f1, f2, …, f24這些旋轉一樣。

|G|就是說,f1, f2, …, f24這些旋轉,數一數,總共有幾個呢?當然就是「24個」啦!

那麼C(f1),或者C(f2),又是代表什麼意思呢?是說原本我們如果用乘法原哩,正立方體6個面,每個面可以用紅色或者藍色來塗,總共會有2^6 = 64種著色方法,列出來就是RRRRRR, RRRRRB, …, BBBBBB這些著色方法。

C(f1)就是說,這些著色方法裡面,有哪些著色方法,經過f1這個旋轉以後,會保持不變,譬如說64種著色方法,我們用c1, c2, …, c64這些符號來代表好了。那麼如果第15種著色方法,經過f1這個旋轉方式旋轉,還是原來第15種著色方法的外貌,那麼C(f1)就包含了c15這種著色方法。

因此,Pólya計數法和我們說,如果你要知道不等價的著色方法有幾種,有哪些,你只要告訴我有哪些旋轉方式 (f1, f2, …, f24在這個例子裡面),以及每一種旋轉方式之下,有哪些著色方法可以保持不變,把這些著色方法的個數加起來以後,再除以旋轉方式的總個數|G|,就可以知道答案!

那麼有沒有比較有系統的方式,可以算出每一個旋轉方式 (f1, f2, …, f24) 裡面,有幾種著色方法,可以經過某個旋轉方式旋轉以後,仍舊等於他自己?這邊用了一個數學表示方法,在數學裡面稱為「循環群」,不過使用起來十分直覺。讓我們先觀察下面這個例子:假設我們把正立方體六個面先做一個編號

那麼,如果有一個旋轉軸是穿過第一面和第六面的中點,像是下面這張圖:

然後繞著旋轉軸逆時針旋轉90度,那麼第二面會跑到第三面的位置,第三面會跑到第四面的位置,第四面會跑到第五面的位置,第五面會跑到第二面的位置,第一面和第六面則是各自停在原來的位置。

現在如果用一個括號,裡面分成上下兩排,上面那排數字是旋轉前,第一面到第二面的編號,下面那一排數字是正立方體依照剛才的旋轉軸逆時針旋轉90度之後,會跑道的位置,寫出來就會變成:

如果依照旋轉軸,旋轉180度呢?那麼第二面會轉到第四面的位置,第四面則是轉到第二面的位置;第三面轉到第五面的位置,第五面則是轉到第三面的位置,寫成剛才的表達方式,就是上面的第二個大括號的內容。

接下來要做什麼呢?我們可以把上面表達方式,再做一次轉換,把每個循環的數字抽離出來,所以上圖中的第一個大括號,轉換成循環群的表達方式,就變成:

[1][2 3 4 5][6]

意思就是說,旋轉軸逆時針轉90度以後,第一面和第六面待在原地,所以自己循環到自己,但是第2面、第3面、第4面、第5面,會彼此循環。

同理可推,下面第二列如果用循環群的表示法,就變成:

[1][2 4][3 5][6]

寫成這種表示法,有什麼好處呢?剛才提到對每個旋轉方法,像是f1等等,我們想要有一個有系統的方法,來算出對f1或是f15等旋轉來說,有哪些著色法經過這個旋轉後仍舊等於他自己?

回到剛才具體的例子,假設沿著剛才那個旋轉軸逆時針旋轉90度的旋轉來說,是第15個旋轉,用f15來代表,然後每一面可以用紅色和藍色來塗,那麼有哪幾種著色法,經過f15這個旋轉,仍舊等於他自己呢?如果我們用上面的編號順序來唸的話,RBBBBR這種著色法,是一種。再多列幾種,我們發現,只要第二面到第五面都是紅色,或者都是藍色,的著色法,經過f15這種旋轉,都會等於他自己。

回到循環群表示法,他的好處就是,只要把每一面可以塗上的顏色帶入每一個循環,哪幾種著色法旋轉後可以等於他自己,答案就馬上浮現,譬如說f15這種旋轉的循環群表示法是:

[1][2 3 4 5][6]

代入可能的顏色 紅與藍 R and B

[R+B]*[RRRR+BBBB]*[R+B]

[R+B]*[RRRR+BBBB]*[R+B]

= RRRRRR+RRRRRB+RBBBBR+RBBBBB+BRRRRR+BRRRRB+BBBBBR+BBBBBB

= 1*1*1*1*1*1+1*1*1*1*1*1+1*1*1*1*1*1

+1*1*1*1*1*1+1*1*1*1*1*1+1*1*1*1*1*1+1*1*1*1*1*1+1*1*1*1*1*1

= 1+1+1+1+1+1+1+1

= 8

把R和B用數字1代入,我們就可以知道,透過旋轉f15之後,有8種著色法,仍舊等於他自己。

另外,我們也可以整理一下字母表示法:

RRRRRR+RRRRRB+RBBBBR+RBBBBB+BRRRRR+BRRRRB+BBBBBR+BBBBBB

= (R^6) + (R^5)*( B^1) + (R^2)(B^4)

+ (R^1)*(B^5) + (B^1)*(R^5) + (B^2)*(R^4)

+ (B^5)*(R^1) + (B^5)

=1*(R^6) + 2*(R^5)*(B^1) + 1*(R^4)*(B^2)

+ 1*(R^2)*(B^4) + 2*(R^1)*(B^5) + 1*(B^5)

也就是說,經過f15這個旋轉之後,仍舊等於自己的著色方法有8種,在這8種著色法裡面,六面都是紅色的有一種,五個面是紅色一個面是藍色的著色方法有兩種,依此類推。

所以,整個使用Pólya計數法的流程,就變成:

(1) 列出所有的旋轉方法,在這個例子裡面就是f1, f2, …, f24總共24種旋轉法

(2) 把每一個旋轉法,列出六個面旋轉之後會到哪一個面,像這一張圖:

(3) 把上面的表示法轉換成循環群表示法,像旋轉90度的例子就是:

[1][2 3 4 5][6]

(4) 把可能的顏色,代入循環群表示法,就可以算出在某個旋轉作用下,哪些顏色轉完之後仍舊等於他自己。在這個例子用紅色(R)和藍色(B)的話,就變成:

(R+B)*(RRRR+BBBB)*(R+B)

中間填了四個RRRR以及四個BBBB是因為要表示說四個面因為旋轉之後會有關聯,因此他們的著色一定要一樣,經過這個旋轉,才會等於自己。所以四個面同時為紅色就是RRRR,四個面同時為藍色就是BBBB。我們可以用之前提過的次方表示法,讓表達稍微簡潔一些:

(R+B)*(R^4 + B^4)*(R+B)

同樣地,把R和B分別帶入數字1,我們就會得到量化的資訊,也就是有幾種,而不是把每一種可能的著色法一一列出來。

而因為這種表示法的特性,剛好就是數學裡面「生成函數」的概念,因此正式計算的時候,通常就會寫成生成函數的樣式,來做計算,但是意義上,其實就是我們這一段從頭到尾,想要表達的計算方式。

舉例來說,在上面循環群的表示法裡面,如果我們把長度為1的循環,抽象化,用變數z1來代表,長度為4的循環,抽象化用變數z4來代表,那麼f15這個旋轉的循環群表示法

[1][2 3 4 5][6]

我們忽略面的編號,只注重每個循環的長度,那麼這個循環群抽象後,就變成

z1*z4*z1

接著如果代入R和B兩種顏色的時候,我們就規定,z1代入R^1(R的一次方)+B^1(B的1次方),z2要代入(R^2 + B^2),z4則要代入(R^4 + B^4),那麼跟剛才的計算過程就會一模一樣!只是這個步驟更加系統化了!

[1][2 3 4 5][6]

=> z1*z4*z1

=> (R^1+B^1)*(R^4+B^4)*(R^1+B^1)

=> (R+B)*(RRRR+BBBB)*(R+B)

=> (第一面是RB)而且(第二面到第五面是RB)而且(第六面是RB)

=> (第一面是紅色藍色)而且(第二面到第五面是紅色藍色)而且(第六面是紅色藍色)

您看!從中文,到英文,到乘法,到次方表示法,到循環群和生成函數的互換過程,其實並沒有想像中的困難!您說是吧?

至於用生成函數系統化表示,是因為我們有24個旋轉,每個旋轉用循環群表示之後,我們化簡,然後用z1, z2, z3, z4, z5, z6分別代表長度為1的循環,長度為2的循環,一直到長度為6的循環為止。

那麼24種旋轉,有24個循環群表示法,每個循環群是z1*z4*z1或者z1*z1*z2*z2等等這種形式的化簡,譬如說z1*z4*z1可以變成z1^2 * z4等等。把這24項加起來以後,我們得到的生成函數

P(z1, z2, z3, z4, z5, z6)

= (z1^6 + 6*z1^2 * z4 + 3*z1^2 * z2^2 + 6*z2^3 + 8*z3^2)/24

這個時候再依照剛才的規則,z1代入R^1(R的一次方)+B^1(B的1次方),z2要代入(R^2 + B^2),z4則要代入(R^4 + B^4),以此類推。那麼我們就可以得到

r^6 + r^5*b +2*r^4*b^2 + 2*r^3*b^3 + 2*r^2*b^4 + r*b^5 + b^6

意思是說,不等價的著色方法裡面,六個面都是紅色的有一種,五個面紅色一個面藍色的著色法有一種,四個面是紅色兩個面是藍色的著色方法有兩種,一直到六個面都是藍色的著色法有一種。

同樣地,如果把r和b分別用數字1代入,我們就可以得到,使用紅色或者藍色來塗正方體的六個面,經過這24種旋轉之後,正立方體不等價的著色有幾種,為10種。剛好就是答案多項式的係數相加 1+1+2+2+2+1+1 = 10

有了這個公式,我們是不是就有了系統化的方法,只要知道一個立體結構,在三度空間會怎麼轉,寫成循環群的表示法,再轉換成生成函數表示法,最後代入每一個面可以塗上的顏色,那麼不等價的著色法個數,馬上就算出來了!甚至還可以知道只有某些顏色塗了K個面的著色法有幾個呢!非常神奇吧!

可是接下來我們要問:你怎麼知道這個定理的公式是100%對的呢?這就是下一段要討論的了!

1. 加法原理和乘法原理

2.  Pólya計數法想要解決的問題

3. 在三度空間想像立方體旋轉

4. 應用Pólya計數法算出不等價的著色法

5. …

Pólya計數法的圖解證明

看到這邊還有力氣的人,讓我們繼續衝刺!

在圖解證明之前,我們先看看和Pólya計數法很接近的Burnside定理的數學證明。Burnside定理和Pólya計數法唯一的差別,在於Burnside定理只能算出總共有「幾個」不等價的著色法。Pólya計數法則是除了這個「量」的資訊,還可以進一步把每一個顏色用字母r, b等列舉出來,和你說只有3面塗紅色3面塗藍色的不等價著色法有2種。

不過就證明的過程,其實是共通的。下面是筆者複習Pólya計數法的時候,參考的書籍內容,不習慣數學符號的讀者,可以稍微瀏覽後直接跳到後面的圖解部分。

———————————————————–

讓我們先從最早的地方回想起,搭配正立方體的例子。

我們有一個正六面體,每一個面可以塗兩種顏色:紅色或者藍色。根據乘法原理,總共有2^6 = 64種著色法。把這64種著色法列出來,就像是下面這張圖:

接著我們又知道,正立方體在三度空間裡面,有各種對稱的旋轉軸,旋轉之後,會讓64種著色法裡面某些著色法等價。現在我們的目標,是要計算經過各種旋轉之後 (在這個例子裡面總共有24種旋轉,參考前面講解旋轉的那一段),仍舊不等價的著色個數有多少個,根據Pólya計數法,答案是10種,還可以詳細列出每一種的顏色資訊。

讓我們再看一下Pólya計數法的公式,N(G,C)代表我們想要知道的答案,在這邊是10種不等價的著色方法。

把公式稍微移項得到

現在證明的過程,就是想要證明等號的左邊,等於右邊。

等號的左邊是什麼呢?就是10種不等價的著色法,數字10,乘上旋轉方法的個數,這邊是24。

等號右邊是每一個旋轉法之下,維持不變的著色法個數,每一個旋轉法都算一次,然後相加起來。

所以等號左邊畫成一張圖會是什麼樣子呢?

我們先把64種著色法,用64個灰階小圓球代替。

接下來等號左邊,就像是把這64顆灰階小圓球,分成10組。每一組有幾個,我們並不確定,就先畫個大概就好。

接下來,每一組裡面的每一個小灰階圓球,代表著64種著色法裡面的其中一種,可以經由24種旋轉法,轉來轉去。我們用箭頭,來代表旋轉所做的轉換。

那麼,有些旋轉,對於某種著色法來說,沒有作用,就像是RRRRRR這種著色,不管怎麼亂轉,還是等於他自己,所以24個箭頭,代表正六面體在三度空間裡面的24種旋轉法,在RRRRRR這個著色法小圓球上面,會一直指回他自己。

不過有些著色法,經過某些旋轉會等於他自己,但是經過另一些旋轉,會變成64種著色法裡面的某一種著色法,舉例來說,逆時針旋轉90度,會讓64種著色法裡面的RRBRBR著色法變成RBRBRR著色法,如下圖:

旋轉180度的時候,這RRBRBR和RBRBRR兩種著色法會各自旋轉成自己,如下圖:

所以剛才灰階小球那一張圖裡面,各種箭頭,就是代表各種旋轉,每個小球代表64種著色法裡面的一種著色法,每個小球可以有24個箭頭,代表這種著色經過24種旋轉,會變回自己,還是變成另一種等價的著色法,這就是剛才那張圖想要表達的意思了!讓我們再看一次:

現在我們把注意力,集中在每顆小灰球上面,指回自己的箭頭。這些箭頭代表24種旋轉裡面,那些會讓某一個著色法(某一個小灰球),旋轉後仍舊等於自己的那些旋轉。如果一個小灰球有8個箭頭指回自己,代表24種旋轉裡面,有8種旋轉,轉完以後那顆小灰球仍舊等於自己。

所以,每一組裡面的小球代表經過24種旋轉可以互換的著色,因此同一組的小球,代表著「等價」的著色。

不同組的小球,代表著24種旋轉不管怎麼轉,彼此都轉不到對方的著色,因此互相為不等價。譬如說RRRRRR這種著色不管怎麼轉,永遠不會轉成RRBRBR這種著色法。因為在這個正立方體的例子裡面,不等價的著色有10種,所以上面畫了10組灰色小球,64顆灰球各自落入10組等價著色區裡面。注意!每一個等價著色區的灰色小球個數,並不一定會相同,有的可能只有一顆灰球,有的可能會有8顆灰球,計數法也不在乎每一類有幾顆。

接著讓我們把上面那10組小灰球裡面某一組放大,假設我們放大的那一組等價著色裡面,有三顆灰球,代表這一組等價著色,包括了原來64種著色方法裡面的3種著色法。

同樣地,每顆灰球有24個箭頭,代表每種著色法可以經由24種旋轉來改變。有的箭頭指回自己代表某些旋轉,轉完以後,自己仍舊是自己。

接下來我們要注意,數算哪些東西呢?我們要數,每顆灰球上面,有幾個箭頭指回自己?在上面這張圖,有三顆灰球,不過每顆灰球,都有剛剛好8個箭頭會指回自己,另外16個箭頭,也會剛好8個8個,分別指向另外兩顆灰球。

為什麼呢?怎麼證明?

剛才參考書那一頁有用一個小定理 (lemma) 來證明。這邊我們想用直覺一點的講法試試。

首先,假設對某一顆著色,也就是圖裡面某一顆灰球來說,有8個箭頭指回自己,代表有8種旋轉,對這顆灰球的著色來說,轉完仍舊等於他自己。

接下來假設這顆灰球名字是A好了,另外一個球叫B。球A到球B之間的箭頭,代表某些旋轉,轉完之後,正方體的著色,會從著色A變成著色B。

現在我們好奇的是:會不會剛好也8種呢?答案為「是」。為什麼?

假設球A到球B之間的箭頭,有f1, f2, …, f8

這代表著f1這個旋轉和f2這個旋轉,都有把著色A變成著色B的效果。

如果是這樣,如果我們用f1把著色A轉成著色B,再用和f2的相反的旋轉,也就是f2的逆旋轉,就可以把著色B轉回著色A了。舉個具體的例子,假設著色A是RBRBRR,f1是逆時針轉90度,f2是逆時針轉270度,兩種旋轉都可以把著色A(RBRBRR)轉成另一個著色RRBRBR,那麼我們先用f1對著色A旋轉變成著色B,再把著色B用f2的逆旋轉,回著色A,效果就如同那些指回著色A自己的箭頭一樣。

也就是說,著色A到著色B之間的箭頭,如果兩兩一組,其中一個改成逆旋轉,那麼就等於是一個指回自己的箭頭的旋轉了!像下面這張圖一樣:

現在這個例子裡面,我們知道指回著色A自己的箭頭有8個,所以著色A和著色B之間箭頭兩兩配對,也最多有8種指回自己的方法(不然會和已知只有8個箭頭指回著色A的這個條件矛盾),也最少要有8種自己指回自己的方法(不然會和已知剛好有8個箭頭指回著色A的這個條件矛盾)。

所以根據上面的推論,一個等價區域裡面,如果有3個著色 (3個灰色球),那麼必定會有24/3 = 8個箭頭指回自己,另外16個箭頭分別8個8個指向其他灰色球。

重點是:

因此,每個等價區域裡面,不管有幾顆灰色球,每顆灰色球指向自己的箭頭,個數一定相同,而且全部加起來一定等於旋轉方法個數的總數|G|,在這個例子總共有24種旋轉,

因此我們證明了公式等號的左手邊:N(G, C) * |G|

在這個例子,我們有10個等價區域,每個區域在剛才的討論中證明了一件事,就是等價區域裡面灰色球的個數不一定相同,但是每個等價區域裡面,每個灰球指向自己的箭頭個數加總起來,必定剛好是|G|個,然後等價區域會有N(G, C)個,也就是記數法剛才求解的答案,這個例子裡面是10種不等價著色法。乘上這個例子裡面,旋轉個數總數|G| = 24,所以以這個例子來說,等號左邊是 10 * 24 = 240

現在要開始證明,等號的右手邊,在這個例子裡面是否也是240呢?

讓我們看看下圖:

剛才在等號的左手邊,我們是一類一類去數,在每個等價類裡面,每個著色,指回自己的箭頭個數,全部加起來總共240個箭頭。

等號右手邊,我們回顧一下,是計算每一種旋轉的情況下,有幾種著色會轉回自己,譬如說先討論旋轉f1,會有著色c1, c2, …, c8,在f1的旋轉下,仍舊轉回自己。上面這張圖,紅色的箭頭,就代表著f1這個旋轉,經過f1旋轉後仍舊等於自己的著色c1, c2, …, c8,散佈在不同的等價虛線區域裡面。

用同樣的方式,我們計算有幾個著色經過f2會轉回自己,有幾個著色經過f3會轉回自己,…,一直到在這個例子裡面,有幾個著色經過f24會轉回自己。我們相信數出來的個數,會和等號左邊數出來的個數相同。為什麼?

因為在上面這張圖裡面,每顆灰球指向自己的箭頭個數,加總起來,是240。只是等號左邊加總的順序,和等號右邊加總的順序,不一樣。就如同我們要加總4疊硬幣總共有幾個硬幣,我們可以一疊一疊數在加起來,也可以先算第一層有幾個硬幣,第二層有幾個硬幣,一直到最高層有幾個硬幣。兩種計算方式是一樣的。如下圖:

所以現在唯一要確定的,就是等號左邊的計算個數,真的是上面圖裡面,每顆灰球指向自己的箭頭的個數的總和。我們剛才用了幾段文字argue證明了。

等號右邊要怎麼確定也是正確的呢?

因為上面那張圖裡面,每一顆灰球都有24個箭頭,假設現在要算有幾種著色經過f1旋轉會不變,我們在圖裡面64顆球走一趟,數到有指回自己的箭頭就累加起來,那麼一定不會少算,也不會多算!

等號左邊則是10個等價區域裡面,一個區域一個區域來數。又發現對稱旋轉的作用下,位在同一個等價區域的小球如果有3個,那麼一定會有24/3 = 8個箭頭指回自己,所以每個等價區域指回自己的箭頭總數必定是24,沒有多算也沒有少算。最後每個區域的累計再全部加總起來,成為計數法公式的左手邊。

所以—等號左手邊和右手邊的數量相同!得證!

這種證明法大家看的懂嗎?…希望沒有越講越糊塗才好:)

1. 加法原理和乘法原理

2.  Pólya計數法想要解決的問題

3. 在三度空間想像立方體旋轉

4. 應用Pólya計數法算出不等價的著色法

5. Pólya計數法的圖解證明

6. …

Pólya計數法可能的擴充

終於把計數法的使用方法,以及證明兩大部分說明完畢!正立方體再三度空間的旋轉第一次想像也會比較不容易。然而如果讀者有讀到這邊,也要深深恭喜你!

接下來就探討一些稍微輕鬆的部分了。

首先上面的例子裡面,怎麼沒有考慮順時針?其實也可以考慮,只不過分子分母同時會變成兩倍。分母變成48種旋轉方法。分子變成要累計48種旋轉的不變著色的個數,因為逆時針和順時針對稱,所以個數來講也是乘以2。不過「不轉」那一項為什麼要乘以2,我還不知道怎麼解釋。

第二個難題是:如果今天是要計算正立面體上面,頂點的不等價著色個數,那麼依樣畫葫蘆,從循環群表示法,轉換到生成函數,算一算,就有答案了!

第三個難題是:如果不是正立面體,是正二十面體,那麼萬一漏算了一種旋轉,代入公式以後出來的答案不就錯了,甚至不能整除呢!這點我在複習過程中也有想到,計數法對於旋轉的個數和方式,並沒有提供系統化的方法,可以一步一步往下走,一樣畫葫蘆。不過在列舉旋轉個數的時候,也有一些經驗法則,旋轉軸通常是對稱的中心連成一直線,對稱中心可以是面面相連、邊邊相連、頂點相連為對稱旋轉軸。

不過如果不是正多邊體,恐怕就不是那麼直覺了!也許這部分,是將來可以研究的方向。或許已經有人研究過相關主題,還請專家們多多指教了!

Wikipedia: 正二十面體

1. 加法原理和乘法原理

2.  Pólya計數法想要解決的問題

3. 在三度空間想像立方體旋轉

4. 應用Pólya計數法算出不等價的著色法

5. Pólya計數法的圖解證明

6. Pólya計數法可能的擴充

7. …

對於Pólya計數法應用的想像

有了Pólya計數法,我們可以想像多種不同的應用,只要這個問題可以化約成排列組合的問題,有對稱性,以及對稱性運轉下需要消去重複的組合數,希望能夠計算出有多少種。這一類型的問題,Pólya計數法應該都派得上用場。

在這邊希望無論讀者是哪一個領域,都可以嘗試使用Pólya計數法,因為無論是哪一個領域,只要用得上,公式就在這邊,公式也證明100%正確,因此不用可惜!以下是一些跨領域的應用想像,還請各個領域的專家們多多指教。

(1) 在生物醫學的領域

有些藥物需要多種組合排列,但是化學分子也具有三度空間的性質,有時候或許某些雞尾酒是等價的,或者某些蛋白質結構是等價的,但是幾種胺基酸是已知的,這時候或許Pólya計數法可以應用得上。

(2) 注音輸入法或是語意分析

無論是注音輸入法,語意分析,語音分析,我們的已知通常是一些基本元素,但是答案是這些基本元素的各種可能組合的其中一種。我們也會有一些輸入資料是各種組合之間的等價關係,譬如說同義詞,或者是注音打到一半的片段。這時候如過要計算哪些輸出結果比較有可能,Pólya計數法也許是另外一種嘗試。

(3) 文學與藝術創作

現在內容數位化,然後數位內容的創作,仍然是以人類為主。如果用衣服的製作來類比,也許有一天,我們不一定只觀賞人類的創作,機器的創作一樣可以消費,就如同我們有機器製作的成衣,大量生產,特殊場合才需要手工訂做。

而機器要創作數位內容,除了藝術價值,以及基本的語文概念要如何建立在機器上的難題以外,我想排列組合,應該也是機器創作的一種方式。只要給予基本元素,以及等價關係的限制,利用Pólya計數法,也可以計算不等價的創作個數,以及詳細的組合方法的資訊。也許這一天的到來,可以解決數位內容走向免費的一部分問題吧?

1. 加法原理和乘法原理

2.  Pólya計數法想要解決的問題

3. 在三度空間想像立方體旋轉

4. 應用Pólya計數法算出不等價的著色法

5. Pólya計數法的圖解證明

6. Pólya計數法可能的擴充

7. 對於Pólya計數法應用的想像 8. …

心得和結語

複習Pólya計數法過程中,我的大腦似乎極度的活躍,不過我也滿enjoy這種思考的過程。除此之外,我也想到發明定理的George Pólya,在發明這個定理之前,他只有當時前輩的著作可以參考,以及眼前的一張白紙和一枝筆。切換回現代,我們可以參考的定理變多了,然而不變的是:我們如何從無變有,從一張白紙創造出一個定理?

今天我們只是理解了這個定理。然而理解之後,真正的難題,應該就是無中生有的「創造」了!願彼此勉勵從單單「理解」的人,變成有能力「創造」的人!

Wikipedia: 法國國旗

最後,無論今天是否一次了解Pólya計數法,都沒有關係。還記得小時候曾經有一題考試問說:「一面國旗三種顏色,三面國旗有幾種顏色?」回答3種是正確答案,回答9種可能是被題目騙了,但是如果我沒記錯的話,我好像回答27種,不知道那時候在想什麼。但是長大以後,只要多複習多思考,今天的我仍舊至少可以「理解」Pólya計數法。因此無論生命中有什麼挫折,也勉勵各位只要活著就有希望!願大家一起努力!明年若有機會再來理解另一條定理吧!:D

1. 加法原理和乘法原理

2.  Pólya計數法想要解決的問題

3. 在三度空間想像立方體旋轉

4. 應用Pólya計數法算出不等價的著色法

5. Pólya計數法的圖解證明

6. Pólya計數法可能的擴充

7. 對於Pólya計數法應用的想像

8. 心得和結語

附上原始paper第一頁的貼圖。響應台北花博,貼上花朵照片3張。

延伸閱讀

Pólya計數法原文paper (德文)

G. Pólya (1937). “Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen”Acta Mathematica 68 (1): 145–254. doi:10.1007/BF02546665

Burnside定理原文paper (英文)

Burnside, William (1897), Theory of groups of finite orderCambridge University Press.

組合學漫談

組合數學中的生成函數

————————————————————————

喜歡這篇文章嗎? 分享出去給作者一點鼓勵吧!
  • http://zh-tw.facebook.com/archyaloha Achy Aloha

    請問要如何與 Mr. Thursday 聯絡
    我對於這篇有很多問題想私下請教討論

  • AlcoeJ

    我還是直接讓電腦去算好了……

  • Skyerh

    真糟糕… 我是直接跳過

  • 看不懂

    mmdays 超越 mmdays

  • Pingback: Tweets that mention 圖解Pólya計數法 – MMDays -- Topsy.com()

  • http://www.facebook.com/profile.php?id=1277194911 Wormboss Yao

    太厲害了….你是數學老師嗎
    前面的說明很精彩也很詳細,證明的右式感覺比較難一點還在消化中 XD

    謝謝分享好文阿 太強了!!!

  • 小邱

    真是用心良苦~~~Good Luck!!

  • http://twitter.com/iFavz iFavz

    我有問題想請問 Mr. THursday 有關於立體數獨的組合?

    謝謝!

  • 離散考生

    圖片背景太花了

    中間一些數學式次方居然不是用上標

    閱讀上有相當困難

  • http://www.facebook.com/tzanfeng Tzan-Feng Chien

    天吶,這不是考研究所最頭痛的polya嗎!!!

  • http://pulse.yahoo.com/_GJFIWQ6URBKDMZEUENGRPYHMB4 阿強

    你講得真的太好了 我看黃大師的書都看似懂非懂,你講得太讚了!!

  • firo yang

    如此精彩的文章!!

  • http://lijunle.bitbucket.org/ LiJunLe

    看了证明前面,后面太长了,没有坚持看下去。不过真心觉得是好文章!谢谢博主。

  • Wan

    学术领域里面并不是只需要能够进行深度研究的人,同时也需要博主这样能够把复杂问题简单的表示出来的人,知识才能更好的被接受和传播,谢谢你!

  • Bitdancer

    好多繁体字,看得好吃力。。。收藏了,以后反复研读,谢谢博主啦。