# Burnside 引理与 Pólya 计数定理

# 基本概念

假设 $c$ 是集合 $X$ 上的一种着色. 如果对 $X$ 中的元素按正整数编号， 则可以用 $c(1), c(2), \cdots, c(n)$ 来表示对应元素的着色.

设 $f$ 是 $X$ 上的一个置换：

$f = \begin{pmatrix} 1 & 2 & \cdots & n-1 & n \\ i_1 & i_2 & \cdots & i_{n-1} & i_n \end{pmatrix}$

定义置换对着色的作用 $\circ$ 为将着色按置换变换， 即 $(f \circ c)(i_k) = c(k)$， 也就是把对 $k$ 的着色按置换转移到 $i_k$ 去， 最后 $i_k$ 的颜色就是原来 $k$ 的颜色 $c(k)$.

一般的，对于置换群 $G$ 和着色集合 $C$ 来说， 按照以上方式定义群作用 $\circ$， 只要群中的置换对着色集合 $C$ 作用满足封闭性， 即对于任意 $g \in G, c \in C$ 满足 $g\circ{c} \in C$， 则显然有 $1_G \circ c = c$ 和 $(gh) \circ c = g \circ (h \circ c)$， 其中 $g$ 和 $h$ 为置换群 $G$ 中的任意两个置换， $c$ 为 $C$ 中的一个着色.

可以从群作用中诱导出一个着色的等价关系 $\sim$. 着色集合 $C$ 中的两个着色 $c_1$ 和 $c_2$ 等价，即 $c_1 \sim c_2$， 当且仅当置换群 $G$ 中存在置换 $g$，满足 $g \circ c_1 = c_2$.

# Burnside 引理

设 $G$ 是集合 $X$ 上的一个置换群，$C$ 为 $X$ 上的一个着色集合， $G$ 对 $C$ 的作用满足封闭性. 则 $C$ 中不等价的着色数为：

$B = \frac{1}{|G|}\sum_{g \in G}{|S(g)|}$

其中 $S(g)$ 为 $C$ 中对置换 $g$ 保持不变的着色集合.

# Pólya 计数定理

设 $G$ 是集合 $X$ 上的一个置换群， $X$ 中的每个元素可以被染成 $k$ 种颜色， 则不等价的着色数为：

$P = \frac{1}{|G|}\sum_{g \in G}{k^{nc(g)}}$

其中 $nc(g)$ 为置换 $g$ 种循环节的个数.