波利亞定理

波利亞(1887.12.13-1985.9.7)，美國著名數學家、教育家。1940年移居美國，先在布朗大學任教。1942年後一直在斯坦福大學任教。1953年起，任該校退休教授。以他的名字命名的波利亞計數定理則是近代組合數學的重要工具。波利亞還是傑出的數學教育家，他對數學思維一般規律的研究，堪稱是對人類思想寶庫的特殊貢獻。在前人研究同分異構體計數問題的基礎上，波利亞在1937年以「關於群、圖與化學化合物的組合計算方法」為題，發表了長達110頁、在組合數學中具有深遠意義的著名論文。

波利亞的重要數學著作有《怎樣解題》、《不等式》(與哈代、李特伍德合著)、《數學的發現》多卷、《數學與猜想》多卷。

(1)群(group)的定義：給定集合G和G上的二元運算 · ，滿足下列條件稱為群：

(a)封閉性(Closure)：

若，則存在，使得。

(b)結合律(Associativity)：

任意，有。

由於結合律成立，可記做；

(c)有單位元(Identity)：

存在，任意，。

(d)有逆元(Inverse)：

任意，存在,.。記為。

（2）置換群

置換群是最重要的有限群，所有的有限群都可以用之表示。到自身的1-1映射稱為n階置換。n階置換共有n!個，同一置換用這樣的表示可有n!個表示法。上的由多個置換組成的集合在置換乘法下構成一個群，則稱為置換群，證明如下：

（3）Burnside引理

設G是[1,n]上的一個置換群。G是S的一個子群. ，G中使k元素保持不變的置換全體，稱為k不動置換類，記做。設是目標集上的置換群。每個置換都寫成不相交循環的乘積。是在置換的作用下不動點的個數，也就是長度為1的循環的個數。G將劃分成l個等價類。等價類個數為：

設 是n個對象的一個置換群，是置換的循環的個數，用m種顏色對n個對象著色, 著色方案數為：

比較Pólya定理和Burnside引理

（1）Pólya定理中的群G是作用在n個對象上的置換群

（2）Burnside引理中的群G是對這n個對象染色后的方案集合上的置換群

（3）兩個群之間的聯繫：群G的元素，相應的在染色方案上也誘導出一個屬於G的置換p

（4）通過Pólya定理和Burnside引理的對比，我們可以看出：在a作用下不動的圖象正好對應p的循環節中的對象染以相同顏色得到的圖象。

1.等邊三角形的3個頂點用紅，藍，綠3著色，有多少種方案？

2.在正6面體的每個面上任意做一條對角線，有多少方案？

解：在每個面上做一條對角線的方式有2種，可認為是面的2著色問題。但面心-面心的轉動軸轉±90時，無不動圖像象。除此之外，都有不動圖像。正六面體轉動群：面的置換表示

不動: (1)(2)(3)(4)(5)(6) (1)1個

面面中心轉±90度 (1)(4)2*3個

面面中心轉180度 (1)(2)3個

棱中對棱中轉180度 (2)6個

對角線為軸轉±120度 (3)2*4個

正六面體轉動群的階數為24

故方案數為：

1.把4個球a,a,b,b放入3個不同的盒子里，求方案數，若不允許有空盒，有多少分配方案?

解：設這4個球分別為,將4個球放入3個盒子，可抽象為對4個球的三著色。

展開后取項

的係數的係數的係數

故若不允許有空盒, 分配方案有種

2.4顆紅色珠子嵌在正6面體的4個頂點上，有多少方案？

解：當於對頂點2著色，無珠設b。

正六面體轉動群：頂點的置換表示

–不動: (1)1個

–面面中心轉±90度 (4)2*3個

–面面中心轉180度 (2)3個

–棱中對棱中轉180度(2)6個

–對角線為軸轉±120度 (1)(3)2*4個

–正六面體轉動群的階數為24

–

方案數：求br的係數

1. 假定 是作用於 的置換群，是作用於 的置換群。

若 和 是不相交的兩個集合， ，令 作用於，有

換句話說，若用 表示上面的運算，它是作用於 個元素

的置換，它對 的作用屬於 的置換，對 的作用屬於 的置換。這樣的群用 來表示，群 的階應有

現在再來看看 和、的關係如何？假如 的格式為

的格式為

則 的格式為

所以

2. 作用於，即 作用與，使， 。同樣有。

群 的階為。

若存在 和，使得，有。令 則有，而且 是使 成立的 的最小值。所以元素 是 中屬於群 的 -循環。這樣的 -循環數目為

對於一般的有：

其中， ， ， 。