Visits: 818

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$ 满足：

1. 若 $f,g \in G$，则 $f*g\in G$。
2. $\zeta \in G$。
3. 若 $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$ 的方格涂黑白两色，旋转后相同算一种，问一共有几种涂色方案。

置换群中包括四个置换：

1. 不旋转：$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$；
2. 顺时针旋转 $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$；
3. 逆时针旋转 $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$；
4. 旋转 $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]有色图》