# 群的定义
## 群
若集合 $G$ 和其上的运算 $*$ 满足一下四个条件，则称二元组 $(G,*)$ 构成**群**。
1. **封闭性**：$\forall f,g\in G,f*g\in G$。
2. **结合律**：$\forall f,g,h\in G,(f*g)*h=f*(g*h)$。
3. **单位元**存在性：$\exist e\in G$，使得 $\forall g\in G,e*g=g*e=g$。
4. **逆元**存在性：$\forall f\in G,\exist g\in G$，使得 $f*g=g*f=e$。称 $g$ 为 $f$ 的逆元，记作 $f^{-1}$。
特别地，若群 $G$ 满足交换律，称 $G$ 是一个交换群或阿贝尔（Abel）群。
## 阶
群 $G$ 的元素个数称为 $G$ 的**阶**，记为 $|G|$。若 $G$ 有无穷多个元素，称 $G$ 为**无限群**，若 $G$ 的元素个数有限，称 $G$ 为**有限群**。
## 子群
设 $(G,*)$ 是群，若 $G$ 的子集 $H$ 对于**同一种运算** $*$ 也构成群，则称 $(H,*)$ 是 $(G,*)$ 的子群，记作 $H\leq G$。
## 陪集
对于群 $(G,*)$ 和它的一个子群 $H\leq G$，对于一个元素 $g\in G$，记**集合** $gH=\{g*h|h\in H\}$ 为 $H$ 在 $G$ 中导出的一个左陪集，同理可以给出右陪集的定义。
很明显，陪集的大小等于 $|H|$。
注意，**陪集不一定是子群**。
# Lagrange 定理
## 定理 1（陪集的性质）
对于子群 $H\leq G$，它导出的任意两个陪集，要么完全相同，要么交集为空。
**证明**（以两个元素都导出左陪集为例）：
若 $g_1,g_2\in G,g_1\neq g_2$ 所导出的陪集有交，那么必然存在 $h_1,h_2\in H,h_1\neq h_2$，满足 $g_1*h_1=g_2*h_2$。
同时右乘一个 $h_1^{-1}$ 得 $g_1=g_2*h_2*h_1^{-1}$，又因为 $h_1^{-1}\in H$，所以 $h_2*h_1^{-1}\in H$，即 $\exist t\in H$，满足 $g_1=g_2*t$。
因此，对于 $g_1H$ 中的任意元素 $g_1*h,h\in H$，都可以表示成 $g_2*t*h$，而 $t*h\in H$，所以 $g_1*h\in g_2H$。
如上就证明了 $g_1H\subseteq g_2H$，同理可以证明 $g_2H\subseteq g_1H$，因此 $g_1H=g_2H$，定理得证。
## 定理 2（Lagrange 定理）
对于有限群 $G$ 及其子群 $H\leq G$，有 $|G|=|H|[G:H]$。
其中，$[G:H]$ 表示 $H$ 能够导出的陪集的种类数。
## 定理 3（子群的性质）
由 Lagrange 定理可以得到一个推论。
对于有限群 $G$ 及其子群 $H\leq G$，有 $|H|$ 整除 $|G|$。
# 染色的定义
## 染色
有一个由编号 $1$ 到 $n$ 构成的集合，它上面的染色 $c$ 定义为给集合中的每一个元素分配一种颜色的分配方案，其中第 $i$ 个元素的颜色为 $c[i]$。
## 广义的染色
对于群 $G$（无须是置换群）和一个全集 $\mathcal{C}$，对于 $G$ 中的任意一个元素 $g$ 和 $\mathcal{C}$ 中的任意一个元素 $c$，定义运算 $\cdot$ 满足 $g\cdot c\in\mathcal{C}$，且满足如下两个性质：
1. $e\cdot c=c$。
2. $(f*g)\cdot c=f\cdot(g\cdot c)$。
则称 $\mathcal{C}$ 为广义染色集合，$\mathcal{C}$ 中的元素 $c$ 是广义染色。
## 置换对染色的作用
对于置换 $f\in S_n$ 的染色 $c\in \mathcal{C}$，定义置换 $f$ 作用于 $c$ 的结果为 $f\cdot c$，满足 $(f\cdot c)[i]=c[f^{-1}(i)]$（相当于是沿着 $f(i)$ 这条边走了一步）。
不难发现，它满足下面两个性质：
1. $e\cdot c=c$。
2. $(f*g)\cdot c=f\cdot(g\cdot c)$。
也就是说，它符合广义染色的定义。
# 轨道——稳定子群定理
## 轨道
对于一个群 $G$ 和一个染色 $c$，定义 $c$ 在 $G$ 中的**轨道**为：
$$
G\cdot c=\{g\cdot c|g\in G\}
$$
对于一个染色集合 $X\subseteq\mathcal{C}$，定义 $G\cdot X=\{g\cdot c|g\in G,c\in X\}$，若 $G\cdot X=X$，则称 $X$ 在 $G$ 下**固定**。
## 稳定子群
对于一个群 $G$ 和一个染色 $c$，群中满足 $g\cdot c=c$ 的 $g$ 构成一个**群**，称之为染色 $c$ 的**稳定子群**，记作 $G_c$。
**证明**为什么是一个子群：
考虑反证法。
设使得 $g\cdot c=c$ 的 $g$ 构成集合 $H$。
如果不是一个子群，那么必然存在 $p,q\in H$，使得 $p*q\notin H$。
因为 $p\cdot c=c,q\cdot c=c$，所以 $p\cdot (q\cdot c)=c=(p*q)\cdot c$，$p*q\in H$，与之前的假设矛盾。
因此，$H$ 一定是 $G$ 的子群。
## 轨道——稳定子群定理
对于群 $G$ 和染色 $c$，有 $|G\cdot c|\cdot|G_c|=|G|$。
**证明**：
任取 $g\in G$，对于左陪集 $gG_c$ 中的元素 $g*h,h\in G_c$，它作用于染色 $c$ 的结果为 $(g*h)\cdot c=g\cdot(h\cdot c)=g\cdot c$。
也就是说，对于 $G_c$ 的每种不同的左陪集 $H$，$H$ 内部的元素作用于 $c$ 的结果相同。
另一方面，对于两个不同的左陪集 $g_1G_c,g_2G_c$，它们中的元素作用于 $c$ 不能产生相同的结果。
否则，$g_1\cdot c=g_2\cdot c$，有 $(g_1^{-1}*g_2)\cdot c=c$，那么 $g_1^{-1}*g_2\in G_c$，于是 $g_2\in g_1G_c$，矛盾。
因此，对于每种不同的陪集，对 $c$ 作用的结果不同，陪集内部的元素作用的结果有分别相同。
由 Lagrange 定理，$|G\cdot c|\cdot|G_c|=|G|$ 得证。
# Burnside 引理
对于一个群中元素 $g$ 和一个染色集合 $X\subseteq \mathcal{C}$，$X$ 中满足 $g\cdot c=c$ 的染色 $c$ 的集合记作 $X^g$。
记 $c_1\thicksim c_2$ 表示染色 $c_1$ 和染色 $c_2$ 本质相同。
$c_1\thicksim c_2$ 当且仅当满足下列条件之一：
1. $c_2\thicksim c_1$。
2. $\exist g\in G$，使得 $g\cdot c_1=c_2$。
3. $c_2\in G\cdot c_1$。
4. $G\cdot c_1=G\cdot c_2$。
对于染色集合 $X\subseteq \mathcal{C}$，在群 $G$ 的作用下 $X$ 中本质不同的染色数等于 $X$ 中所有元素在 $G$ 中形成的不同轨道的数目，记作 $|X/G|$。
于是可以得到 Burnside 引理：
$$
|X/G||G|=\sum_{g\in G}|X^g|
$$
**证明**：
考虑计算 $g\cdot c=c,g\in G,c\in\mathcal{C}$ 的数量。
可以枚举群中元素
$$
\sum_{g\in G}|X^g|
$$
也可以枚举染色
$$
\sum_{c\in X}|G_c|=\sum_{c\in X}\frac{|G|}{G\cdot c}=|G|\sum_{c\in X}\frac{1}{|G\cdot c|}
$$
每种轨道 $G\cdot c$ 中的每种染色都会在轨道中贡献一次，因此
$$
\sum_{c\in X}\frac{1}{|G\cdot c|}=|X/G|
$$
因此
$$
|X/G||G|=\sum_{g\in G}|X^g|
$$