波利亞定理母函數(shù)型定理

Sk=(b₁^k b₂^k … b_m^k),k=1,2…n

1.等邊三角形的3個(gè)頂點(diǎn)用紅，藍(lán)，綠3著色，有多少種方案？

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

解： 在每個(gè)面上做一條對(duì)角線的方式有2種，可認(rèn)為是面的2著色問題。但面心-面心的轉(zhuǎn)動(dòng)軸轉(zhuǎn)±90時(shí)，無(wú)不動(dòng)圖像象。除此之外，都有不動(dòng)圖像。正六面體轉(zhuǎn)動(dòng)群:面的置換表示

不動(dòng): (1)(2)(3)(4)(5)(6) (1)⁶ 1個(gè)

面面中心轉(zhuǎn)±90度 (1)²(4)¹2*3個(gè)

面面中心轉(zhuǎn)180度 (1)²(2)²3個(gè)

棱中對(duì)棱中轉(zhuǎn)180度 (2)³ 6個(gè)

對(duì)角線為軸轉(zhuǎn)±120度 (3)² 2*4個(gè)

正六面體轉(zhuǎn)動(dòng)群的階數(shù)為24

故方案數(shù)為：[26 0 3·24 8·22 6·23]/24=[8 6 4 6]/3=8

比較Pólya定理和Burnside引理

（1）Pólya定理中的群G是作用在n個(gè)對(duì)象上的置換群

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

（3）兩個(gè)群之間的聯(lián)系：群G的元素，相應(yīng)的在染色方案上也誘導(dǎo)出一個(gè)屬于G的置換p

（4）通過(guò)Pólya定理和Burnside引理的對(duì)比，我們可以看出：在a_i作用下不動(dòng)的圖象正好對(duì)應(yīng)p_i的循環(huán)節(jié)中的對(duì)象染以相同顏色得到的圖象。C₁(a_i)=m^c(p_i^{)。即同一循環(huán)中的元素都著同一種顏色的圖象在a}_i^{的作用下保持不變。}

設(shè)

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

(a)封閉性(Closure)：

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

(b)結(jié)合律(Associativity)：

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

由于結(jié)合律成立，(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!個(gè)，同一置換用這樣的表示可有n!個(gè)表示法。[1,n]上的由多個(gè)置換組成的集合在置換乘法下構(gòu)成一個(gè)群,則稱為置換群，證明如下：

（3）Burnside引理

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

波利亞(1887.12.13-1985.9.7)，美國(guó)著名數(shù)學(xué)家、教育家。1940年移居美國(guó)，先在布朗大學(xué)任教。1942年后一直在斯坦福大學(xué)任教。1953年起，任該校退休教授。以他的名字命名的波利亞計(jì)數(shù)定理則是近代組合數(shù)學(xué)的重要工具。波利亞還是杰出的數(shù)學(xué)教育家，他對(duì)數(shù)學(xué)思維一般規(guī)律的研究，堪稱是對(duì)人類思想寶庫(kù)的特殊貢獻(xiàn)。在前人研究同分異構(gòu)體計(jì)數(shù)問題的基礎(chǔ)上，波利亞在1937年以「關(guān)于群、圖與化學(xué)化合物的組合計(jì)算方法」為題，發(fā)表了長(zhǎng)達(dá)110頁(yè)、在組合數(shù)學(xué)中具有深遠(yuǎn)意義的著名論文．

波利亞的重要數(shù)學(xué)著作有《怎樣解題》、《不等式》(與哈代、李特伍德合著)、《數(shù)學(xué)的發(fā)現(xiàn)》多卷、《數(shù)學(xué)與猜想》多卷

1. 假定

若

換句話說(shuō)，若用

現(xiàn)在再來(lái)看看

則

所以

2.

群

若存在

對(duì)于一般的有：

其中