置换群学习笔记

置换群的相关内容主要用于解决一类“充满对称性”的计数问题。基于轨道-稳定子群定理的 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})$。

相关资料

参考:

  • 《浅谈群论在信息学竞赛中的简单应用》虞皓翔,IOI中国国家候选队论文2020

相关题目:

  1. 「AHOI2002」黑白瓷砖
  2. 「HNOI2008」Cards
  3. 「LG-P4980」Pólya 定理
  4. 暂无来源

进阶指南丧命指南:

作者

ce-amtic

发布于

2020-11-26

更新于

2021-03-10

许可协议

CC BY-NC-SA 4.0

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×