波利亚定理

比较Pólya定理和Burnside引理

（1）Pólya定理中的群G是作用在n个对象上的置换群

（2）Burnside引理中的群G是对这n个对象染色后的方案集合上的置换群

（3）两个群之间的联系：群G的元素，相应的在染色方案上也诱导出一个属于G的置换p

（4）通过Pólya定理和Burnside引理的对比，我们可以看出：在a_i作用下不动的图象正好对应p_i的循环节中的对象染以相同颜色得到的图象。C₁(a_i)=m^c(p_i^{)。即同一循环中的元素都着同一种颜色的图象在a}_i^{的作用下保持不变。}

波利亚(1887.12.13-1985.9.7)，美国著名数学家、教育家。1940年移居美国，先在布朗大学任教。1942年后一直在斯坦福大学任教。1953年起，任该校退休教授。以他的名字命名的波利亚计数定理则是近代组合数学的重要工具。波利亚还是杰出的数学教育家，他对数学思维一般规律的研究，堪称是对人类思想宝库的特殊贡献。在前人研究同分异构体计数问题的基础上，波利亚在1937年以「关于群、图与化学化合物的组合计算方法」为题，发表了长达110页、在组合数学中具有深远意义的著名论文．

波利亚的重要数学著作有《怎样解题》、《不等式》(与哈代、李特伍德合著)、《数学的发现》多卷、《数学与猜想》多卷

设

1. 假定

若

换句话说，若用

现在再来看看

则

所以

2.

群

若存在

对于一般的有：

其中

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

(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=

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

故方案数为：[26 0 3·24 8·22 6·23]/24=[8 6 4 6]/3=8