Polya 定理入门
2huk
·
·
算法·理论
群的定义
定义二元组 (G,*) 是一个群，其中 G 是一个集合，* 是一种二元运算，当且仅当其满足：
- 封闭性：对于任意 a,b\in G，都有 a * b \in G。
- 结合律：对于任意 a,b,c \in G，(a*b)*c = a*(b*c)。
- 存在单位元：存在一个元素 e \in G，满足对于任意 a \in G，都有：a * e = e * a = a
我们称 e 为单位元。
- 存在逆元：对于任意 a \in G，存在 a^{-1} \in G 满足：a*a^{-1}=a^{-1}*a = e
我们称 a^{-1} 为 a 的逆元。
在不引起歧义的情况下，我们有时也会直接把 G 称作一个群。
我们有如下基本性质：
- 单位元唯一：如果存在两个单位元 e_1,e_2，那么根据定义，e_1*e_2 = e_1，以及 e_1 * e_2 = e_2。因此 e_1=e_2。
-
- 逆元唯一：假设 b,c 同时为 a 的逆元，即 a*b=a*c=e，则 b=b*e = b*(a*c)=(b*a)*c=e*c=c。
子群和陪集
对于一个群 (G,*)，定义 (H,*) 为其子群，当且仅当 H \subseteq G 且 (H,*) 本身也是一个群。
考虑什么样的 H 是子群。在四条要求中，首先结合律是天然满足的。因此我们只需要额外要求 H 是封闭的、存在单位元、以及所有元素都存在逆元即可。容易发现 H 的单位元就是 G 的单位元。
对于 G 及其子群 H，以及一个元素 g \in G，定义左陪集：
gH = \{gh \mid h \in H\}
同样的定义右陪集：
Hg = \{hg \mid h \in H\}
不过后面我们没用过右陪集，所以后面的陪集都是指的左陪集。
关于陪集的性质，我们在下一节边证定理边说。
拉格朗日定理
对于有限群 G 及其子群 H，定义 [G:H] 表示 H 在 G 中的不同陪集个数。即：
[G:H] = |\{gH \mid g \in G\}|
拉格朗日定理：
|G|=|H| \times [G:H]
我们来证明它。
首先定义等价关系 \sim：
- 对于 a,b \in G，a \sim b 当且仅当 a^{-1}b \in H。
证明等价需要证自反性、对称性和传递性。分别来看：
- 自反性：即 a \sim a，即 a^{-1}a \in H。显然 a^{-1}a = e \in H。
- 对称性：若 a \sim b，即 a^{-1}b \in H。根据 H 的定义，a^{-1}b 的逆元 b^{-1}a 也在 H 中。因此 b \sim a。
- 传递性：若 a\sim b, b\sim c，即 a^{-1}b \in H,b^{-1}c \in H，那么根据封闭性，(a^{-1}b)(b^{-1}c) 也就是 a^{-1}c 也在 H 中。因此 a \sim c。
所以，根据这个等价关系，可以将 G 划分为若干等价类。
对于 a \in G，记 [a] 表示 a 所在的等价类。即 [a] = \{x\mid a \sim x\}，也即 [a] = \{x \mid a^{-1}x \in H\}。同时，如果 a\sim b，则 [a]=[b]。
设 a^{-1}x = h。同时左乘 a 得到 x = ah。因此 [a] = \{ah \mid h \in H\}。而这正好是陪集的定义，即 [a] = aH。
因此我们得到陪集的性质：
- 对于 a,b\in G，aH = bH 当且仅当 a^{-1}b \in H。
总结一下。将 G 分成若干等价类后，对于一个等价类 O 以及任意 a,b \in O，有 aH = bH = O。
而这个等价类的个数就是 [G:H]。因此，如果我们能证明每个等价类的大小都是 |H|，就能得到拉格朗日定理 |G| = |H| \times [G:H] 了。
即我们证明另一个陪集的性质：
即证明 |\{ah \mid h \in H\}| = |H|，直观理解就是没有重复的，即对于 h_0,h_1 \in H 且 h_0 \ne h_1，都有 ah_0 \ne ah_1。反过来，如果 ah_0 = ah_1。左乘 a^{-1} 就得到 h_0 = h_1。
这样就得到了优美的拉格朗日定理。
群作用
对于一个群 (G,*) 以及一个外部集合 X。我们定义另一个二元运算 \cdot，对于 g \in G,x \in X，有 g \cdot x \in X。群 G 作用在 X 上，指的就是存在这个映射 \cdot，且满足：
- 对于 x \in X，e \cdot x = x。
- 对于 g_0,g_1 \in G,x \in X，(g_0 * g_1) \cdot x = g_0 \cdot (g_1 \cdot x)。
注意这两种运算（*,\cdot）是不同的。
直观上可以把 G 看作一些变换。对于一个外部集合内的元素 x，把它放到 G 中进行某一种变化，假设是变化 g，得到的新元素就是 g \cdot x。
轨道-稳定子定理
这个的断句可不是 轨道/稳定/子定理。
对于 x \in X，我们定义轨道 Orb(x) 以及稳定子 Stab(x)。
-
Orb(x) = \{g \cdot x \mid g \in G\}
-
Stab(x) = \{g \mid g \cdot x = x\}
很形象，轨道就是把 x 通过一些变换能得到的元素，稳定子就是那些使 x 不变的变换。
这里也引入一个等价关系。
- 对于 x,y \in X，x \sim y 当且仅当存在 g \in G 使得 g \cdot x = y。
证明等价依然三步：
- 自反性：即 x \sim x。显然取 e \in G 即可，因为 e \cdot x = x。
- 对称性：即如果 x \sim y 则 y \sim x。设 g \cdot x = y，同时左乘 g^{-1} 得到 x = g^{-1} \cdot y。而 g^{-1} \in G，所以 y \sim x。
- 传递性：即如果 x \sim y,y \sim z，则 x \sim z。设 g_0 \cdot x = y, g_1 \cdot y = z，那么 g_1 \cdot (g_0 \cdot x) = z，即 g_1g_0 \cdot x = z。而 g_1g_0 \in G，所以 x \sim z。
如法炮制，将 X 分成若干等价类后，对于一个等价类 O 以及任意 x,y \in O，有 Orb(x) = Orb(y) = O。我们称一个等价类为一个轨道。
轨道-稳定子定理：
|G| = |Orb(x)|\times |Stab(x)|
证它！
考虑刚才的拉格朗日定理：
|G| = |H| \times [G:H]
如果我们把 Stab(x) 视作 H，就可以得到：
|G| = |Stab(x)| \times [G:Stab(x)]
然后直接证明 [G:Stab(x)] = |Orb(x)| 即可。
在这之前，我们要先证一下 Stab(x) 是 G 的子群，不然直接代入 H 是不对的。考虑分别证明这三条：
- 封闭性：即对于 a,b \in Stab(x)，有 a*b \in Stab(x)。根据定义，a \cdot x = b \cdot x = x，因此 a \cdot (b \cdot x) = x，即 (a * b) \cdot x = x。因此 a * b \in Stab(x)。
- 存在单位元：e * x = x，因此 e \in Stab(x)。
- 存在逆元：即对于 a \in Stab(x)，其逆元 a^{-1} \in Stab (x)。根据定义，a \cdot x = x，左乘 a^{-1} 得到 x = a^{-1} \cdot x。因此 a^{-1} \in Stab(x)。
然后证明 [G:Stab(x)] = |Orb(x)|。构造映射 \varphi : \{g Stab(x) \mid g \in G\} \to Orb(x)。
定义 \varphi(gStab(x)) = g * x。即，对于一个陪集，任意取出它的这个等价类中的任意一个元素 g，然后定义这个陪集映射到 g * x。
首先要证明这个映射是良定义的。即对于 g_0,g_1 \in G，如果 g_0 Stab(x) = g_1Stab(x)，则 g_0 \cdot x = g_1 \cdot x。
根据陪集的性质，g_0 Stab(x)=g_1 Stab(x) 等价于 g_0^{-1}g_1 \in Stab(x)。即 g_0^{-1}g_1 \cdot x = x。同时左乘 g_0 即可得到 g_1 \cdot x = g_0 \cdot x。
然后要证明这个映射是单射以及满射。
- 单射：即对于 g_0,g_1 \in G，如果 \varphi(g_0 Stab(x)) = \varphi(g_1 Stab(x))，那么 g_0Stab(x) = g_1Stab(x)。根据 \varphi 定义得到 g_0 \cdot x = g_1 \cdot x。同时左乘 g_0^{-1} 得到 x = g_0^{-1}g_1 \cdot x，因此 g_0^{-1}g_1 \in Stab(x)。根据陪集的性质得到 g_0Stab(x) = g_1Stab(x)。
- 满射：即对于任意 y \in Orb(x)，都存在 \varphi(g Stab(x)) = y。根据定义，存在 g \in G 满足 g \cdot x = y。这个 g 是定值，那么 \varphi(g Stab(x)) = g \cdot x = y。
这样就得到了轨道-稳定子定理。
Burnside 引理
设 t 为轨道个数，即 X 的等价类个数。
对于 g \in G，定义 g 的不动点个数 Fix(g) = \{x \mid g \cdot x = x\}。注意别把它和 Stab(x) 搞混了。
Burnside 引理：
t = \dfrac 1{|G|} \sum_{g \in G} |Fix(g)|
证证证！
显然 \sum_{g \in G}|Fix(g)| = \sum_{x \in X} |Stab(x)|，因为两边都是满足 g * x = x 的 (g,x) 对的数量。因此：
t = \dfrac 1{|G|}\sum_{x \in X} |Stab(x)|
设 X 的所有等价类为 O_1,O_2 \dots O_t。把枚举顺序改成：
t = \dfrac 1{|G|} \sum_{i=1}^{t} \sum_{x \in O_i} |Stab(x)|
根据轨道-稳定子定理，有：
|Stab(x)| = \dfrac{|G|}{|Orb(x)|}
而我们已经枚举了这个轨道。即 Orb(x)=O_i。因此：
\sum_{x \in O_i} |Stab(x)| = \sum_{x \in O_i} \dfrac{|G|}{|Orb(x)|} = |O_i| \times \dfrac{|G|}{|O_i|} = |G|
所以：
\dfrac 1{|G|} \sum_{i=1}^t |G| = t
这样就得到了 Burnside 引理。
实际意义
会了 Burnside 引理后已经可以做一些题了。先把式子贺下来：
t = \dfrac 1{|G|} \sum_{g \in G} |Fix(g)|
考虑其实际意义。一般 G 是某些变换及其复合，X 是你要计数的东西。t 就是答案，即 X 中的满足某种性质的本质不同的元素。其中，X 中的两个元素本质相同，当且仅当其中一个可以通过 G 中的变换得到另一个。
Polya 定理
先从 P4980 【模板】Pólya 定理 说起：
有一个 n 个点，n 条边的环，有 n 种颜色，给每个顶点染色，问有多少种本质不同的染色方案。两个环本质相同当且仅当一个可以通过旋转得到另一个。
把环看作 [0,1,\dots,n-1] 这个数组的一个循环位移。显然循环位移有 n 种，我们定义 g_k=[n-k,\dots, n-1,0,\dots, n-k-1]，即循环位移 k 次的结果。定义 g_a * g_b = g_{(a+b)\bmod n}（也可以看作置换的复合，即 (a * b)_i = a_{b_i}），这样我们就得到了一个群 G = (\{g_0 \dots g_{n-1}\},*)。
然后定义 X。对于 x \in X，x 就是一种 n 个数的染色方案。即 x 也是一个长度为 n 的数组，且 x_{i} \in [1,n] 表示每个位置的的颜色。定义 g_k \cdot x 表示将 x 这个染色方案，循环位移 k 位后的状态。
> 解释一下。对于一个位置 $i$，它要满足 $x_i = x_{i+k} = x_{i+2k} = \dots x_i$（下标都在模 $n$ 意义下）。设这条链的长度是 $p$，则 $n \mid pk$。显然最小的 $p=\dfrac n{\gcd(n,k)}$。因此总共有 $\dfrac n{n / \gcd(n,k)} = \gcd(n,k)$ 条链。一条链上颜色必须相同，即都是 $[1,n]$ 中的一种，因此答案为 $n^{\gcd(n,k)}$。
那么就可以套 Burnside 引理的式子了：
$$
ans = t = \dfrac 1{|G|} \sum_{g \in G} |Fix(g)| = \dfrac 1n \sum_{k=0}^{n-1} n^{\gcd(n,k)}
$$
然后就是数论问题了，就不提了。
可以发现，我们目前只用到了 Burnside 引理，就解决了 Polya 定理的模板题。事实上，Polya 定理（准确来说，是无权重版本）是 Burnside 引理的一个简单推论。
模板题中，$g \in G$ 本质上是一个排列。而 $\gcd(n,k)$ 指的是，对于 $g$ 这个排列，连出 $n$ 条有向边 $i \to g_i$ 后，图上的环的数量。一个环上的点颜色必须相同，所以得到 $|Fix(g_k)| = n^{\gcd(n,k)}$。这里并没有用到“循环移位”本身的性质。那么如果 $g$ 不是本题中的特殊形式，我们依然可以定义 $c(g)$ 表示用 $g$ 生成的图上的环的数量，$|Fix(g)| = m^{c(g)}$ 依然成立。这样就得到了 Polya 定理：
$$
t = \dfrac 1{|G|} \sum_{g \in G} m^{c(g)}
$$
（其实一般 Burnside 引理用的比较多。）
## 例题
> **P4128 [SHOI2006] 有色图**
>
> $n$ 个点的完全图。你要给每条边染色 $1 \sim k$。定义两个染色方案本质相同，当且仅当存在点编号的置换使得两个染色方案完全相同。求有多少本质不同的染色方案。
>
> $n \le 53$。
考虑 Burnside 引理。显然这里 $g \in G$ 就是一个 $1\sim n$ 的排列。先暴力枚举这个排列 $g$，并尝试计算不动点个数。
建一张新图，由 $i$ 指向 $g_i$。显然图上会形成若干环。分别考察，两点在同一个环上的边，以及两点在不同环上的边的颜色。
比如有一个环 $0 \to 1 \to \dots \to n-1 \to 0$。由于要保证点的编号置换一次后边的颜色不变，因此边 $(0,i),(1,i+1),(2,i+2)\dots$ 的颜色应当相同（点编号需要对 $n$ 取模）。所有的边可以根据这个划分成 $\lfloor n/2 \rfloor$ 组。因此方案数为 $k^{\lfloor n/2 \rfloor}$。
再考虑环与环之间的边。比如有两个环 $0 \to 1 \to \dots \to n-1 \to 0$ 和 $0 \to 1 \to \dots \to m-1 \to 0$。同样的，我们需要保证，边 $(0,i),(1,i+1),\dots$ 的颜色都应相同（第一个点对 $n$ 取模，第二个点对 $m$ 取模）。注意到，当 $k \equiv 0 \pmod n,i+k \equiv i \pmod m$ 时，$k$ 的最小值为 $\operatorname{lcm}(n,m)$。也就是说一圈的长度是 $\operatorname{lcm}(n,m)$。因此一共有 $\dfrac{nm}{\operatorname{lcm}(n,m)} = \gcd(n,m)$ 组，每组颜色应当相同。因此方案数为 $k^{\gcd(n,m)}$。
所以如果整张图上所有环的大小分别为 $a_1,a_2\dots a_n$，答案为：
$$
\sum_i \lfloor a_i / 2 \rfloor + \sum_{i<j} \gcd(a_i,a_j)
$$
$k$ 的这么多次方。
注意到 $n$ 很小。于是直接枚举所有 $a$，复杂度是 $n$ 的分拆数，可过。