群的概念及基本性质

由集合 $G\neq \emptyset$ 和 $G$ 上的二元运算 $*$ 组成。
满足以下性质：
- 封闭性：$\forall a,b\in G,$ 均有 $(a*b)\in G$。
- 结合律：$(a*b)*c=a*(b*c)$ 。
- 存在单位元：存在 $\epsilon\in G$ 使得 $\forall a\in G$，均有 $a*\epsilon=\epsilon *a=a$ 。
- 存在逆元：$\forall a \in G,$ 均存在 $b\in G$ 使得 $a*b=\epsilon$。
定理：单位元唯一。证明略去。
定理：每个元素的逆元唯一。证明略去。
定理：对于任意的有限群 $G={\epsilon,a_1,…,a_n}$，$\forall a\in G$，均存在一个常数 $b$ 使得 $a^b=\epsilon$，且有 $a^{-1}=a^{b-1}$ ，称 $b$ 为 $a$ 的阶。证明略去。

置换与置换群

置换的定义：有限集合到自身的双射称作置换。

可以写作

$$\large\begin{pmatrix}1&2&3&…&n\\p_1&p_2&p_3&…&p_n\end{pmatrix}$$
置换的乘法：相当于将映射叠加。

性质：
- 置换的乘积还是置换。
- 满足交换律。
- 单位元为 $\large\begin{pmatrix}1&2&3&…&n\\1&2&3&…&n\end{pmatrix}$
- $\begin{pmatrix}1&2&3&…&n\\p_1&p_2&p_3&…&p_n\end{pmatrix}$ 的逆元为 $\begin{pmatrix}p_1&p_2&p_3&…&p_n\\1&2&3&…&n\end{pmatrix}$
一般不满足交换律。
置换群：由上面的性质可知对 $1..n$ 作用的所有置换形成一个群。一般只研究一个子群。
置换的循环：把置换看作有向图，连边 $(i,p_i)$，会形成若干个环。

置换可以用这些环来表示，并且是唯一的。

设 $G$ 为 $1..n$ 的一个置换群。

不动点：对于 $p\in G$ ，若 $p_k = k$ 则称 $k$ 是 $p$ 下的不动点。

$p$ 下的不动点个数记作 $c(p)$。
$\text{k}$ 不动置换类

对于 $p\in G$，若 $k$ 是 $p$ 下的不动点，则称 $p$ 属于 $\text{k}$ 不动置换类，记作 $p\in Z_k$。$Z_k$ 为 $G$ 的一个子群。
等价类：等价类 $E_k$ 为对元素 $k$ 任意施加 $G$ 中的置换所能到达的元素集合。
- 定理：当 $x,y$ 同属一个等价类时，有 $|Z_x| = |Z_y|$。证明略去。
轨道-稳定子定理：

$$|Z_k|\times|E_k|=G$$

证明略去。
$\text{Burnside 引理}$ ：

记 $l$ 为 $E_{1..n}$ 中本质不同的等价类个数，则有：

$$l = \large\dfrac 1 {|G|}\sum\limits_{p\in G}c(p)$$

即等价类个数 $=$ 所有置换下的不动点总数的平均数。
$\text{Polya 定理}$:

设有 $n$ 个元素，每个元素有 $m$ 种染色方案。

设 $G$ 是 $n$ 个元素的置换群，则染色总方案数为：

$$\large\dfrac 1 {|G|}\sum\limits_{p\in G}T(p)$$

其中 $T(p)$ 表示在置换 $p$ 下不动的染色方案数。