我们在高中的组合数学中常常会碰到有关涂色的问题，例如：用红蓝两种颜色给正方形的四个顶点涂色，会有几种不同的方案。在当时，我们下意识的认为，正方形的四个顶点是各不相同的，即正方形是固定的。而实际上我们知道，正方形是中心对称图形，我们在得到某种方案后，经过旋转，可能会得到之后我们得到的一个看似是全新的方案，实际上这种方案被重复计算了两次，那么，如果我们要讨论涂色问题中有多少本质不同的方案，应该如何解决呢？ 今天介绍的Burnside引理，就是专门解决这类问题而生的。 基于对数据的更加抽象的建模，我们这里引出群和置换群的概念。 群的概念： 
置换群的表示： 
简单的看这些概念，群的概念其实是在集合的概念下给出几条限制条件给出的。而置换群，则是在群的基础上构造了一一映射，而所谓m阶循环其实就是一类特殊的变换，即在群的基础上，把第一个元素拖到最后然后形成一一映射来构造出一个置换群。简而言之，置换群其实是给出了群中各个元素的某种变化形态，这一点在理解后面的Burnside引理是有一定的作用的。
联系我们文章一开始就要解决的问题，再对之进行一定程度的抽象。我们想得到的是在不同的变化(旋转)后所得到的方案数，而这里的变化(上段有提到)，即生成置换群，我们想要的就是生成置换群之后未发生改变的元素，那么这里，我们就自然而然的引出了稳定核的概念。 稳定核的概念： 
单给定义抽象无比，我们结合一个例子更好的理解。 
上文中已有提及，G={g1,g2,g3……gt}中的gi表示某种生成置换群的方式，如果遍历G中的每一种方式，会生成t个置换群，t*n个元，显然这里面这t*n个元里本质上不同的只有n个元(显而易见，由n个元组成的群变化而来的)，由此不难理解"∑"左边为什么是1/∣G∣(G代表G含有的元素个数t)。 理解了这个，我们再回头解决我们在一开始就提出的问题。用红蓝两种颜色图正方形的送四个顶点，会得到多少种本质不同的方案呢？ 
运用Burnside引理，我们建立一个包含上面16种元素的群。{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}。G{g1 = (均为顺时)旋转0°,g2 = 旋转90°,g3 = 旋转180°,g4 = 旋转270°} (这里设置gi是与导致出现重复方案的操作是呼应的，设置的时候也必须把所有的情况都构造出来，这里与上面的例题进行呼应，例题中给出的g并不符合burnside引理，而只是用于理解概念，这一点读者阅读的时候需要注意)。 显然G包含的4元素。 λ1(g1) = 16 λ1(g2) = 2 λ1(g3) = 4 λ1(g4) = 2 所以本质不同的方案数是(1/4)*(16 +2 + 4 +2) = 6种。 这个引理将会给polya计数公式打下思维基础。
下面从另一个角度来理解上面的这个问题，以此来引出polya定理。 在用Burnside引理解决这个问题的时候，我们发现，需要找到一个“基群”，即我们进行生成4个置换群所基于的那个群，依旧是上面给出的16种情况。但是在实际求解问题中，这样还是给计算带来了极大的不便。而polya定理实际上就是基于Burnside引理进一步的优化并推广。 我们这里先不找“基群”的16种情况，而关注G中的各个元素gi，也就是各种生成置换群的方式。在这里，g1 = 旋转0° ， g2 = 旋转90° ， g3 = 180° ， g4 = 270° 。我们给正方形四个顶点进行标号，结合这四种生成置换群的方式，得到下图。 
我们这里再次引入群的概念(说再次引入是因为这里分析问题的角度和用Burnside引理是不同的)，将a、b、c、d四种情况与另一个“基群”进行比较，会得到下面的图示。 
这里我们再用循环对置换群进行简化得表示。这里我们可以想到，其实只要出现一个循环，就意味着会出现重复的情况。(因为这篇文章讨论的问题就是组合数学中如何筛去那些可通过循环的到的重复方案。) 举个栗子，g1其实没有循环，但是也可以看成单个元素的循环，那么它有4个循环(1)(2)(3)(4)，这种n个元表示成n个循环的情况，我们可以理解成这个置换群其实就是"基群"，既然没有变化，我们可以对它进行随意的涂色，最后得到都还将是不变元(这里在和Burnside引理进行呼应)，那么现在开始随意涂色，1点——2种情况、2点——2种情况……类推，最后g1这种置换情况会得到 2*2*2*2(当前的分析方式暂且忽略掉公式前面的1/G，我们在试图从不同的角度找到一条通向Burnside引理的路径)。同理，我们再来分析g2，仅仅表示出了一个循环(1 4 3 2)，这种情况下如果想得到不变元，那么显然4个点要涂成一样的颜色，那么这种情况下得到的等价方案是2。再来分析g3，形成了二阶循环，这里我们可以再重新的思考一下“循环”所体现的实际内涵——我们在构造涂色方案并旋转后4个顶点发生的相对位置的变化。那么我们就可以知道，如果1,2形成了(1 2)的循环，说明1,2的位置其实是相对于原始位置("基群")发生了互换。不仅两个元素构成的循环如此，多个元素构成的循环也是这样的。 知道了循环的真正含义，那么既然是位置发生了互换，那么如果在基群给出的涂色方案中，循环中对应的点图的颜色是一样的，那么置换后显然还是不变元，然后再用到分步乘法定理，就可以得到g3情况中的等价方案数——2 * 2,或写成2^2,这个过程哪个数字来相乘(即底数)是由几种涂料颜色决定的，而有几个数字乘在一起(即指数)，则是由循环的个数来决定的。 概括起来，gi情况下的等价方案数可以这样表示：m^λ(gi)，m表示涂料种数量，λ(gi)表示gi下的循环的阶数。 由此，从gi的角度看问题，可以很好的和Burnside引理联系起来，而此时，也可以正式的给出Polya定理。 
来看一下一道具体的关于用polya定理的问题。 (Problem source : hdu 3923)
In his new map, Kael can control n kind of elements and he can put m elements equal-spacedly on a magic ring and combine them to invoke a new skill. But if a arrangement can change into another by rotate the magic ring or reverse the ring along the axis, they will invoke the same skill. Now give you n and m how many different skill can Kael invoke? As the number maybe too large, just output the answer mod 1000000007.
题目大意：就是给你n种技能，然后用他们排成含有m个元素的技能环，这里要排除通过旋转和翻折得到的重复的技能环，然后让你输出可以构造多少种本质不同的技能环，最后的数据较大，只需输出其对1000000007取模后的结果。 数理分析：我们通过对题目表层大意的抽象，我们不难将其与polya定理所解决的涂色问题的模型(用n种颜色涂m个格)进行比较，发现此题中n种技能，实际上对应了模型中n种颜色，m个元素的技能环对应着模型的m个格，说明这一题是一道很典型的关于polya定理的问题。
而考虑到polya定理给出的公式，我们计算的重点是∑n^λ(g)，而这里题目会出现重复的两种情况——旋转和翻折。那么我们下面开始从这两个方面开始分析。 ①旋转：这里的旋转情况实际上是对应着polya定理G{g1,g2,g3……gi……gt}中gi——某种生成置换群的方式。假设我们生成一个正m多边形(这个联想很重要)的技能环，那么显然它可以旋转m次(每次旋转是的顶点移到相邻的顶点)。既然这样，我们现在就开始关注如何求第i次循环后生成的置换群所含有的循环数。这里我们注意到进行的是图形的变化，而我们需要通过数理的分析使之往数字的变化，这里的过渡主要运用到了数论的知识，它给编程实现奠定很重要的基础。 假设我们还没有开始旋转的时候，标记一个A点，然后旋转i次后，显然中间隔着i-1个点，此时A点的位置记作A'。那么此时我们想，如果我们从原始的A点所在的位置，顺着这个正m多边形，割i - 1个点选出一个点，一直操作下去，如果刚好能和起始的A点重合起来，那么就成功构造出来了一个正m/i多边形，而这个正m/i多边形在刚才进行的i次循环时，开始形成了一个循环，这里就对应起来polya定理中生成置换群后的某个循环。这里好像初步完成了从图到数的过渡(polya定理显然是关于数的)，注意这里仅仅找出了某个循环，我们想要的确实所有的循环数。我们现在开始进一步的从数的角度来分析图，我们把正m多边形展开，然后选点。如果我们再将之看成数轴上的点，我们发现其实是把m个数分成了m/i组，选点的结果无非两种，构造成功or构造失败，那么下面我们分开分析。 (1)而如果能够构造成功一个正m/i多边形，即i是m的约数，j那么我们最多可以构造i个正多边形，这样i就是我们想要得到的循环数。 (2)而如果构造失败呢？举个例子，m = 16 ， i = 12.每隔11个点显然构造不出正12边形，那么它就是一个循环就没有么？——非也。每隔11个点所选出的点是否在i更小的时候已经选出了呢？显然是的！我们急需从数的角度来看这个过程，i = 12显然要把m个数分成m/12个，而含有12个元素的一组中，显然还可以分成2个组、3个组、4个组，这说明在i= 2的时候构造循环多边形 的时候，很多点是在这个含有12个元素的组里的，也就是说，i = 12的时候选出的点构成的集合，是i = 2 、 3 、 4、6这些情况下选出的点集的真子集，那么现在问题就转化了，i = 12构造出来的点我们可以从i = 2 、 3 、 4、6这几种情况中寻找。这就回到了第一种情况，剩下i = 2 、 4两种情况。而我们可以看到，i = 4的情况下构造出的循环数是比i = 2构造出的循环数要多的，我们显然要找出最多的循环数，因此i = 12的循环数应该是等于i = 4。 分析了这么多，我们从图到数的过渡得到这样的 结论——第i次旋转后会出现GCD（m，i）个循环。(m与i的最大公约数)。
②翻折 可能有人会疑惑，为什么还会出现翻折情况，在我们引出理论阶段并没有翻折这种情况。的确，理论引出阶段的确没有考虑这种情况，而在这个题目中对重复情况则给了更严格的要求，那么，翻折这种情况的存在是否合理呢？ 现在有2种放技能的顺序以及2种互为翻折(不同的施放顺序会得到一个序列)得到的方案。如果召唤师选择了某种施放顺序加某一方案，会得到一个施放序列，而剩下的那个组合，和先前的方案刚好是一样，主要考虑到施放技能的顺序是不知道的，所以这里两个方案是本质一样的，因此考虑翻折情况是有必要的。 了解到考虑翻折情况的必要性，就好分析多了。进行翻折显然要找对称轴，而这就要分m奇偶了。 (1)m是奇数，m种情况，m/2 + 1 个循环。(+1是对称点过的那个点自己的循环) (2)m是偶数，对称轴又有两种情况 1.过2个顶点的对称轴，m/2 + 1个循环 (过的那2个点不需要互为循环，因此这里是2个循环) 2.过2条边的中点的对称轴，m/2个循环。
编程实现：有了以上雄厚的数理分析，那么编程实现就显得简单了很多。 1.如何得到m ， i的最大公约数？(辗转相除) 2.用polya定理的时候需要进行较大数的指数计算？如何优化？(快速幂)
以上虽然已经用到了数论分析问题的思维，但是还没完，由于要连续取模，而polya定理要/G，这里G = 2m，显然这二者是冲突的(连续取模的结果只有再进行加和乘的运算才能得到正确结果)，这里就要用到数论当中逆元的技巧，而这里由于时间有限，不展开论述，代码中会直接给出结果，笔者将会在数论专题中更详细的展开。
代码如下：
#include<stdio.h>
using namespace std;
typedef __int64 LL;
;
LL gcd(LL a , LL b)
{
) ? a : gcd(b , a % b); //辗转相除求最大公约数
}
LL pow_mod(LL a , LL b)
{
LL s = ;
while(b) //快速幂求a^b
{
)
s = (s * a)%mod;
a = (a * a)% mod;
b = b >> ;
}
return s;
}
LL polya(int m , int n) //polya定理
{
LL ans = ;
;i <= m;i++) //旋转情况
ans += pow_mod(n , gcd(m , i));
) //翻折情况：1.奇数
ans += m*pow_mod(n , m/ + );
else //翻折情况：2.偶数
ans += m / *pow_mod(n , m / ) + m / * pow_mod(n , m / +);
ans = ans % mod * pow_mod( * m , mod - ) % mod; //由于需要连续取模，这里要用到逆元
return ans;
}
int main()
{
int T , t ,m , n;
t = ;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n ,&m);
printf("Case #%d: %I64d\n",++t , polya(m , n));
}
;
}
再来看一看一道与polay定理有关的简单题目。(Problem source : 4633)
题目大意：给你k种颜色，让你对一个三阶魔方的顶点、每个小正方形、每条棱进行涂色，你可以得到多少种本质不同的方案？注意这里只能通过旋转来得到相同的方案，输出其对10007取模后的结果。
数理分析：关于涂色……算是很典型的polya定理的题目。我们来找到polya定理中给出m、n在这道题中分别指什么——显然，k种颜色与模型中n种颜色是完全对应的，而三阶魔方8个顶点、12条边、54个小正方形就对应了模型中的m，而且在这道题中，m是确定的。 根据polya定理给出的公式：1/|G|∑n^λ(g)，我们其实可以发现，只有再知道G的情况下，我们才能够利用这个公式进行计算(这显而易见，|G|表示G中含有的元素个数，循环数λ(g)也是根据G中具体的元素得来的)。所以，构造出正确的G集合使我们首先要解决的问题——这其实也是polya定理在具体问题分析中的精髓所在。
如果说上面那道题的数理分析的精髓是图到数的过渡，而这道题则更注重于单纯对图的理解与分析，以及用对称的思想来观察立体图形来快速准确的得到一些结论。 我们在这里需要是手动对这个三阶魔方进行循环、然后不同情况下(gi)的循环数。为什么要这样做呢？其源于这道题m是给定的，即三阶魔方是确定的(如果这个需要输入这题就更有意思了)，所以我们构造G中的元素是有限个而且对于人脑来说进行遍历查找循环数是可行的，因此我们在这里采取的策略构准确构造出G，并遍历其所有元素，得到我们所需要的参数(λ(g))。
基于对polya定理中循环数的深刻理解(理论上简而言之就是基群通过gi置换后形成的循环数，从实际操作的角度来说，就是这个魔方经过一定的旋转，图形的相对位置没有发生改变，此时形成的循环数，而要达到这个要求我们需要找到几何体的中心对称轴)，我们开始寻找三阶魔方的中心对称轴——过对面中点的中心对称轴、过对顶点的中心对称轴、过对棱中心的中心对称轴，有了这个初步的分类，下面我们便可以进行分别讨论。(建议自带魔方)
①静止不动的情况：这显然是要分析的，而循环数显而易见——8(点) + 12(棱) + 54(面)，这里记作g1；
②过对顶点的中心对称抽：这里我们为了更直观的观察图形，把立方体竖起来，向下面那个图那样，将体对角线(这里做旋转操作的对称轴)作为垂直方向，这样为我们用对称的思想观察图形做好了铺垫
基于对图形一步微小的处理我们不难找出循环数：4(点) + 4(边) + 18(面) 而对称轴有4条，并且能够旋转2次(g2:此情况下旋转1次 ， ……g8：……)，这在计算的时候将作为系数出现。 这里在数面的时候有一定的技巧。 数面时无非会遇到两种情况，所在平面构成了循环or没有构成循环，那么我们分别来看看这两种情况.
1.所在平面构成了循环，那么我们看看这个循环中有多少个平面，最后再乘以9即可，这里显然有2组3个面形成的循环，所以得到2 * 9 = 18个小面的循环
2.如果没有多个平面形成循环，那么显然要一个平面自己形成循环，这时可不是无脑的1 * 9，而是要具体看看这一个平面里的9个小面是如何旋转的，然后得到循环数，这在下面的情况中会遇到，这里做一下铺垫。
③ 过对面中点的中心对称轴，有旋转90°、180°、270°三种情况，而90°和270°从对称的角度来看是一样的，所以把它们两个放在一起。
1.90°、270°：2(点) + 3(线) + 15(面) ，对称轴6条，2种情况。(g8……g13)
2.180°： 4 (点) + 6(线)+ 28(面) ，对称轴6条，一种情况 (g9……g19)。
3个对称轴 ， 3种情况 (g9……g17)
④过对棱中点的中心对称轴：
180°：4(点) + 7(线) + 27(面) ， 6条对称轴(g18……g24)(这里手动记录了立方体24个对称置换群是如何生成的，这在《组合数学》中也有证明)。
编程实现：有了以上的数据，再针对关于polya公式中需要计算a^b，我们这里需要用到快速幂，然后再结合一定的处理数据的技巧，即可编程实现。
#include<stdio.h>
using namespace std;
typedef __int64 LL;
;
] = { , , , }; //指数
] = { , , , }; //系数
int k;
LL pow_mod( int a ,int b) //快速幂求a^b
{
LL s = ;
while(b)
{
)
s = (s*a)%mod;
a = (a * a)%mod;
b = b >> ;
}
return s;
}
int main()
{ int T;
scanf("%d",&T);
;i <= T;i++)
{
scanf("%d" , &k);
LL ans = ;
;j < ;j++)
ans = (ans + coefficient[j]*pow_mod(k ,Index[j])) % mod ;
ans = (ans * ) %mod; //逆元
printf("Case %d: %d\n" , i , ans);
}
;
}
参考系：《程序设计中的组合数学》 孙贺 吴文虎