Burnside

只是一些定义，具体例子去看组合数学。

置换

对于排列 $X$，将函数 $f:X \to X$ 称为置换。也可以记作

$$\begin{pmatrix} 1 & 2 & ... & n \\ i_1 & i_2 & ... & i_n \end{pmatrix}$$

定义置换的合成 $f \circ g$，有 $(f \circ g)(k) = f(g(k))$。

定义置换群 $G$ 满足

• $\forall f,g \in G, f \circ g \in G$。

• 存在单位元。

• $\forall f \in G, f^{-1} \in G$。

着色

记 $C$ 为颜色集合，将函数 $c:X \to C$ 称为着色。

定义颜色的置换 $f*c$ ，有 $(f*c)(i_k)=c(k)$。

$c_1$ 与 $c_2$ 等价当且仅当 $\exists f \in G, f*c = c$，记作 $c_1 \sim c_2$。

定义着色集 $\mathcal{C}$ 满足

• $\forall f \in G,c \in \mathcal{C}, f*c \in \mathcal{C}$。

Burnside 定理

定义 $G(c) = \{f|f \in G,f*c=c\},\mathcal{C}(f) = \{c|c \in \mathcal{C},f*c=c\}$ 也称为不动点。

与 $c$ 等价的着色个数 = $\frac{|G|}{|G(c)|}$。

证明

$\forall f \in G,g \in G(c)$ 有 $(f \circ g)*c = f*(g*c) = f*c$。

而每个 $f \circ g$ 是不同的，因此对 $c$ 作用与 $f$ 相同的置换个数为 $|G(c)|$，总置换个数为 $|G|$，所以与 $c$ 等价的不同的着色有 $\frac{|G|}{|G(c)|}$ 种。

Burnside 定理：$非等价着色数 = \frac{1}{|G|} \sum_{f \in G} |\mathcal{f}|$

用人话将就是，本质不同的着色个数为所有置换不动点个数的平均值。

证明

$$\begin{align} \sum_{f \in G} |\mathcal{C}(f)| &= \sum_{c \in \mathcal{c}} |G(c)| \\ \sum_{f \in G} |\mathcal{C}(f)| &= \sum_{c \in \mathcal{c}} \frac{|G|}{与 c 等价的着色的个数} \\ \sum_{f \in G} |\mathcal{C}(f)| &= |G|(非等价着色数) \\ (非等价着色数) &= \frac{1}{|G|} \sum_{f \in G} |\mathcal{C}(f)| \end{align}$$

Polya 定理

浅浅写一下。

置换可以被几个循环的合并代替。例

$$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 4 & 9 & 1 & 7 & 6 & 5 & 3 & 8 & 2 \end{pmatrix} = [1 \ 4 \ 7 \ 3] \circ [2 \ 9] \circ [5 \ 6] \circ [8]$$

计算着色方案数时，我们只关心大小一定的循环有多少个，因此一个置换群可以被一个生成函数代替。

该方法的优势在于可以限定颜色的个数。

习题

1.【模板】Polya 定理

有 $n$ 种置换，即旋转 $[1,n]$ 次（这里将 $0$ 归为 $n$ 方便计算）。

对于旋转 $k$ 次的，其不动点个数为 $n^{\gcd(n,k)}$。所以答案为

$$\begin{align} \frac{1}{n} \sum_{k=1}^{n} n^{\gcd(n,k)} &= \frac{1}{n} \sum_{d|n} n^d \sum_{k=1}^{n} [\gcd(n,k)=d] \\ &= \sum_{d|n} n^d \varphi(\frac{n}{d}) \end{align}$$

单点求 $\varphi$，时间复杂度 $O(n\sqrt{n}\log n)$（可以通过预处理将 $\log n$ 去掉）。

2.[JSOI2012] 爱之项链

搬题人的 id 提示了此题的做法。

求一个戒指的方案数同上，记方案数为 $k$。考虑容斥，答案为

$$\begin{align} \sum_{i=0}^{n-2} (-1)^{i} k(k-1)^{n-1-i} &= (-1)^{n-1} k \sum_{i=1}^{n-1} (1-k)^{i} \\ &= (-1)^{n-1} k \frac{(1-k)^{n}-(1-k)}{-k} \\ &= (k-1)^{n} + (-1)^{n} (k-1) \end{align}$$

$n=1$ 要特判？

参考

组合数学（第五版）