波利亞定理

人物信息

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

背景知識

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

(a)封閉性(Closure)：

若a,b∈G，則存在c∈G，使得a·b=c。

(b)結合律(Associativity)：

任意a,b,c∈G，有(a·b)·c=a·(b·c)。

由於結合律成立，(a·b)·c=a·(b·c)可記做a·b·c；

(c)有單位元(Identity)：

存在e∈G，任意a∈G，a·e=e·a=a。

(d)有逆元(Inverse)：

任意a∈G，存在b∈G,，a·b=b·a=e.。記為b=a^-1。

(2)置換群

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

（3）Burnside引理

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