群论

# 置换

定义

有限集合到自身的双射（即一一对应）称为置换。集合 $S = \left\{a_1, a_2, \cdots ,a_n \right\}$ 的置换可以表示为：

$$f = \begin{pmatrix}a_1, a_2, \cdots , a_n\\ a_{p_1}, a_{p_2}, \cdots ,a_{p_n}\end{pmatrix}$$

$p_1, p_2, \cdots, p_n$ 为一个 $1 \sim n$ 的排列，显然置换个数为 $n!$。

置换的乘法

置换的乘法是置换的叠加，如对于置换 $f = \begin{pmatrix}a_1, a_2, \cdots , a_n\\ a_{p_1}, a_{p_2}, \cdots ,a_{p_n}\end{pmatrix}$ 和 $g = \begin{pmatrix}a_{p_1}, a_{p_2}, \cdots , a_{p_n}\\ a_{q_1}, a_{q_2}, \cdots ,a_{q_n}\end{pmatrix}$，置换的乘积 $f \circ g$ 为：

$$f \circ g = \begin{pmatrix}a_1, a_2, \cdots , a_n\\ a_{q_1}, a_{q_2}, \cdots ,a_{q_n}\end{pmatrix}$$

# 置换群

集合 $S$ 的所有置换构成一个群，这个群的任意子群称为置换群。

置换群中的元素是置换。

# 轨道 - 稳定化子定理

（这个定理是为了证明 $\text{Burnside's}$ 引理，所以不看也没关系 /kk）

设 $G$ 为置换群，$X$ 为一种操作所有方案的集合（看不懂的话下面有例子）。

对于 $\forall x \in X$，$G(x) = \left\{f(x) | f \in G \right\}$ 称为 $x$ 的轨道，$G_x = \left\{f|f(x) = x, f \in G\right\}$ 称为 $x$ 的稳定化子。

轨道 - 稳定化子定理： $|G(x)||G^x| = |G|$

（对于置换 $f$，满足 $f(x) = x$ 的元素称为该置换的不动点。）

# Burnside 引理

设 $G$ 是集合 $X$ 上的置换群，$c(f)$ 为置换 $f$ 的不动点个数，若 $G$ 把集合 $X$ 分为了 $L$ 个等价类，则有：

$$L = \frac 1{|G|}\sum_{f \in G}c(f)$$

证明:

若集合中一个元素 $x$ 的轨道大小为 $|G(x)|$，那么有 $|G(x)|$ 个元素的轨道都相同，每个元素的贡献为 $\frac 1{G(x)}$。

$$\begin{aligned} L =& \sum_{x \in X}\frac 1{|G(x)|} \\ =& \frac 1{|G|}\sum_{x \in X} |G_x| \\ =& \frac 1{|G|}\sum_{f \in G} c(f) \end{aligned}$$

例子：

一个 4 个点的环，染黑白两种颜色，循环同构，求本质不同方案数。

集合 $X$：不考虑重复的染色方案，共有 $2^{4}$ 种。

不动点：旋转之后四个点的颜色与旋转之前一样，这样的染色方案叫做不动点。

置换群：置换群大小为 4，有 $f_0, f_1, f_2, f_3$ 4 种置换，$f_i$ 表示旋转 $i$ 次。

$L$：即为本质不同染色方案数。

$$\begin{aligned} L =& \frac 1{|G|}\sum_{f \in G}c(f) \\ =& \frac 1{|G|}(c(f_0) + c(f_1) + c(f_2) + c(f_3)) \\ =& \frac 1{4}(16 + 2 + 4 + 2) \\ =& 6 \end{aligned}$$

# Pólya 定理

$\text{Pólya}$ 定理提供了在特殊情况下计算不动点个数的方法。

考虑一种置换会形成许多置换环。

设 $h(f)$ 为置换 $f$ 的置换环数量，若要用 $k$ 种颜色给集合 $X$ 染色，那么有 $c(f) = k^{h(f)}$。

证明：

因为要计算不动点个数，所以一个置换环上面的点颜色必须都一样，有 $k$ 种选择。又由于一共有 $h(f)$ 个置换环，所以方案数为 $k^{h(f)}$。

进一步得：

$$L = \frac 1{|G|}\sum_{f \in G}k^{h(f)}$$

# 例题

# P4980 【模板】Pólya 定理

$\text{Pólya}$ 定理板题。

考虑如何计算置换环个数。

枚举旋转 $k$ 个，即从 1 旋转到 $k + 1$，那么循环节长度为 $\frac {lcm(n, k)}k$，所以共有 $\frac {n}{lcm(n, k) / k} = \gcd(n, k)$ 个循环节。

$$Ans = \frac 1n\sum_{k = 1}^nn^{\gcd(n, k)}$$

然后就要用到莫反基本功了。

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

暴力计算 $\varphi$ 也可以通过。

# [POJ 1286] Necklace of Beads

题目描述

$n$ 个珠子串成一个圆，用 3 种颜色去涂色。问一共有多少种不同的涂色方法。（旋转和对称同构）

题解

旋转同构和对称同构分开考虑。

• 旋转：跟上面那道题是一样的，甚至直接暴力计算 $\gcd$ 都能过。

• 对称：

  • $n$ 为奇数：只能过一个端点对称，有 $n$ 个置换，每种置换有 $\frac {n + 1}2$ 个不同的置换环。

  • $n$ 为偶数：可以过两个端点对称，也可以切两条边对称。

    • 过端点：有 $\frac n2$ 个置换，每种置换有 $\frac n2 + 1$ 个置换环。

    • 过边：有 $\frac n2$ 个置换，每种置换 $\frac n2$ 个置换环。

置换群 $G$ 的大小为 $2n$，所以把上面所有情况都加起来之后再除以 $2n$ 就是答案。