群及置换群的定义略去，此处我们重点讨论其性质。
置换群的元素是置换，置换的运算是连接。比如： \[ \left( \begin{matrix} 1 &2 &3\\ 2 &1 &3\\ \end{matrix} \right) \left( \begin{matrix} 1 &2 &3\\ 1 &3 &2\\ \end{matrix} \right) = \left( \begin{matrix} 1 &2 &3\\ 3 &1 &2\\ \end{matrix} \right) \]
三个置换可以表示为 \((1\ 2)(3),(1)(2\ 3),(1\ 3\ 2)\)。
理论基础
Burnside 引理
设 \(G\) 是 \(N=\{1,2,\cdots,n\}\) 上的置换群，\(G\) 是 \(N\) 上可引出不同的等价类，其中不同的等价类的个数为：
\[\frac1{|G|} \sum_{g\in G} f(g)\]
其中 \(f(g)\) 为在置换 \(g\) 的连接下不变元的个数。
注意对 \(\forall\ i,j\in G,i\cdot j\in G\)。因此假设置换集有旋转 \(90^\circ\)，则旋转 \(180^\circ\) 也要在置换集中。特别注意如果定义了自己等价于自己，则置换元也要在集合中。
这帮助我们解决了等价类计数问题，但是当规模变大时，我们不可能枚举所有元素考察是否在置换下不变。因此有时会用到组合数学或动态规划的方法进行计数，同时还需要 Polya 定理。
Polya 定理
设 \(G=a_1,a_2,\dots,a_n\) 是 \(n\) 个对象的置换群，用 \(m\) 种颜色（不一定都用上）给这 \(n\) 个对象着色，则不同的着色方案数为：
\[\frac1{|G|} \sum_{g\in G} m^{f(g)}\]
其中 \(f(g)\) 为置换 \(g\) 的循环节数。
可以理解为只有每个循环都染一种颜色，置换后才会不动。则不动点自然为 \(m\) 的循环节数次幂。这极大加快了我们计算染色等价类的速度，在一些特殊等价类（如循环同构）中甚至可以不需要真正计算循环节而采用结论。
不加证明地给出如下结论：
- 在长度为 \(n\) 的循环同构中，对移动 \(i\) 个元素的置换 \(g_i\) 有 \(f(g_i)=(n,i)\)，每个循环长度 \(len_i=\frac n{(n,i)}\)。
可以画个圆理解。有了这个结论，我们就可以化简循环同构类染色的计数。其他的等价类也有结论，但是往往比较少见，需要现推。
通常步骤：
- 列出所有置换。
- 利用 Burnside 引理和 Polya 定理计算每个置换的不变点。
- 最后除以置换总数。
有时候在第二步呆太久会忘记最后一步，因此要小心。
练习
等价类计数题目基本套公式，但更重要的通常在于如何快速计算置换中的不变点。
基础
POJ1286 Necklace of Beads
基础题目。等价类具有特殊性，可以得到结论，不需要真正计算循环节数。
进阶
POJ2154 Color
循环同构，直接结论。显然答案为 \(\frac 1n\sum_{i=1}^n n^{(i,n)}\)，然而 \(n\) 很大，需要优化。我们单独考察指数部分。令 \(j=(i,n)\)，有：
\[ \begin {aligned} \frac 1n\sum_{i=1}^n n^{(i,n)} &=\frac 1n\sum_{i=1}^n \sum_{j|(i,n)} n^j \text {且}[(i/j,n/j)==1] \\ &=\frac 1n\sum_{j|n} \sum_{i=1}^{n/j} n^j \text {且}[(i/j,n/j)==1] \\ &=\frac 1n\sum_{j|n} \phi (n/j)*n^j \\ \end {aligned} \]
需要质数表、快速幂和单欧拉函数值计算，但时间复杂度远远到不了 \(\mathrm{O}(n)\)。然而我们最后要除以 \(n\)，模数不保证质数，也不一定有逆元。我们发现答案的每一项都存在 \(n\) 的非 \(0\) 次幂，因此我们在快速幂的时候就可以少乘一个 \(n\)。
HNOI2008 洗牌
保证任意几种洗牌法可以用其中的一种代替，且都能回到原状态保证了置换群的封闭性，可以用 Burnside 引理。不使用 Polya 定理是因为有颜色数量的限制，不能直接使用。
我们发现一个循环要不变就只能染同一种颜色，因此求出一种置换的循环后，我们相当于求对这些循环染 \(3\) 种颜色使得总数满足数量限制的方案数。这是一个背包问题，可以动态规划解决。
POJ2888 Magic Bracelet
类似 POJ2154 Color，但是这次有颜色限制，然而我们发现颜色数量很少。
考虑一个置换 \(g\_i\)，它有 \((n,i)\) 个循环长度为 \(\frac{n}{(n,i)}\) 的循环，并且这些循环在任意长度为 \((n,i)\) 的序列中刚好各有一个循环元素，整个序列为这段序列重复 \(\frac{n}{(n,i)}\) 次构成（画图），因此我们可以认为这段序列首尾相接的满足方案数是等价的。把珠子看成点，能连接的两个珠子之间连边，则满足的方案相当于从点 \(u\) 经过 \((n,i)\) 个点再回到 \(u\) 的方案数。令邻接矩阵为 \(a\)，则方案数为 \((a^{(n,i)})_{u,u}\)（邻接矩阵的性质）。
同样利用欧拉函数加速计算，本题解决。
高级
Sgu282 Isomorphism/SHOI2006 有色图
是道好题。
题目很明显是 Polya 定理计数，不过我们计数的对象不是点而是边，这就不容易计算循环节了。不过我们发现对于完全图，一个边由唯一确定的两个点确定，因此点的一种置换唯一对应边的一种置换，即置换数 \(|G|=n!\)。对于一个边，它的置换是由两个点的置换决定，边循环是点循环上一圈长度任意的连续的边集（想象一个点循环上有一条边连接了任意两个点，则一次点置换之后，边会顺着置换方向移动 \(1\) 格，而此处在置换前的边，在置换后又对应了下一个间隔为 \(1\) 的边，直到最终回到初始边）。因此我们希望通过考虑点的置换间接得到边的置换节，从而得到 Polya 定理中的指数。
不难发现一个边的两个点有两种情况：在点循环中，在点循环间。我们先确定这么一个结论：边循环节 \(=\) 点循环中的边循环节 \(+\) 点循环间的边循环节。分类讨论：
在点循环中。则按照刚刚我们的脑补，一个边循环由转了一圈循环长度为 \(len\) 的点循环的边集构成，因此边循环长度为 \(len\)。然而我们发现 \(len\) 为偶数的情况时长度不一定都是 \(len\)，比如边的长度刚好为 \(\frac{len}2\) 时，转 \(\frac{len}2\) 次就结束了（画图验证）。显然奇数情况不会出现长度为 \(\frac{len}2\) 的边。我们再分奇偶讨论：
\(len\) 为奇数。则在点循环中只有 \(\frac{len*(len-1)}2\) 条边，每个边循环长度都为 \(len\)，因此循环节数为 \(\frac{len-1}2=\lfloor \frac{len}2 \rfloor\)。
\(len\) 为偶数。则恰好只有一个循环长度为 \(\frac{len}2\)，因此我们从 \(\frac{len*(len-1)}2\) 条边中去除多余的 \(\frac{len}2\) 条边，再给循环节数单独加上 \(1\)。循环节数为 \(\frac{len}2\)。
合并结果为 \(\frac{len}2\)。
在点循环间。则对于一条边，相当于在两个点循环 \(len_i\) 与 \(len_j\) 中连边，每次轮换就前进 \(1\) 格。不难看出这样的循环长度为 \([len_i,len_j]\)，且所有的循环不相交。因此循环节为 \(\frac{len_i*len_j}{[len_i,len_j]} = (len_i,len_j)\)。
综上，我们得到了对于给定的一种点循环长度方案计算边循环节长度的算法，且满足 \(\sum{len_i}=n\)。这个就是整数划分方案，对于 \(n\leq 53\) 来说数量远少于 \(n!\)，可以 DFS 枚举。令 \(cnt_i\) 为划分中 \(i\) 出现的次数，\(len_i\) 为划分的一个方案集，则满足这种划分的排列数为 \(\frac{n!}{\prod(cnt_i!)\prod{len_i}}\)，简单证明：
考虑划分方案。假设一种划分方案已经被我们钦定排成一排，对于每种全排列我们都顺序按划分方案划分，不难看出这种划分方案在考虑划分间及其内部的顺序时是不重复也不遗漏的，这样的方案数为 \(n!\)。
不考虑划分集内部元素。我们认为集合大小相同的两个集合是等价的，因此总数为可重集的全排列，要除以 \(\prod(cnt_i!)\)。
考虑划分集内元素。由于划分集内是一个循环，因此我们认为循环同构是等价的。而对于不产生循环同构的含有 \(len\) 个元素的序列，我们每对一个排列进行循环同构就能增加 \(len-1\) 个新排列（注意所有产生的序列和原序列都不相同，否则原序列存在循环同构），因此每一个划分集要除以 \(len\)，总数要除以 \(\prod{len_i}\)。
综上，满足一种划分条件且划分集内部不存在循环同构的全排列数为 \(\frac{n!}{\prod(cnt_i!)\prod{len_i}}\)。
于是我们就很完美地解决了这个问题。
总结
置换群通常解决一类置换问题，Burnside 引理和 Polya 定理通常解决一类等价类计数问题。等价类计数的重点在于寻找不变点总数，通常存在高效的方法。有时需要动态规划和数论知识甚至矩阵快速幂解决。
Burnside 引理：求解每个置换下本质不同的方案数即在该置换下保持不变的方案数；Polya 定理：计算每个置换下循环节个数。
染色计数中，若存在对染色的限制（数量、间隔）则不能直接应用 Polya 定理。Polya 定理的本质是对置换的每个循环染同一种颜色。
无论用 Burnside 引理还是 Polya 定理，都需要除以置换总数。若存在与总数不互质的模数，需要考虑边做就边除以总数。