等价关系

若集合 A 上的关系 \sim 满足如下条件：

• 自反性：\forall a \in A，a \sim a；
• 对称性：\forall a, b \in A，若 a \sim b 则 b \sim a；
• 传递性：\forall a, b \in A，若 a \sim b, \ b \sim c，则 a \sim c；

则称 \sim 是等价关系 (equivalence relation)

a \sim b := a \equiv b \pmod 7

• 自反性？对称性？传递性？
• 看起来可以把所有自然数分成 7 类……

等价类

设 \sim 是 A 上的等价关系，\forall a \in A，[a] 表示 A 中与 a 等价的全部元素构成的集合：

[a] = \{ b \sim a \mid b \in A \}

称 [a] 为 a 所在的等价类 (equivalence class)。

若 a, b \in A 且 [a] \cap [b] \neq \emptyset，则 [a] = [b]。

• 左右逆元相等：

  • 设 x 是 a 的左逆元，y 是 a 的右逆元，有：

    x = xe = x(ay) = (xa)y = y

• 满足消去律：
  • \forall a, b, c \in G, \ ab = ac \Leftrightarrow b = c

子群

设 (G, \cdot) 为群，H 是 G 的子集，若 (H, \cdot) 成群，则称 H 为 G 的子群 (subgroup)，记作 H \le G；

陪集

设 H \leq G，对于 x \in G：

• H 的一个左陪集 (left coset) xH： xH = \{ x \cdot h \mid h \in H \}
• H 的一个右陪集 (right coset) Hx： Hx = \{ h \cdot x \mid h \in H \}

\begin{aligned} xH & = \{ x \cdot h \mid h \in H \} \end{aligned}

• 若 xH \cap yH \neq \emptyset，则 xH = yH；

• 利用陪集可以对群 G 进行划分（陪集分解）：

  G = \bigcup\limits_{g \in R} gH \text{（两两不相交之并）}

• 对于 a, b \in H, g \in G，由消去律 a \neq b \Leftrightarrow ga \neq gb；
• 因此，\forall g \in R, \ |gH| = |H|: |G| = \sum\limits_{g \in R} |gH| = \sum\limits_{g \in R} |H| = |R| \cdot |H|

拉格朗日定理

设 G 为有限群，H \leq G，则：

|G| = [G : H] \cdot |H|

其中 [G : H] 称为群 H 对于群 G 的指数 (index)。

\left(\begin{array}{c} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 5 & 1 & 3 & 6 & 2 \end{array}\right)

轮换表示法

\left(\begin{array}{c} a_1 & a_2 & \dots & a_n \\ a_2 & a_3 & \dots & a_1 \end{array}\right) \xRightarrow{\text{记作}} (a_1 \enspace a_2 \enspace \dots \enspace a_n)

\left(\begin{array}{c} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 5 & 1 & 3 & 6 & 2 \end{array}\right) = (1 \enspace 4 \enspace 3) \cdot (2 \enspace 5 \enspace 6)

• 对于恒等置换，显然分解是唯一的；
• 对于非恒等置换，\exist i \text{ \ s.t. \ } \sigma(i) \neq i。
  • i \rightarrow \sigma(i) \rightarrow \sigma^2(i) \rightarrow \dots
  • 由抽屉原理，\exist t_1 < t_2 \text{ \ s.t. \ } \sigma^{t_1}(i) = \sigma^{t_2}(i)
  • 令 t 为使得 \sigma^t(i) = i 的最小正整数，则： (i \enspace \sigma(i) \enspace \dots \enspace \sigma^{t - 1}(i)) 是一个轮换。

• 对于每个这样的 i 都如此操作即可构造出一个唯一的不相交轮换分解式：
  • 每个元素在分解式中恰好出现 1 次；
  • 每个元素所属于的轮换是固定的。

轮换的幂运算

\sigma = (a_0 \enspace a_1 \enspace \dots \enspace a_{n - 1})

• \sigma^t(a_i) = a_{[(i + t) \bmod n]}
• 令 k \in N^{*} \text{ \ s.t. \ } \sigma^{tk}(a_i) = a_i：

\sigma = (a_0 \enspace a_1 \enspace \dots \enspace a_{n - 1})

• \sigma^t 可表示为 \gcd(n, t) 个长为 \frac{n}{\gcd(n, t)} 的轮换；

• a_i 所在轮换里第 j 个元素为 a_{(i + jt) \bmod n}。

  • a_i 所在轮换内元素下标模 \gcd(n, t) 均为 i；
  • a_0, a_1, \dots a_{\gcd(n, t) - 1} 一定位于不同轮换。

置换群

n 个元的所有置换，在复合运算 \circ 下成群，称作 n 元对称群 (symmetric group)，记作 S_n

• 结合律：(\sigma \circ \tau) \circ \phi = \sigma \circ (\tau \circ \phi)
• 单位元：恒等置换 \epsilon \circ x = x；
• 逆元：置换是双射，故必然存在逆置换。

用黑白两色对等边三角形顶点染色，若可通过旋转得到的方案算相同方案，求方案数？

• 一种等价关系？
• 借助该等价关系对集合进行划分？
• 有多少不同的等价类？

轨道

群 G 作用于集合 M 上，x \in M，称 M 的子集

\text{orb}_G(x) = \{ \sigma \circ x \mid \sigma \in G \}

为 x 在 G 作用下的轨道 (orbit)，简称过 x 的轨道。

\text{orb}_G(x) = \{ \sigma \circ x \mid \sigma \in G \}

x \sim y := x \in \text{orb}_G(y)

• 自反性：x \in \text{orb}_G(x)；
• 对称性：若 y \in \text{orb}_G(x)，则 x \in \text{orb}_G(y)；
• 传递性：若 z \in \text{orb}_G(y), y \in \text{orb}_G(x)，则 z \in \text{orb}_G(x)。

• 若 \text{orb}_G(x) \cap \text{orb}_G(y) \neq \emptyset，则 \text{orb}_G(x) = \text{orb}_G(y)；

• 在 M 的每一条轨道上取一个元素组成 M 的一个子集 R，称为 M 的轨道的代表元集，则：

  M = \bigcup\limits_{x \in R} \text{orb}_G(x)

  并且此中各 \text{orb}_G(x) 互不相交。

稳定子

设群 G 作用于集合 M，对 x \in M，称

\text{stab}_G(x) = \{ \sigma \mid \sigma \in G, \sigma \circ x = x \}

为群 G 作用下 x 的稳定子 (stabilizer)。

\text{stab}_G(x) = \{ \sigma \circ x = x \mid \sigma \in G \} \le G

\text{stab}_G(x) = \{ \sigma \circ x = x \mid \sigma \in G \} \le G

轨道-稳定子定理

设有限群 G 作用于集合 M ，x \in M，则：

|G| = \mid \text{stab}_G(x) \mid \cdot \mid \text{orb}_G(x) \mid

证明

\begin{aligned} \text{stab}_G(x) & = \{ \sigma \mid \sigma \in G, \sigma \circ x = x \} \\ \text{fix}(\sigma) & = \{ x \mid x \in M, \sigma \circ x = x \} \end{aligned}

\sum\limits_{x \in M} \mid \text{stab}_G(x) \mid = \sum\limits_{\sigma \in G} \mid \text{fix}(\sigma) \mid

• 每个轨道对轨道数贡献为 1，故 x \in M 对答案的贡献为 \frac{1}{\mid \text{orb}_G(x) \mid}：

\begin{aligned} | M/G | & = \sum\limits_{x \in M} \frac{1}{ \mid \text{orb}_G(x) \mid } \\ & = \sum\limits_{x \in M}\frac{ \mid \text{stab}_G(x) \mid }{ |G| } \text{（轨道-稳定子定理）} \\ & = \frac{1}{|G|}\sum\limits_{\sigma \in G} \mid \text{fix}(\sigma) \mid \end{aligned}

对正六边形的 6 个顶点，一半涂黑一半涂白。若经旋转可得到的方案算相同方案，求方案数？

旋转 0^\circ

\left(\begin{array}{c} A_1 & A_2 & A_3 & A_4 & A_5 & A_6 \\ A_1 & A_2 & A_3 & A_4 & A_5 & A_6 \end{array}\right)

将这一置换作用于 M 中的任意元素都不会使该元素发生变化，故不动元有 20 个。

旋转 60^\circ

\left(\begin{array}{c} A_1 & A_2 & A_3 & A_4 & A_5 & A_6 \\ A_6 & A_1 & A_2 & A_3 & A_4 & A_5 \end{array}\right)

若要成为不动元，则应当满足：

A_1 = A_2 = \dots = A_6

故没有不动元

旋转 120^\circ

\left(\begin{array}{c} A_1 & A_2 & A_3 & A_4 & A_5 & A_6 \\ A_5 & A_6 & A_1 & A_2 & A_3 & A_4 \end{array}\right)

若要成为不动元，则应当满足：

A_1 = A_3 = A_5, \ A_2 = A_4 = A_6

故不动元数量为 2

旋转 180^\circ

\left(\begin{array}{c} A_1 & A_2 & A_3 & A_4 & A_5 & A_6 \\ A_4 & A_5 & A_6 & A_1 & A_2 & A_3 \end{array}\right)

若要成为不动元，则应当满足：

A_1 = A_4, \ A_2 = A_5, \ A_3 = A_6

故没有不动元

• 旋转 60^\circ 与 旋转 300^\circ 情形相似；
• 旋转 120^\circ 与 旋转 240^\circ 情形相似。

轨道数：\frac{1}{6}(20 + 2 + 2) = 4

分析

\begin{aligned} G & = \{ \text{顺时针旋转} \frac{2\pi}{n}, \dots, (n - 1)\frac{2\pi}{n}, 2\pi, \\ & \text{过每一条对称轴的翻转 } \} \\ M & = \{ \text{不考虑同构的所有染色方案} \} \end{aligned}

G 作用于 M

若将环上的元素按顺时针编号：0, 1, \dots (n - 1)

• 顺时针旋转 k \frac{2\pi}{n}：\sigma_k(i) = (i + k) \bmod n；
• 沿过点 a 的对称轴翻转： \tau_a(i) = \begin{cases} i & i = a \text{ \ or \ } a \text{ 对面的点 } \\ (2a - i) \bmod n & \text{ otherwise } \end{cases}

旋转

• 旋转置换一共 n 种；
• 旋转 \frac{2\pi}{n} 时只能分解成一个不交轮换；
• 旋转 i \frac{2\pi}{n} 可看作前者的 i 次幂，故可拆成 \gcd(n, i) 个轮换：

\sum\limits_{\sigma} \mid \text{fix}(\sigma) \mid = \sum\limits_{i = 1}^{n} m^{\gcd(n, i)}

\begin{aligned} \sum\limits_{g \in G} \mid \text{fix}(\sigma) \mid & = \sum\limits_{i = 1}^{n} m^{\gcd(n, i)} \\ & = \sum\limits_{d \mid n} m^d \sum\limits_{i = 1}^{n} [ \gcd(n, i) = d ] \\ & =\sum\limits_{d \mid n} m^d \sum\limits_{i = 1}^{\frac{n}{d}} [ \gcd(\frac{n}{d}, i) = 1 ] \\ & = \sum\limits_{d \mid n} m^d \cdot \varphi(\frac{n}{d}) \end{aligned}

翻转

• 翻转置换一共 n 种。
• n 为偶数：
  • \frac{n}{2} 条过点的对称轴：c(\tau) = \frac{n}{2} + 1
  • \frac{n}{2} 条过边的对称轴：c(\tau) = \frac{n}{2} \sum\limits_{\tau} \mid \text{fix}(\tau) \mid = \frac{n}{2} \cdot m^{\frac{n}{2} + 1} + \frac{n}{2} \cdot m^{\frac{n}{2}}

• n 为奇数：
  • n 条 既过点又过边的对称轴：c(\tau) = \frac{n + 1}{2}
  \sum\limits_{\tau} \mid \text{fix}(\tau) \mid = n \cdot m^{\frac{n + 1}{2}}

结论

\begin{aligned} | M/G | & = \frac{\sum\limits_{\sigma} \mid \text{fix}(\sigma) \mid + \sum\limits_{\tau} \mid \text{fix}(\tau) \mid}{2n} \\ & = \frac{1}{2n}\sum\limits_{d \mid n} m^d \cdot \varphi(\frac{n}{d}) \\ & + \frac{1}{2n} \begin{cases} \frac{n}{2} \cdot m^{\frac{n}{2} + 1} + \frac{n}{2} \cdot m^{\frac{n}{2}} & 2 \mid n \\ n \cdot m^{\frac{n + 1}{2}} & 2 \nmid n \end{cases} \end{aligned}

复杂度：\mathcal{O}(d(n) \cdot \sqrt{n})，d(n) 代表 n 的约数个数。

分析

\begin{aligned} G & = \{ \text{顺时针旋转} \frac{2\pi}{n}, \dots, (n - 1)\frac{2\pi}{n}, 2\pi \} \\ M & = \{ \text{满足限制且不计同构的染色方案} \} \end{aligned}

• 旋转 \frac{2\pi}{n} 只能分解成一个不交轮换；
• 旋转 i \frac{2\pi}{n} 可看作前者的 i 次幂，因此：
  • 可表示为 \gcd(n, i) 个不交轮换之积；
  • 标号模 \gcd(n, i) 结果相同的点在同一轮换内。

DP 求不动元数量

• 记 \text{v} \langle a, b, c, d \rangle 代表是否允许 a, b, c, d 四种颜色相邻；

\text{v} \langle a, b, c, d \rangle = \begin{cases} 0 & \text{不允许 } a, b, c, d \text{ 相邻} \\ 1 & \text{允许 } a, b, c, d \text{ 相邻} \end{cases}

• 记 \text{dp} \langle i, a, b, c \rangle 代表 i 个元素排成一排，最后 3 个元素的颜色分别为 a, b, c 的方案数： \text{dp} \langle i, a, b, c \rangle = \sum\limits_{k} \text{v} \langle k, a, b, c \rangle \cdot \text{dp} \langle i - 1, k, a, b \rangle

矩阵快速幂优化 DP

\text{dp} \langle i, a, b, c \rangle = \sum\limits_{k} \text{v} \langle k, a, b, c \rangle \cdot \text{dp} \langle i - 1, k, a, b \rangle

\begin{aligned} \begin{bmatrix} \text{dp} \langle i, 1, 1, 1 \rangle \\ \text{dp} \langle i, 1, 1, 2 \rangle \\ \vdots \\ \text{dp} \langle i, 4, 4, 4 \rangle \end{bmatrix} \end{aligned} = T \cdot \begin{aligned} \begin{bmatrix} \text{dp} \langle i - 1, 1, 1, 1 \rangle \\ \text{dp} \langle i - 1, 1, 1, 2 \rangle \\ \vdots \\ \text{dp} \langle i - 1, 4, 4, 4 \rangle \end{bmatrix} \end{aligned}

• 枚举前三 3 个元素的颜色 \langle a, b, c \rangle 时，初始化： \begin{aligned} \begin{bmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{bmatrix} \end{aligned}, \begin{aligned} \begin{bmatrix} 0 \\ 1 \\ \vdots \\ 0 \end{bmatrix} \end{aligned}, \dots, \begin{aligned} \begin{bmatrix} 0 \\ 0 \\ \vdots \\ 1 \end{bmatrix} \end{aligned}
• 等价于 T^{n} 直接乘上单位矩阵；
• T^{n} 主对角线元素之和即为所有不动元数量。

结论

分析

\begin{aligned} G & = S_n \enspace (n \text{阶对称群}), \ \mid S_n \mid = n! \\ M & = \{ \text{不计同构的无向图染色方案} \} \end{aligned}

• 置换是对点的置换，而染色是对边染色；
• 两点确定一条边，分析边两端点的情况。

两端在同一轮换内的边

\sigma = (1 \enspace 3 \enspace 5 \enspace 6) \cdot (2 \enspace 4)

(a_0 \enspace a_1 \enspace \dots \enspace a_{l - 1})

\langle a_i, a_j \rangle \rightarrow \langle a_{(i + 1) \bmod l}, a_{(j + 1) \bmod l} \rangle \rightarrow \dots

(a_0 \enspace a_1 \enspace \dots \enspace a_{l - 1})

\langle a_i, a_j \rangle \rightarrow \langle a_{(i + 1) \bmod l}, a_{(j + 1) \bmod l} \rangle \rightarrow \dots

(a_0 \enspace a_1 \enspace \dots \enspace a_{l - 1})

• 对于边 \langle a_i, a_j \rangle 所在的边轮换：
  • 若 2 \mid l 且 \mid j - i \mid = \frac{l}{2}，则其大小为 \frac{l}{2}；
  • 否则其大小为 l；
• \mid j - i \mid \bmod l 相同的边在同一边轮换内，故边轮换个数为 \lfloor \frac{l}{2} \rfloor。

两端在不同轮换内的边

\sigma = (1 \enspace 3 \enspace 5 \enspace 6) \cdot (2 \enspace 4)

• 两点在不同点轮换里的边：
  • \langle 1, 2 \rangle \rightarrow \langle 3, 4 \rangle \rightarrow \langle 5, 2 \rangle \rightarrow \langle 6, 4 \rangle
  • \langle 1, 4 \rangle \rightarrow \langle 3, 2 \rangle \rightarrow \langle 5, 4 \rangle \rightarrow \langle 6, 2 \rangle

(a_0 \enspace a_1 \enspace \dots \enspace a_{l - 1}) \cdot (b_0 \enspace b_1 \enspace \dots \enspace b_{s - 1} )

\langle a_i, b_j \rangle \rightarrow \langle a_{(i + 1) \bmod l}, b_{(j + 1) \bmod s} \rangle \rightarrow \dots

点轮换与边轮换的关系

\sigma = \prod\limits_{i = 1}^{k} c_i \quad (\text{轮换 } c_i \text{ 长度为 } l_i)

• 可表示成边轮换的个数： \sum\limits_{i = 1}^{k} \left\lfloor \frac{l_i}{2} \right\rfloor + \sum\limits_{i = 1}^{k}\sum\limits_{j = i + 1}^{k} \gcd(l_i, l_j)

剪枝

• 枚举 n 的拆分方案：

  n = \sum\limits_{i = 1}^{k} l_i \ (l_1 \le l_2 \le \dots \le l_k)

• 每一种拆分方案对应多少点置换？

结论

• 对 n 的每一种拆分方案：n = \sum\limits_{i = 1}^{k} l_i
  • l_1 \le l_2 \le \dots \le l_k；
  • 记共有 s 种不同长度的轮换，其中第 i 种轮换的个数为 q_i；
  • 其对应的点轮换数量为：

\frac{n!}{(\prod\limits_{i = 1}^{k} l_i) \cdot (\prod\limits_{i = 1}^{s} q_i!)}

\begin{aligned} & \frac{1}{|G|} \sum\limits_{\sigma \in G} \mid \text{fix}(\sigma) \mid \\ & = \frac{1}{n!} \cdot \sum\frac{n!}{(\prod\limits_{i = 1}^{k} l_i) \cdot (\prod\limits_{i = 1}^{s} q_i!)} \cdot m^{\sum\limits_{i = 1}^{k} \left\lfloor \frac{l_i}{2} \right\rfloor + \sum\limits_{i = 1}^{k}\sum\limits_{j = i + 1}^{k} \gcd(l_i, l_j)} \end{aligned}

• 复杂度 \mathcal{O} \left( \sum\limits_{p \in \text{Partition}(n)} \text{len}^2(p) \cdot \log{n} \right)
• 其实题目数据范围内 \text{Partition}(n) 大小不大…… 所以 \mathcal{O}(\text{能过})。

思路回顾

• 置换是对点的置换，均可分解成点轮换之积；
• 染色对边染色，同一边轮换内边染色方案相同；
• 点轮换和边轮换之间的关系？
• 只关心边轮换个数，其只与点轮换的大小情况有关，枚举点轮换的大小情况……

相关题目 #1

• HDU 1817: Necklace of Beads
• HDU 3547: DIY Cube
• HDU 3441: Rotation
• POJ 2888: Magic Bracelet
• 洛谷 P1446: Cards

相关题目 #2

• 洛谷 P4128: 有色图
• ICPC 2014 鞍山 K: Colorful Toy
• HDU 6360: Kaleidoscope
• ICPC 2019 南昌 J: Summon
• ICPC 2019 银川 M: Crazy Cake

参考资料

• 近世代数引论/冯克勤,李尚志,章璞编著.-3版.-合肥：中国科学技术大学出版社,2009.12
• 近世代数初步/石生明.-2版.-北京：高等教育出版社,2006.3
• Contemporary Abstract Algebra/Joseph A. Gallian.-8th Edition
• 群论初探 - nosta - 博客园