群论，置换和Burnside引理笔记

参考/来源：
图的同构
置换群
群

Burnside引理

$|X / G|=\frac{1}{|G|} \sum_{g \in G}\left|X^{g}\right|$

其中

$X^{g}=\{x \mid x \in X, g(x)=x\}$

$X$为映射（所有染色方案），$X/G$为置换群$G$作用在$X$上产生的等价类，$X^g$代表$X$中运用置换$g$仍然不变的元素（通俗的讲就是给正方体染色，所有染色方案中执行这个置换后正方体完全相同的染色方案）。考虑下$X^g$如何求，其实把$g$划分成多个等价类使得等价类个数最少，且对于$X$中所有元素执行置换$g$，不会存在一个元素出现“跨等价类置换”的情况。
（图的情况中）换句话说，对于置换$g$如果存在$k$个边的等价类，那么$X$中就有$2^k$个不动点。即：

$\left|X^{g}\right|=2^{k}$

图的同构

式子：

$\begin{array}{l} |X / G|=\sum_{b} \frac{2^{k}}{\prod\left(b_{i}\right) \prod\left(c_{i} !\right)} \\ k=\sum_{i=1}^{K}\left\lfloor\frac{b_{i}}{2}\right\rfloor+\sum_{i=1}^{K} \sum_{j=1}^{i-1} \operatorname{gcd}\left(b_{i}, b_{j}\right) \end{array}$

其中$b$是从小到大划分$n$，$c$每个划分的每种划分大小有多少个。