参考链接：

http://www.cnblogs.com/hankers/archive/2012/08/03/2622231.html

http://blog.csdn.net/raalghul/article/details/51767941

首先来说说burnside引理是什么。

一天你正在刷题，看到一道关于染色的问题，你认为是一个傻逼题，然后认真一看题目上面写着旋转、翻转后相同的计算一次......你立刻就傻眼了。

接下来是科普时间。

首先我们考虑什么东西叫置换，例如(1,2,3,4,5)->(2,1,4,5,3)就是一个置换，1喂进去会变成2，3喂进去会变成4，喂进去一个(5,4,3,2,1)会变成(3,5,4,1,2)。

老司机们可能会把它写成这样：

例如现在三角形有三个顶点123，那么旋转本质上就是置换：(1,2,3)->(2,3,1)和(1,2,3)->(3,1,2)。

那么burnside引理就是对于k个置换，设在每个置换的作用下保持不变的染色方案为z1...zk，那么在置换意义下不同的染色方案一共有(z1+z2+...+zk)/k种。

应用的时候需要注意，例如转一次和转两次这两个置换都需要考虑，以及本身也是一个置换。

举个老例子，4个格子排成2*2的正方形，用两种颜色染色，旋转之后相同的算同一种，求不同染色方案数。

置换有四个：不动、转90°、转180°、转270°，在这些置换下不变的方案数共有16、2、4、2种，由burnside原理可以知道有(16+2+4+2)/4=6种方案。

接下来讲polya定理。首先，每个置换都可以被分解成若干不相交循环的乘积，什么意思呢？

例如上面的那个置换，我们注意到1->2->1，3->4->5->3，所以就可以写成(12)(345)，(12)、(345)就叫循环。

我们发现在每个置换的作用下保持不变的染色方案，每个循环必须染一样的颜色，所以可以发现z就等于颜色数^循环节个数。

对应到上面那个题目，我们先把正方形四个格子按从左到右从上到下1234编号。

不动：(1)(2)(3)(4)。转90°：(1234)。转180°：(13)(24)。转270°：(1432)。

那么一共也是有(2^4+2^1+2^2+2^1)/4=6种方案。

（施工中，例题待补）

polya/burnside 学习