等价关系

若集合 $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}{cccccc} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 5 & 1 & 3 & 6 & 2 \end{array}\right)$$

轮换表示法

$$\left(\begin{array}{cccc} 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}{cccccc} 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$ ；
• 逆元：置换是双射，故必然存在逆置换。

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

$$\begin{aligned} G& = \{ \text{顺时针旋转 } 0^\circ, 120^\circ, 240^\circ \} \\ M & = \{ \text{不考虑同构时的染色方案} \} \end{aligned}$$

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

轨道

群 $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$ 进行左陪集划分；
• $\beta \text{stab}_G(x)$ 里的元素相当于作用于 $x$ 时 $G$ 中所有与 $\beta$ 等价的置换：

轨道-稳定子定理

设有限群 $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}{cccccc} 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}{cccccc} 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}{cccccc} 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}{cccccc} 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}$$