2020-11-26发表2023-04-15更新OI笔记15 分钟读完 (大约2281个字)

置换群学习笔记

置换群的相关内容主要用于解决一类“充满对称性”的计数问题。基于轨道-稳定子群定理的 Burnside 引理和引申出的 Pólya 计数原理是我们解决这类问题的有力工具……

群

对于一个非空集合 $S$ 和该集合上定义的二元运算 $·$，当该运算满足一些性质时，我们称它们构成一个群，记作 $(S,·)$。运算需要满足的性质是：

封闭性：$\forall x,y\in S, x·y\in S$
结合性：$\forall x,y,z\in S,(x·y)·z=x·(y·z)=x·y·z$
存在单位元：$\exists e\in S, \text{s.t. }\forall y\in S, e·y=y$
存在逆元：$\forall y\in S,\exists x\in S,\text{s.t. } x·y=e$

这是群论的基本定义，在 OI 界，更加常用的是置换群。

置换和置换群

置换：一个从某个排列到某个排列的双射称作置换，记作 $p:f\to g$，其中 $f\to g$ 指代某种双射。
乘法：两个置换 $u,v$ 的乘法定义为它们对排列先后作用得到的结果，记作 $v·u$。
置换群：根据群论的基本概念，置换构成的集合和建立在置换上的乘法构成置换群。

然后是一些有关于计数的概念。

染色：给序列中的每个元素分配一个“颜色”从而得到的不同序列的过程称作染色。形式化地，可以用序列 $c$ 表示一个染色，其中 $c[i]$ 表示 $i$ 这个位置上的颜色。所有染色组成染色全集 $\mathcal{C}$。
置换对染色的作用：对于一个置换 $g$，其作用于某个染色 $c$ 可以得到一个新的染色，记作 $g·c$。
置换群对染色的作用（轨道）：对于一个置换群 $G$ 和一个染色 $c$，将所有 $g\in G$ 作用于 $c$ 得到的集合称作 $c$ 在 $G$ 下的轨道，记作 $G·c=\begin{Bmatrix}g·c\text{ | }g\in G \end{Bmatrix}$。

Burnside 引理与 Pólya 计数原理用于解决在某种置换群 $G$ 作用下染色集合 $X\subseteq \mathcal{C}$ 共有多少本质不同的元素，即轨道数 $|X/G|$。

Burnside 引理

设 $X\subseteq \mathcal{C}$ 是某个染色集合， $G$ 是作用在 $X$ 上的置换群，我们记 $X/G$ 为在 $G$ 作用下 $X$ 的轨道集合，即 $X/G=\begin{Bmatrix} gc\text{ | } c\in X, g\in G\end{Bmatrix}$。

不动点（稳定子）：置换 $g\in G$ 作用在 $X$ 上的不动点为 $X$ 中在 $g$ 作用下不发生变化的元素，组成的集合即 $\begin{Bmatrix}c\in X\text{ | }gc=c\end{Bmatrix}$，记作 $X^g$。

Burnside 引理指出，轨道数 $|X/G|$ 等于 $G$ 中所有置换对应的不动点个数的平均值，即有：

$$ |X/G|= \dfrac{1}{|G|}\sum\limits_{g\in G}|X^g| $$

Pólya 计数原理

置换的循环表示：简单来讲，如果把置换的双射看成图上的有向边，那么置换显然是成环的。我们可以据此把一个置换拆分成若干置换（轮换）的乘积，这称作置换的循环表示。
循环数：某一个置换 $g$ 具有的轮换的个数称作循环数，记作 $\chi(g)$。

Pólya 原理指出，如果对于所有染色序列 $c\in X$ ，如果 $c$ 的所有位置可分配的颜色集合 $S$ 相同，那么不动点个数恰等于色数的循环数次方，即 $|X^g|=|S|^{\chi(g)}$。

根据 Burnside 引理，可以进一步得到一个常见的计数公式：

$$|X/G|=\dfrac{1}{|G|}\sum\limits_{g\in G}|S|^{\chi(g)}$$

一道栗题

$n(n+1)/2$ 个格子形成一个 $n$ 层的三角形，我们要给每个格子涂上黑白两种颜色。三角形可以沿中线翻转或顺/逆时针旋转，问一共有多少种本质不同的涂色方式。
$n\le 20$

显然，旋转的置换一共有三种 $\sigma^0,\sigma^1,\sigma^2$，翻转的置换题目给出了一种。考虑到置换群需要满足自闭性，那么先翻转再旋转的置换也应当位于置换群中，这等价于沿着一条斜着的中线翻转。因此翻转的置换也共有三种。

然后需要求出某种置换的循环数。$\sigma^0$ 显然是 $n(n+1)/2$，$\sigma^1,\sigma^2$ 容易发现是 $\lceil n(n+1)/6 \rceil$，翻转的循环数显然是 $(n(n-1)/2-\lceil n/2\rceil)/2+\lceil n/2\rceil$，从而答案是 $\dfrac{1}{6}(2^{\binom{n+1}{2}}+2^{\lceil n(n+1)/6 \rceil+1}+3·2^{(\binom{n+1}{2}-\lceil n/2\rceil)/2+\lceil n/2\rceil})$。

又一道栗题

给定三个整数 $A,B,C$ 和由 $m$ 个置换形成的置换群 $G=\begin{Bmatrix}p_1, p_2, …, p_m\end{Bmatrix}$。需要给 $n=A+B+C$ 个格子涂三种颜色，满足三种颜色的格子各有 $A,B,C$ 个，问在 $G$ 作用下共有多少不同的涂色方案。
$A,B,C\le 20,m\le 60$

考虑如何求在某个置换作用下的不动点个数。把每个置换循环分解，一个轮换上的点显然只能涂同一种颜色。然后看上去就可以背包一下，DP 把方案数计出来，套一个 Burnside 引理就可以算了。

朴素的复杂度大概是 $O(mnA^3)$，可能还能进一步优化。

双一道栗题

现在有 $n$ 个点的环，需要给每个点染上 $m$ 种颜色 $0\text{ ~ }m-1$ 之一。环可以旋转，旋转得到的环视为相同的环，问有多少种本质不同的染色方案。
$ n,m\le 10^9 $

考虑先写出置换群 $G$ 来。我们设 $\sigma$ 为一次顺时针旋转（转动一个单位），则有 $G=\begin{Bmatrix} \sigma ^{x} \text{ | }x\ge 0\end{Bmatrix}$。注意到旋转 $n$ 次等价于不旋转，则 $|G|=n$。

根据 Pólya 原理，在 $\sigma^{i}$ 下的不动元素数 $|X|^{\sigma ^i}=m^{\chi(\sigma^i)}$。把 $\chi(\sigma^i)$ 写成循环表示的形式，即 $\sigma^i=(1,i,2i,…)(2,i+1,2i+1,…)…$，容易发现循环数为 $(i,n)$，这里的小括号特指两个数的最大公因数（Greatest Common Divisor, GCD）。

从而答案是 $\dfrac{1}{n}\sum\limits_{i=1}^n m^{(i,n)}$。

注意到 $(i,n)|n$，化一下柿子变成：
$$\begin{aligned}&\dfrac{1}{n}\sum\limits_{i=1}^n m^{(i,n)}\newline =& \dfrac{1}{n}\sum\limits_{d|n}m^d \sum\limits_{i=1}^n[(i,n)=d]\newline =&\dfrac{1}{n}\sum\limits_{d|n}m^d \sum\limits_{d|i,i\le n}[(i/d,n/d)=1]\newline =&\dfrac{1}{n}\sum\limits_{d|n}m^d \varphi(n/d)\end{aligned}$$

直接做就是 $O(d(n)\sqrt{n})$。

叒一道栗题

现在有 $n$ 个点的环，需要给每个点染上 $m$ 种颜色 $0\text{ ~ }m-1$ 之一。有两类置换：

将环旋转若干次
给环上每个点的编号 $+1$ 再模 $m$。

问共有多少种本质不同的染色方案。
$n,m\le 10^{18}$

设 $G_1=\begin{Bmatrix}\sigma^0,\sigma^1,…,\sigma^{n-1} \end{Bmatrix}$ 是旋转操作 $\sigma$ 的置换群， $G_2=\begin{Bmatrix}\tau^0,\tau^1,…,\tau^{m-1} \end{Bmatrix}$ 是加法操作 $\tau$ 的置换群，则本题中作用在环上的置换群 $G=G_1\times G_2$，其中 $\times$ 表示笛卡尔积。

分析一下不动点的个数，得到的柿子是：
$$\begin{aligned}&\dfrac{1}{nm}\sum\limits_{i=1}^n\sum\limits_{k=1}^m [k\text{ is legal}]m^{(n,i)} \newline =&\dfrac{1}{nm}\sum\limits_{i=1}^nm^{(n,i)}\sum\limits_{k=1}^m [m|\dfrac{kn}{(n,i)}]\newline =&\dfrac{1}{nm}\sum\limits_{i=1}^nm^{(n,i)}(m,n/(n,i))\end{aligned}$$

第一个柿子里的 $[k\text{ is legal}]$ 这个条件一看就很吓人。但是冷静分析一下，就可以注意到我们实际上是需要轮换上相邻数字之差在模 $m$ 意义下恰好为 $k$，那么只需要判断是否能填充一个合法的轮换，即是否存在 $m|lk$，其中 $l$ 是轮换长，满足 $l=n/(n,i)$。

化一下变成：
$$\begin{aligned} =&\dfrac{1}{nm}\sum\limits_{d|n}m^d(m,n/d)\sum\limits_{i=1}^{n/d}[(i,n/d)=1]\newline =& \dfrac{1}{nm}\sum\limits_{d|n}m^d(m,n/d)\varphi(n/d)\end{aligned}$$

直接做是 $O(d(n)\sqrt{n})$，加个 Pollard-Rho 强行降成 $O(d(n)n^{1/4})$。