置换群
置换:置换是一个集合映至自身的双射。$(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$,