Burnside引理一般求解步骤

1. 列出所有的可能的状态。
2. 把所有的操作用置换的形式写出来。
3. 数出每种置换不动点的数目。
4. 利用Burnside引理求解：\(L = \dfrac{1}{|G|}\sum_{\tau \in G}c_1(\tau)\)。可以简记为每个置换不动点个数的平均值就是方案数。

利用Polya定理对Burnside引理进行优化

条件：

对于任意一个置换\(\tau\)，将其拆分成若干个循环。每个循环彼此之间相互独立。

做法：

试想，如果一种状态是\(\tau\)的不动点，那么任意一个循环中的点的“颜色”必须是相同的。设一共有\(m\)中颜色。那每个循环就会有\(m\)种方案。设\(c(\tau)\)为\(\tau\)置换包含的循环个数。那么\(\tau\)置换不动点的个数\(c_1(\tau)=m^{c(\tau)}\)。

所以\(L=\dfrac{1}{|G|}\sum_{\tau\in{G}}m^{c(\tau)}\)。

Burnside引理和Polya定理相关总结

原文：https://www.cnblogs.com/little-aztl/p/14399423.html