群论学习笔记 · 徐皓天

OI 中的群论

理论

置换群

置换就是把 $n$ 个元素做一个排列变换，一般地，把 $i$ 变成 $a_i$ 的置换记为 $\left( \begin{matrix} 1 & 2 & \dots & n \\\\ a_1 & a_2 & \dots & a_n \end{matrix} \right)$ 。

置换本质上为一一映射的函数，因此置换可以结合，有结合律。

置换 $\zeta = \left( \begin{matrix} 1 & 2 & \dots & n \\\\ 1 & 2 & \dots & n \end{matrix} \right)$ 为恒等置换。若置换 $f,g$ 满足 $f*g=\zeta$ ，则 $g$ 为 $f$ 的逆，记作 $f^{-1}$ 。

一个置换的集合 $G$ 满足：

若 $f,g \in G$ ，则 $f*g\in G$ 。
$\zeta \in G$ 。
若 $f \in G$ ，则 $f^{-1} \in G$ 。

则称 $G$ 为一个置换群。

在置换群的作用下，元素存在等价关系。等价关系满足自反性、对称性、传递性。满足等价关系的元素处于同一个等价类中。

Burnside 引理

对于一个置换 $f$ ，若一个元素 $s$ 经过 $f$ 后不变，则称 $s$ 为 $f$ 的不动点。

记 $f$ 的不动点个数为 $C(f)$ ，则对于一个置换群，等价类个数为所有 $C(f)$ 的平均值。

Polya 定理

置换可以分解成循环的乘积，其中每个循环代表一些元素的“循环移位”。如 $\left( \begin{matrix} 1 & 2 & 3 & 4 & 5 \\\\ 3 & 5 & 1 & 4 & 2 \end{matrix} \right) = (1\ 3)(2\ 5)(4)$ 。

循环节为循环的个数，如 $(1\ 3)(2\ 5)(4)$ 的循环节为 $3$ 。

对于一个置换 $f$ ， $C(f)=k^{m(f)}$ ，其中 $k$ 为颜色数， $m(f)$ 为 $f$ 的循环节。

综上，在置换群中，等价类个数等于所有置换 $f$ 的 $k^{m(f)}$ 的平均数。

【练习】UVA12103 Leonardo's Notebook、SP1843 LEONARDO - Leonardo Notebook

【练习】UVA1156 Pixel Shuffle

应用

【例题】经典问题

给 $2 \times 2$ 的方格涂黑白两色，旋转后相同算一种，问一共有几种涂色方案。

置换群中包括四个置换：

不旋转： $f = \left( \begin{matrix} 1 & 2 & 3 & 4 \\\\ 1 & 2 & 3 & 4 \end{matrix} \right) = (1)(2)(3)(4), C(f) = k ^ {m(f)} = 2 ^ 4 = 16$ ；
顺时针旋转 $90^\circ$ ： $f = \left( \begin{matrix} 1 & 2 & 3 & 4 \\\\ 2 & 3 & 4 & 1 \end{matrix} \right) = (1\ 2\ 3\ 4), C(f) = k ^ {m(f)} = 2 ^ 1 = 2$ ；
逆时针旋转 $90^\circ$ ： $f = \left( \begin{matrix} 1 & 2 & 3 & 4 \\\\ 4 & 1 & 2 & 3 \end{matrix} \right) = (1\ 2\ 3\ 4), C(f) = k ^ {m(f)} = 2 ^ 1 = 2$ ；
旋转 $180^\circ$ ： $f = \left( \begin{matrix} 1 & 2 & 3 & 4 \\\\ 3 & 4 & 1 & 2 \end{matrix} \right) = (1\ 3)(2\ 4), C(f) = k ^ {m(f)} = 2 ^ 2 = 4$ 。

综上，答案为 $\frac{16+2+2+4}{4} = 6$ 。

【例题】经典问题扩展

经典问题相当于：圆上有 $4$ 个点， $2$ 种颜色，旋转同构，求方案数。
我们把它扩展一下：圆上有 $n$ 个点， $k$ 种颜色，旋转同构，求方案数。

仔细分析可以发现，当我们旋转 $i$ 个点时，一共会有 $\gcd(i,n)$ 个循环，每个循环会有 $\frac{n}{\gcd(i,n)}$ 个元素。

因此 $ans = \frac{1}{n} \sum_{i = 0}^{n-1} k^{\gcd(i,n)}$ 。

【练习】P4980 【模板】Polya定理

【例题】经典问题再扩展

圆上有 $n$ 个点， $k$ 种颜色，旋转同构，翻转同构，求方案数。

旋转同构总共形成 $a=\sum_{i = 0}^{n-1} k^{\gcd(i,n)}$ 个不动点。

翻转同构分两种情况考虑：

当 $n$ 为奇数时，对称轴有 $n$ 条，每条对称轴形成 $\frac{n-1}{2}$ 个长度为 $2$ 的循环， $1$ 个长度为 $1$ 的循环，共 $\frac{n+1}{2}$ 个循环，因此总共形成 $b=nk^{\frac{n+1}{2}}$ 个不动点。

当 $n$ 为偶数时，有两种对称轴。穿过两个点的对称轴有 $\frac{n}{2}$ ，共形成 $\frac{n}{2} + 1$ 个循环；不穿过点的对称轴有 $\frac{n}{2}$ ，共形成 $\frac{n}{2}$ 个循环，因此总共形成 $b=\frac{n}{2}(k^{\frac{n}{2} + 1} + k^{\frac{n}{2}})$ 个不动点。

综上， $ans = \frac{a+b}{2n}$ 。

【练习】UVA10294 Arif in Dhaka (First Love Part 2)

【例题】P4128 [SHOI2006]有色图

请参考小粉兔的题解，~~窝写不过他 QwQ~~

【练习】P4727 [HNOI2009]图的同构记数

参考资料

刘汝佳 & 陈锋《算法竞赛进阶指南·入门经典》
Richard A. Brualdi 《组合数学》
小粉兔《洛谷 P4128: bzoj 1815: [SHOI2006]有色图》

理论

置换群