从群论经Burnside到Polya
引入：计数 $m$ 染色的环。
群
集合 $G$ 上的二元运算 $+$（这里只用来代替一个操作）：
$\forall f, g \in G, f + g \in G$。
$\forall f, g, h \in G, (f + g) + h = f + (g + h)$，相对于交换律，是更为本质的存在。
- 也有不满足的群
单位元：$\exists e \in G, \forall x \in G, e + g = g + e = g$
直积/直和：
$$G_1, G_2 \to G = G_1 \times G_2 = \{(a, b) | a \in G_1, b \in G_2 \} $$
置换群：
对于有限集 $X$，不失一般性，我们取 $X$ 为前 $n$ 个正整数的集合 $\{1, 2, \cdots , n\}$。
置换可以看作一个函数：$f : X \to X$。为了直观可视，认为可以看作一个 $2 \times n$ 的矩阵：
$$\begin{pmatrix} $$
1 & 2 & \cdots & n \
f_1 & f_2 & \cdots & f_n
\end{pmatrix}
$$ 于是对于两个置换 $(f \circ g)(x) = f(g(x)) = f_{g_x}$。 由此，可知置换操作满足**结合律**，**不满足交换律**。 定义所有 $n$ 的置换构成的集合为 $S_n$。 对于 $S_n$ 的非空子集 $G$ 满足一下三个性质，则称 $G$ 为 $X$ 的置换群。 - 对于 $f, g \in G$，有 $f \circ g \in G$。 - $S_n$ 中的恒等变换 $\iota \in G$。 - 对于 $f \in G$，有 $f^{-1} \in G$。 有一类特殊的置换，$\rho_n$ 表示如下定义的置换： $$
\begin{pmatrix}
1 & 2 & \cdots & n-1 & n \
2 & 3 & \cdots & n & 1
\end{pmatrix}
$$ 我们可以认为 $\rho_n$ 表示将序列均匀放在一个圆上，然后旋转 $\frac {2\pi}n$。 特别的，当 $s \equiv t \pmod n$ 时，有 $\rho_n^s = \rho_n^t$。并且有恒等置换 $\rho_n^0 = \iota$。 因此，对于 $n$，只有 $n$ 个本质不同的置换：$\rho_n^0, \rho_n^1, \cdots \rho_n^{n - 1}$。 于是我们有：$C_n = \{\rho_n^0, \rho_n^1, \cdots \rho_n^{n - 1}\}$。 可知 $C_n$ 是一个置换群，隐含了圆周上的转换。 **阿贝尔群**： - 满足交换律的群。 - 可以表示为多个循环群的直积。 ## 着色 对于有限集合 $X$，其一种*着色*指给 $X$ 的每一个元素指定一种颜色的分配方案。 设 $\mathcal C$ 是 $X$ 的一个着色集合，其中包含了 $X$ 的任意着色。 设 $c$ 是 $X$ 的一种着色，$1, 2, \cdots, n$ 的颜色分别记为 $c_1, c_2, \cdots, c_n$。 此时，有一个置换 $f \in G$，那么定义 $f * c$ 为使得 $f_k$ 具有颜色 $c_k$。 而着色集 $\mathcal C$ 需要满足一下条件： - 对于 $f \in G$，$c \in \mathcal C$，$f * c \in \mathcal C$ 现在我们考虑**等价着色**。 设 $c_1, c_2$ 是 $\mathcal C$ 中的两种着色，等价关系记为 $\sim$。 如果存在置换 $f \in G$ 使得 $f * c_1 = c_2$，那么称 $c_1$（在 $G$ 的作用下）等价于 $c_2$。 ## Burnside 定理 我们考虑置换于着色之间的关系。定义 $$
G(c) = {f : f \in G, f * c = c}
$$ 表示使得着色 $c$ 不变的置换，以及 $$
\mathcal C (f) = {c : c \in \mathcal C, f * c = c}
$$ 表示在置换的作用下不变的着色。 其中 $G(c)$ 称为 $c$ 的稳定核，并且形成一个置换群。 --------------- **定理 1**：对于着色 $c$ 以及稳定核 $G(c)$，$g, f \in G(c), g * c = f * c$ 当且仅当 $f^{-1} \circ g \in G(c)$。 **证明**：由于 $f \in G(c)$ 那么根据群的性质，必定有 $f^{-1} \in G(c)$。于是可以有： $$
f^{-1} \circ (g * c) = f^{-1} \circ (f * c)
$$ 根据结合律，可以有： $$
(f^{-1} \circ g) * c = (f^{-1} \circ f) * c = c
$$ 所以可知 $f^{-1} \circ g$ 不会使得 $c$ 改变，所以根据定义 $f^{-1} \circ g \in G(c)$。 ------------------- **推论 1**：对于着色 $c$，与 $c$ 等价的着色数有等式： $$
|{ f * c : f \in G }| = \cfrac {|G|}{|G(c)|}
$$ 也就是等于总的置换个数除以稳定核中的置换个数。 **证明**： 根据**定理 1**，满足 $g * c = f * c$ 的那些置换 $g$ 应当 $\in G(c)' = \{f \circ h:h \in G(c)\}$。 由消去律，从 $f \circ h = f \circ h'$ 可以推导出 $h = h'$。于是，集合 $|G(c)'| = |G(c)|$。 从而对于置换 $f$，恰好存在 $|G(c)|$ 个置换，作用在 $c$ 上与 $f$ 有同样的效果。 因而于 $c$ 等价的着色数应当为 $\frac {|G|}{|G(c)|}$。 -------------- **定理 2**：对于 $\mathcal C$ 中的**非等价**着色数 $N(G, \mathcal C)$ 由下式给出： $$
N(G, \mathcal C) = \cfrac 1 {|G|} \sum_{f \in G} |\mathcal C(f)|
$$ 也就是说等于在 $G$ 中的置换作用 -------------- ### 轨道 - 稳定子群定理 $c$ 表示一种染色（操作），$G_c$ 是染色 $c$ 的稳定子群，即轨道的个数： $$
|G_c| \cdot | G \cdot c | = | G |
$$ $$
G_c = {g | g \in G, g + c = g}
$$ **限制**：封闭。 ## Burnside 将无标号转化为有标号然后计数。 不动点：一种染色方案，放在旋转 $r$ 操作下，合法（不变）。 答案：不动点个数 $|G_c|$ 的平均值 $$
\cfrac 1 {|G|} \sum_{c} |G_c|
$$$$