Burnside's_Lemma
This is a fantastic lecture note about Burnside's Lemma and Ploya Theorem:
https://math.mit.edu/~apost/courses/18.204_2018/Jenny_Jin_paper.pdf
I would write down my learning notes for myself so it would be in Chinese.
1 背景¶
不管是算法题里还是生活中其实这是一个比较常见的问题：某某场景下本质不同的染色有多少种？ 既然强调了本质不同，就是说在一些变换下我们认为某两个染色方案是相同的。比如一个很自然的问题：我们想给一个正方体六个面染上红蓝绿三种颜色。如果我们认为正方体每个面都是相同的（比如骰子六个面就不同，因为它有标号），那么显然方案数并不是简单的 \(6^3\)，因为有很多情况之间是本质相同的，我们把正方体转一转它们就一样了。一通思考之后不难发现这并不是一个非常简单的问题。
除了这个之外还能想到很多类似的问题，它们可能有不同的变换方式，如果每次都要重新去想方法实在是太蠢了。我们希望能够抽象出一套东西来帮助我们解决这个问题。
2 基本定义¶
首先我们有两个集合，一个是我们的方案集合 \(X\)，它代表的是所有的染色方案（不考虑是否本质不同）；另一个是我们的操作集合 \(G\)，它代表的是所有可以施加的操作（具体来说可能是旋转、对称等）。操作天然就具有 复合 这个特性，也就是说我可以先进行 \(A\) 操作，然后再进行 \(B\) 操作。从我们朴素的情感出发，显然这个操作的 复合 运算应该是封闭的，也就是说先进行 \(A\) 操作再进行 \(B\) 操作，应该要等价与 \(G\) 中的某个元素才行。(后面换成英文标点看看效果)
我们很自然的认为这个操作集合 \(G\) 和操作的 复合 运算应该构成一个群. 当然并不是所有的操作集合都能构成群. 比如我们有一个碾碎操作, 但是没有复原操作, 那就不能构成群. 我们下面讨论的都是能够构成群的场景.