Pólya定理是非常重要和基本的计数工具。Pólya定理是匈牙利数学家Pólya利用发生函数的方法，结合群的观点和权的概念建立起来的一个有关计数定理。Pólya定理在有关计算不同等价类的个数问题上起着重要的作用。

波利亚(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是Sn的一个子群. k∈[1,n]，G中使k元素保持不变的置换全体，称为k不动置换类，记做Zk。设G={a1,a2,…ag}是目标集[1,n]上的置换群。每个置换都写成不相交循环的乘积。c1(ak)是在置换ak的作用下不动点的个数，也就是长度为1的循环的个数。G将[1,n]划分成l个等价类。等价类个数为：l=

设 是n个对象的一个置换群，C(Pk)是置换Pk的循环的个数，用m种颜色对n个对象着色, 着色方案数为：

比较Pólya定理和Burnside引理

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

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

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

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

1.等边三角形的3个顶点用红，蓝，绿3着色，有多少种方案？

2.在正6面体的每个面上任意做一条对角线，有多少方案？

解： 在每个面上做一条对角线的方式有2种，可认为是面的2着色问题。但面心-面心的转动轴转±90时，无不动图像象。除此之外，都有不动图像。正六面体转动群:面的置换表示

不动: (1)(2)(3)(4)(5)(6) (1)6 1个

面面中心转±90度 (1)2(4)12*3个

面面中心转180度 (1)2(2)23个

棱中对棱中转180度 (2)3 6个

对角线为轴转±120度 (3)2 2*4个

正六面体转动群的阶数为24

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

Sk=(b1k+b2k+…+bmk),k=1,2…n

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

解:设这4个球分别为a1,a2,b1,b2,将4个球放入3个盒子,可抽象为对4个球的三着色。

G={e,(a1a2),(b1b2),(a1a2)(b1b2)}

l=(34+2*33+32)/4=36

P(G)=((r+b+g)4+2*(r2+b2+g2)(r+b+g)2+(r2+b2+g2)2)/4

展开后取ribjgk项,i,j,k＞0

r1b1g2的系数= r1b2g1的系数= r2b1g1的系数= (C(4,1)*C(3,1)*C(2,2)+2*C(2,1))/4=4

故若不允许有空盒, 分配方案有4*3=12种

2.4颗红色珠子嵌在正6面体的4个顶点上，有多少方案？

解 ：当于对顶点2着色，无珠设b。

正六面体转动群：顶点的置换表示

–不动: (1)8 1个

–面面中心转±90度 (4)22*3个

–面面中心转180度 (2)43个

–棱中对棱中转180度(2)46个

–对角线为轴转±120度 (1)2(3)2 2*4个

–正六面体转动群的阶数为24

–p=[(b+r)8+6(b4+r4)2 +9(b2+r2)4 +8(b+r)2(b3+r3)2]/24

方案数：求b4r4的系数 (C(8,4)+12+9*C(4,2)+8*C(2,1)*C(2,1))/24=7

1. 假定 是作用于 的置换群， 是作用于 的置换群。

若 和 是不相交的两个集合， ，令 作用于 ，有

换句话说，若用 表示上面的运算，它是作用于 个元素

的置换，它对 的作用属于 的置换，对 的作用属于 的置换。这样的群用 来表示，群 的阶应有

现在再来看看 和 、 的关系如何？假如 的格式为

的格式为

则 的格式为

所以

2. 作用于 ，即 作用与 ，使 ， 。同样有 。

群 的阶为 。

若存在 和 ，使得 ，有 。令 则有 ，而且 是使 成立的 的最小值。所以元素 是 中属于群 的 -循环.这样的 -循环数目为

对于一般的有：

其中 ， ， ，。