置换群
置换：置换是一个集合映至自身的双射。$(a_1,a_2,\cdots,a_n)$ 表示将原数列的第 $a_i$ 个数在此置换作用下变到第 $i$ 个位置。
对于状态 $s$ 和置换 $f$，记 $f*s$ 为将 $f$ 作用于 $s$ 所得到的状态。
定义置换的乘法：$f\cdot g$ 表示显作用 $g$ 再作用 $f$。
置换群：有限集合上的一些置换组成的集合在置换的乘法下组成的群。
等价类：若状态组成的集合 $X$ 中的元素经过置换群 $G$ 中的置换作用后可以变成相同的状态，则这些状态属于一个等价类。等价类组成的集合记为 $X/G$。
循环：如果一个置换 $f=(a_1,a_2,\cdots,a_n)$，存在 $k$ 个元素使得 $a_{x_1}=x_2,a_{x_2}=x_3,\cdots,a_{x_k}=x_1$，则称 $x_1,x_2,\cdots,x_k$ 为一个长度为 $k$ 的循环。一个置换可以被拆分为一些不相交的循环，如：
$$
(6,5,7,4,1,2,3)=(1,6,2,5)\circ(3,7)\circ(4)
$$轨道与稳定子：
$$
X^{\tau}={s|s\in X,\tau*s=s}
$$$$
G(s)={\tau*s|\tau\in G}
$$$G(s)$ 称为 $s$ 的轨道。
$$
G^s={\tau|\tau*s=s}
$$
$G^s$ 称为 $s$ 的稳定子。
Burnside 引理
$$
\left|X/G\right|=\frac{\sum_{\tau\in G}\left|X^\tau\right|}{\left|G\right|}
$$
证明：
$$
\sum_{\tau\in G}\left|X^\tau\right|=\sum_{\tau\in G}\sum_{s\in X}[\tau*s=s]
$$
$$
=\sum_{s\in X}\sum_{\tau\in G}[\tau*s=s]=\sum_{s\in X}\left|G^s\right|
$$
注意到，$s$ 所在的等价类的大小（记为 $|L_s|$）为 $\tau*s$ 的所有可能结果数。
联想拉格朗日定理，可以猜想：$\left|G^s\right|=\frac{|G|}{|L_s|}$。
首先易证，$G^{s}$ 是 $G$ 的子群。
若 $\alpha,\beta\in G$，$\alpha*s=\beta*s$，
$$
\beta^{-1}*(\alpha*s)=\beta^{-1}*(\beta*s)
$$
$$
(\beta^{-1}\cdot\alpha)*s=s
$$
$$
\alpha\in aG^s,x,y\in G^s,\alpha=a\cdot x
$$
$$
\beta^{-1}\cdot\alpha=y,\beta^{-1}\cdot a\cdot x=y,\beta^{-1}\cdot a=y\cdot x^{-1}\in G^s
$$
$$
\beta\in aG^s
$$
则 $\alpha,\beta$ 在同一个 $G^s$ 的左陪集中。
$$
\alpha,\beta\in aG^s
$$
$$
x,y\in G^s,\alpha=a\cdot x,\beta=a\cdot y
$$
$$
\beta^{-1}\cdot\alpha=y^{-1}\cdot a^{-1}\cdot a\cdot x=y^{-1}\cdot x\in G^s
$$
$$
\alpha*s=\beta*s
$$
易得：$\left|G^s\right|=\frac{|G|}{L_s}$
$$
\sum_{\tau\in G}\left|X^\tau\right|=\sum_{s\in X}\left|G^s\right|=\sum_{s\in X}\frac{|G|}{|L_s|}
$$
$$
=\sum_{L}\sum_{s\in L}\frac{|G|}{|L|}=|G||X/G|
$$
证毕。
Polya 定理
在染色问题中，如果一个位置可以有 $m$ 种颜色，则记 $c(\tau)$ 为 $\tau$ 中的循环数，则
$$
\left|X^\tau\right|=m^{c(\tau)}
$$
例
Code
1 |
|