群论,置换和Burnside引理笔记

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

Burnside引理

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

其中

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

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

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

图的同构

式子:

X/G=b2k(bi)(ci!)k=i=1Kbi2+i=1Kj=1i1gcd(bi,bj)\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}

其中bb是从小到大划分nncc每个划分的每种划分大小有多少个。