前言

我们先引入一些例子来介绍一下 Burnside 引理常见的应用。

考虑一个等边三角形玩具，要对其顶点用红蓝两种颜色进行染色。由乘法原理，如果不考虑其他条件染色方案数量为 23=82^3 = 8 种。但是，红 - 蓝 - 红 和 红 - 红 - 蓝 本质上对应的是同一种方案，后者可以由前者通过旋转得到。故本质上不同的染色方案一定小于 88 种（事实上只有 44 种）。应对这一类问题，仅靠传统的组合数学是非常难以应对的，而如果引入群论、置换群、置换群在集合上的作用等概念，再结合 Burnside 引理的话，就可以较好地解决这一类”求本质不同染色方案数“的问题。

另外，Burnside 引理也常被应用于化学上同分异构体种类的计数，大家感兴趣的话也可以了解一下~

本文大致分为三个部分：第一部分会首先对证明 Burnside 引理所需要的基本抽象代数知识进行介绍；第二部分会引入文章的主题 —— Burnside 引理和基础的 Pólya 计数法；最后会浅谈一下 Burnside 引理在算法竞赛中的几类常见题型。同时，本文某种程度上也可以作为之前在集训队内做过的讲座 浅谈置换群 的讲义。

另外，我的水平也有限，所以本文中的部分用语可能不太严谨…… 欢迎大家提出指正 QwQ。

群论基础

集合论基础

关系

关系 (relation) 指集合内部分元素之间的某种关联。比如整数构成的集合内元素间可以存在倍数关系，三角形构成的集合内元素间可以存在相似关系。

首先回顾集合 AA 和 BB 的 笛卡尔积 (Cartesian product) 定义：

A×B={(a,b)∣a∈A,b∈B} A \times B = \left\{ (a, b) \mid a \in A, b \in B \right\}

可见 A×BA \times B 后得到的是一个由二元组的集合，并且这些二元组的左部来自于集合 AA ，右部来自于集合 BB 。

接下来尝试相对严格地定义关系：对于集合 AA ，集合 A×AA \times A 的每个子集 RR 都叫做集合 AA 上的一个关系。如果 (a,b)∈R(a, b) \in R ，则称 aa 和 bb 有关系 RR ，记作 aRbaRb 。

等价关系

等价关系是一类特殊的关系。若集合 AA 上的关系 ∼\sim 满足如下条件：

  • 自反性：∀a∈A\forall a \in A ，a∼aa \sim a ；
  • 对称性：∀a,b∈A\forall a, b \in A ，若 a∼ba \sim b 则 b∼ab \sim a ；
  • 传递性：∀a,b∈A\forall a, b \in A ，若 a∼b, b∼ca \sim b, \ b \sim c ，则 a∼ca \sim c ；

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

前面提到的整除关系并不一定满足对称性、传递性，因此不属于等价关系；而三角形间的相似则满足全部 33 条性质，因此属于等价关系。

再举一个例子，定义关系 a∼b:=a≡b(mod7)a \sim b := a \equiv b \pmod 7 ，即若 aa 和 bb 除以 77 所得的余数相等则称 aa 和 bb 间存在关系 ∼\sim ，也可以很容易验证自反性、对称性、传递性。

等价类

发现等价关系可以对集合内的元素进行分类：

  • 依据三角形的相似关系可以对三角形集合进行分类，
  • 依据模 77 的余数可以把所有自然数分成 77 类。

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

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

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

注意到一个元素似乎只可能属于一个等价类，而不能同时存在于多个等价类内。这也就使得，不同等价类之间的交集必然为空集。

性质：若 a,b∈Aa, b \in A 且 [a]∩[b]≠∅[a] \cap [b] \neq \emptyset ，则 [a]=[b][a] = [b] 。

运用反证法可以证明这一性质：

  • 假设存在 [a]≠[b][a] \neq [b] 且 [a]∩[b]≠∅[a] \cap [b] \neq \emptyset ；
  • 令 k1∈[a]k_1 \in [a] 且 k1∉[b]k_1 \notin [b] ，k2∈[a]∩[b]k_2 \in [a] \cap [b] ；
  • 则有 k1∼a, k2∼a, k2∼bk_1 \sim a, \ k_2 \sim a, \ k_2 \sim b ；
  • 由传递性得 k1∼bk_1 \sim b ，与假设不符。

这启示我们：

  • 集合 AA 可看作一些两两不相交的等价类的并：

    A=⋃a∈R[a]（两两不相交之并） A = \bigcup\limits_{a \in R} [a] \text{（两两不相交之并）}

    其中，式子里的 RR 称之为完全代表系，由等价类 [ai][a_i] 中选出一个元素构成，使得 AA 中每个元素都与 RR 中的某个元素等价，同时 RR 中的元素彼此不等价。

  • AA 上的每个等价关系给出集合 AA 的一个划分 (partition)。

    划分的定义：若 AA 是它的某些子集 {Ai∣i∈I}\{ A_i | i \in I \} 之并，且 AiA_i 两两不交，则称其为集合 AA 的一个划分（或分拆）。

引入等价类的意义就是为了对集合中的元素进行分类。后面要介绍的轨道、陪集等本质上都是基于等价关系的。

群论基础

群

设 GG 是非空集合，且二元运算 ⋅\cdot 满足：

  • 结合律：(a⋅b)⋅c=a⋅(b⋅c)(a \cdot b) \cdot c = a \cdot (b \cdot c)
  • 单位元 ee ：∀a∈G, ea=ae=a\forall a \in G, \ ea = ae = a
  • 逆元：∀a∈G, ∃b∈G  s.t.  ab=ba=e\forall a \in G, \ \exist b \in G \text{ \ s.t. \ } ab = ba = e

则称 (G,⋅)(G, \cdot) 是一个群 (group)，有时也简写成 GG 。

需要注意的是，群并不要求运算满足交换律。如果运算满足交换律，称这样的群为阿贝尔群 (Abelian group)，或交换群。另外，若群 GG 的大小有限，则成其为有限群 (finite group)。

例如在集合 Z7=[0,1,2,3,4,5,6]\mathbb{Z}_7 = [0, 1, 2, 3, 4, 5, 6] 上定义模 77 加法，即 a+b:=(a+b) mod 7a + b := (a + b) \bmod 7 。我们来验证一下 (Z7,+)(\mathbb{Z}_7, +) 是否成群：

  • 结合律：(a+b)+c=a+(b+c)(a + b) + c = a + (b + c) ；
  • 单位元 e=0e = 0 ：0+a=a+0=a0 + a = a + 0 = a ；
  • 逆元：对于 aa ，其逆元 a−1=(7−a) mod 7a^{-1} = (7 - a) \bmod 7 ；

所以 (Z7,+)(\mathbb{Z}_7, +) 成群。

群有两条非常重要的性质：

  • 左右逆元相等：

    设 xx 是 aa 的左逆元，yy 是 aa 的右逆元，有：

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

  • 满足消去律：

    ∀a,b,c∈G, ab=ac⇔b=c \forall a, b, c \in G, \ ab = ac \Leftrightarrow b = c

    可见，只要逆元存在就存在消去律。

子群

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

陪集

前面提到可以通过等价类来对集合进行划分，而现在我们需要找到一种东西来对群进行划分。基于此引入陪集这一概念。

设 H≤GH \leq G ，对于 x∈Gx \in G ：

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

由于左陪集和右陪集性质上相似，故后文只讨论左陪集。对于右陪集，请读者自行尝试~

对于 x,y∈Gx, y \in G ，定义如下关系 ∼\sim ：

x∼y:=x∈yH x \sim y := x \in yH

发现这其实是一个等价关系：

  • 自反性：x∈xHx \in xH ；
    • 既然 HH 是群，则 e∈He \in H ，故 x⋅e=x∈xHx \cdot e = x \in xH
  • 对称性：若 y∈xHy \in xH ，则 x∈yHx \in yH ；
    • y∈xH⇒∃h∈H  s.t.  y=x⋅hy \in xH \Rightarrow \exist h \in H \text{ \ s.t. \ } y = x \cdot h
    • HH 中逆元存在，则 ∃h∈H,  s.t.  x=y⋅h−1\exists h \in H, \ \text{ s.t. } \ x = y \cdot h^{-1}
    • 由 h−1∈Hh^{-1} \in H ，故 x∈yHx \in yH
  • 传递性：若 z∈yH, y∈xHz \in yH, \ y \in xH ，则 z∈xHz \in xH 。
    • z∈yH⇒∃h1∈H  s.t.  y=z⋅h1z \in yH \Rightarrow \exist h_1 \in H \text{ \ s.t. \ } y = z \cdot h_1
    • y∈xH⇒∃h2∈H  s.t.  x=y⋅h2y \in xH \Rightarrow \exist h_2 \in H \text{ \ s.t. \ } x = y \cdot h_2
    • 令 h=h1h2h = h_1h_2 ，则 x=z⋅hx = z \cdot h 且 h∈Hh \in H ，故 z∈xHz \in xH

故直接将讨论等价类时得出的结论搬到此处：

  • 若 xH∩yH≠∅xH \cap yH \neq \emptyset ，则 xH=yHxH = yH ；

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

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

    这里展现了对群 GG 的左陪集分解。与之前类似， RR 称作 GG 对 HH 左陪集的代表元系。RR 由 GG 中的元素构成，并且这些用元素生成的左陪集彼此互不相同，与此同时这些左陪集的并集恰好为 GG 。

拉格朗日定理

对于群 H≤GH \leq G （两者均为有限群），∀a,b∈H,g∈G\forall a, b \in H, g \in G ，由消去律：

a≠b⇔ga≠gb a \neq b \Leftrightarrow ga \neq gb

这启示我们，∀g∈G\forall g \in G ，gHgH 内的元素其实和 HH 内的元素是一一对应的。因为 HH 内不同的元素左乘 gg 后并不会变得相等。因此两者大小也是相等的： ∣H∣=∣gH∣|H| = |gH| 。

这也意味着群 GG 对子群 HH 的所有陪集的大小都是相等的，并且都等于 ∣H∣|H| 。

记 RR 为 HH 的左陪集代表元系，有：

∣G∣=∑g∈R∣gH∣=∑g∈R∣H∣=∣R∣⋅∣H∣ \begin{aligned} |G| & = \sum\limits_{g \in R} |gH| \\ & = \sum\limits_{g \in R} |H| \\ & = |R| \cdot |H| \end{aligned}

若把 HH 的左陪集代表元系的大小 ∣R∣|R| 称作群 HH 对于群 GG 的指数 (index) 并记作 [G:H][G : H] ，便得到抽象代数里的拉格朗日定理 (Lagrange’s Theorem)：

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

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

置换、置换群

置换

一个集合的置换 (permutation) 即从该集合映射至自身的双射。

例如，对于 [1,2,…n][1, 2, \dots n] 的置换 σ\sigma 可记作：

σ=(12…nσ(1)σ(2)…σ(n)) \sigma = \left(\begin{array}{cccc} 1 & 2 & \dots & n \\ \sigma(1) & \sigma(2) & \dots & \sigma(n) \end{array}\right)

其含义为，置换将 11 变成 σ(1)\sigma(1) ，22 变成 σ(2)\sigma(2) …… 依此类推。

置换之间存在复合运算： (f∘g)(x)=f(g(x))(f \circ g)(x) = f(g(x)) ，后文中时常简写为 f∘gf \circ g ，有时也称其为置换间的乘法。

举一个例子：

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

试着写出其对应的“映射关系链”：

1→4→32→5→6 \begin{aligned} 1 & \rightarrow 4 \rightarrow 3 \\ 2 & \rightarrow 5 \rightarrow 6 \end{aligned}

任何一个置换都能被划分成若干不交的映射链吗？如果可以的话，这就意味着我们发现了一种能够更简单表示置换的方式 —— 以“映射链”相乘的形式表示置换（也就是马上会讲到的轮换表示法）。

轮换表示法

(a1a2…ana2a3…a1)⇒记作(a1a2…an) \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)

借助轮换表示法来表示刚才的例子：

(123456451362)=(143)⋅(256) \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)

这令人联想到对于整数的质因数分解…… 那么若不计轮换内的次序（即 (a,b,c)(a, b, c) 和 (b,c,a)(b, c, a) 当作相同置换）以及轮换间的次序（即 (a,b,c)⋅(d,e,f)(a, b, c) \cdot (d, e, f) 与 (d,e,f)⋅(a,b,c)(d, e, f) \cdot (a, b, c) 当作相同分解方案），对于任意置换的不交轮换分解是唯一的吗？

Hmm… 显然是唯一的。下面给出一个构造性的说明：

  • 对于恒等置换，显然分解是唯一的；
  • 对于非恒等置换，∃i  s.t.  σ(i)≠i\exist i \text{ \ s.t. \ } \sigma(i) \neq i 。
    • i→σ(i)→σ2(i)→…i \rightarrow \sigma(i) \rightarrow \sigma^2(i) \rightarrow \dots
    • 由抽屉原理，∃t1<t2  s.t.  σt1(i)=σt2(i)\exist t_1 < t_2 \text{ \ s.t. \ } \sigma^{t_1}(i) = \sigma^{t_2}(i)
    • 令 tt 为使得 σt(i)=i\sigma^t(i) = i 的最小正整数，则： (iσ(i)…σt−1(i)) (i \enspace \sigma(i) \enspace \dots \enspace \sigma^{t - 1}(i)) 是一个轮换。
  • 对于每个这样的 ii 都如此操作即可构造出一个唯一的不相交轮换分解式：
    • 每个元素在分解式中恰好出现 11 次；
    • 每个元素所属于的轮换是固定的。

置换的幂运算

下面讨论如何快速得到置换 σ\sigma 的 tt 次幂 σt\sigma^t ，即与先后作用 tt 次 σ\sigma 置换等价的置换。举几个例子：

(123456)2=(135)⋅(246)(123456)3=(14)⋅(25)⋅(36)(123456)4=(153)⋅(264) \begin{aligned} (1 \enspace 2 \enspace 3 \enspace 4 \enspace 5 \enspace 6)^2 & = (1 \enspace 3 \enspace 5) \cdot (2 \enspace 4 \enspace 6) \\ (1 \enspace 2 \enspace 3 \enspace 4 \enspace 5 \enspace 6)^3 & = (1 \enspace 4) \cdot (2 \enspace 5) \cdot (3 \enspace 6) \\ (1 \enspace 2 \enspace 3 \enspace 4 \enspace 5 \enspace 6)^4 & = (1 \enspace 5 \enspace 3) \cdot (2 \enspace 6 \enspace 4) \end{aligned}

直接考虑置换的幂并不方便，但由于置换可被分解成若干不相交轮换，不妨先看简单一些的情形：求一个轮换的幂次。

σ=(a0a1…an−1) \sigma = (a_0 \enspace a_1 \enspace \dots \enspace a_{n - 1})

首先根据轮换的定义，不难发现：

σt(ai)=a[(i+t) mod n] \sigma^t(a_i) = a_{[(i + t) \bmod n]}

接下来看看 σt\sigma^t 中 aia_i 所在的轮换大小，实际上也就是 aia_i 所在“映射链”的长度。只需要求得最小正整数的 kk ，使得 σ\sigma 作用于 aia_i kk 次后能够回到 aia_i （也就是找到周期），就能够知道其所在的映射链的长度了。

令 k∈N∗  s.t.  σtk(ai)=aik \in N^{*} \text{ \ s.t. \ } \sigma^{tk}(a_i) = a_i ：

i+tk≡i(modn)⇒tk≡0(modn) \begin{aligned} & i + tk \equiv i \pmod n \\ & \Rightarrow tk \equiv 0 \pmod n \end{aligned}

最小正整数解：k=ngcd⁡(n,t)k = \frac{n}{\gcd(n, t)}

这意味着 σt\sigma^t 可表示为 gcd⁡(n,t)\gcd(n, t) 个长为 ngcd⁡(n,t)\frac{n}{\gcd(n, t)} 的轮换。

另外注意到 aia_i 所在轮换里第 j (0≤j<gcd⁡(n,t))j \ (0 \le j < \gcd(n, t) ) 个元素为 a(i+jt) mod na_{(i + jt) \bmod n} 。由于 i+jt≡i(modt)i + jt \equiv i \pmod t 且 gcd⁡(n,t)∣t\gcd(n, t) \mid t ，有 i+jt≡i(modgcd⁡(n,t))i + jt \equiv i \pmod {\gcd(n, t)} 。这意味着：

  • aia_i 所在轮换内元素下标模 gcd⁡(n,t)\gcd(n, t) 均为 ii ；
  • a0,a1,…agcd⁡(n,t)−1a_0, a_1, \dots a_{\gcd(n, t) - 1} 一定位于不同轮换。

这些性质足以快速求得任一长度为 nn 的置换的幂次：

  • 将置换分解为轮换：O(n)\mathcal{O}(n) ；
  • 对轮换内的每一个元素应用上述性质以生成结果的轮换分解式：O(n)\mathcal{O}(n) ；
  • 还原成置换：O(n)\mathcal{O}(n) 。

置换群

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

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

群在集合上的作用

群在集合上作用是一个非常重要的概念。考虑如下映射 ϕ\phi ：

ϕ:G×M⟶M(σ,x)⟼σ∘x \begin{aligned} \phi: G \times M & \longrightarrow M \\ (\sigma, x) & \longmapsto \sigma \circ x \end{aligned}

若 ∀x∈M\forall x \in M 同时满足：

  • 单位元：∃ϵ∈G  s.t.  ϵ∘x=x\exist \epsilon \in G \text{ \ s.t. \ }\epsilon \circ x = x
  • 结合律：τ∘(σ∘x)=(τ∘σ)∘x\tau \circ (\sigma \circ x) = (\tau \circ \sigma) \circ x

则称群 GG 在集合 MM 上有群作用。

根据 Cayley 定理，每个群均同构于某个置换群。有了这个前提可能会更好理解群在集合上的作用。但是今天碍于主题，我们主要探讨置换群对于集合的作用。

为了更加清晰地介绍这一概念，再来看看本文开头所举的对等边三角形顶点染色的例子。

考虑置换群 GG 和集合 MM ：

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

首先来看看不考虑同构时的所有染色方案：

不考虑同构时的染色方案

再来看看 ϕ\phi 作用下得到的结果：

作用下得到的结果

可以看到，本质上 ϕ\phi 作用后是并没有产生新元素的。另外，存在单位置换（旋转 0∘0^\circ ）使得它与任何一个染色方案作用都不发生变化；多个旋转作用于染色方案也是满足结合律的。所以在这个例子里 GG 对 MM 有群作用。

另外，图中每一列其实都是一个等价类。发现实际上不同的等价类只有四种（第 2,3,42, 3, 4 列是相同的，第 5,6,75, 6, 7 列是相同的）。可见，在旋转群的作用下，本质不同的方案实际上只有 44 种。

等价类

轨道

我们把之前图中每一列都称作轨道。换言之，过 xx 的轨道就是将 GG 种每一个置换分别作用于 xx 得到的元素所组成的集合。由于群作用保证了不会产生新元素，因此这个集合是 MM 的子集。

群 GG 作用于集合 MM 上，x∈Mx \in M ，称 MM 的子集

orbG(x)={σ∘x∣σ∈G} \text{orb}_G(x) = \{ \sigma \circ x \mid \sigma \in G \}

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

在之前的例子中，我们发现每一个元素都是属于唯一轨道的。换句话说，借助轨道，我们可以对集合 MM 中的元素进行分类。那对于更一般的情况这也成立吗？为了验证这一点，不妨继续把之前讨论等价类的那一套理论搬过来：

定义如下关系 ∼\sim ：

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

只需要验证 ∼\sim 是一个等价关系即可。

  • 自反性： x∈orbG(x)x \in \text{orb}_G(x) ；
    • 恒等置换 ϵ∈G\epsilon \in G ，故 ϵ∘x=x∈orbG(x)\epsilon \circ x = x \in \text{orb}_G(x)
  • 对称性：若 y∈orbG(x)y \in \text{orb}_G(x) ，则 x∈orbG(y)x \in \text{orb}_G(y) ；
    • y∈orbG(x)⇒∃σ  s.t.  σ∘x=yy \in orb_G(x) \Rightarrow \exist \sigma \ \text{ s.t. } \ \sigma \circ x = y
    • GG 中逆元存在，故 ∃σ  s.t.  σ−1∘y=x\exist \sigma \ \text{ s.t. } \ \sigma^{-1} \circ y = x
    • 由 σ−1∈G\sigma^{-1} \in G ，故 x∈orbG(y)x \in \text{orb}_G(y)
  • 传递性：若 z∈orbG(y), y∈orbG(x)z \in \text{orb}_G(y), \ y \in \text{orb}_G(x) ，则 z∈orbG(x)z \in \text{orb}_G(x)
    • z∈orbG(y)⇒∃σ  s.t.  σ∘y=zz \in orb_G(y) \Rightarrow \exist \sigma \ \text{ s.t. } \ \sigma \circ y = z
    • y∈orbG(x)⇒∃τ  s.t.  τ∘x=yy \in orb_G(x) \Rightarrow \exist \tau \ \text{ s.t. } \ \tau \circ x = y
    • 令 β=σ∘τ\beta = \sigma \circ \tau ，则 β∘x=z\beta \circ x = z 且 β∈G\beta \in G ，故 z∈orbG(x)z \in \text{orb}_G(x)

Voilà! 这样一来，之前的那一套结论也可以搬过来了：

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

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

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

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

既然可用于分类，则更进一步：如果 GG 中两个不同的置换 σ,τ\sigma, \tau 作用于 xx 后的结果是相同的，可以认为 σ,τ\sigma, \tau 在仅考虑作用于 xx 时是两个等价的置换（试着验证一下这是等价关系？）。由此，∣orbG(x)∣| \text{orb}_G(x) | 实际上等价于仅考虑作用于 xx 时 GG 中本质不同的置换种数。

稳定子

另外发现元素 xx 可能在部分置换下所得到的结果依然是 xx 。将这些置换所组成的集合称作群 GG 作用下 xx 的稳定子。

设群 GG 作用于集合 MM ，对 x∈Mx \in M ，称

stabG(x)={σ∣σ∈G,σ∘x=x} \text{stab}_G(x) = \{ \sigma \mid \sigma \in G, \sigma \circ x = x \}

为群 GG 作用下 xx 的稳定子 (stabilizer)。

发现 stabG(x)\text{stab}_G(x) 其实是置换群 GG 的子群：

  • 封闭性：∀σ,τ∈stabG(x)\forall \sigma, \tau \in \text{stab}_G(x) ，σ∘τ∘x=σ∘x=x\sigma \circ \tau \circ x = \sigma \circ x = x ，故 (σ∘τ)∈stabG(x)(\sigma \circ \tau) \in \text{stab}_G(x) ；
  • 结合律：显然置换的复合满足结合律；
  • 单位元：恒等置换 ϵ∘x=x\epsilon \circ x = x ；
  • 逆元：∀σ∈stabG(x)\forall \sigma \in \text{stab}_G(x) ，σ−1∘x=σ−1∘(σ∘x)=ϵ(x)=x\sigma^{-1} \circ x = \sigma^{-1} \circ (\sigma \circ x) = \epsilon(x) = x 。

于是得到 stabG(x)≤G\text{stab}_G(x) \leq G 。

轨道-稳定子定理

联想之前的陪集划分，既然 stabG(x)≤G\text{stab}_G(x) \leq G ，是否也可用子群 stabG(x)\text{stab}_G(x) 对置换群 GG 进行左陪集划分？

∀β∈G, βstabG(x)\forall \beta \in G, \ \beta \text{stab}_G(x) 里的元素相当于作用于 xx 时 GG 中所有与 β\beta 等价的置换：

βstabG(x)={(β∘σ)∘x=β∘x∣σ∈G}let τ=β∘σ={τ∘x=β∘x∣τ∈G} \begin{aligned} \beta \text{stab}_G(x) & = \{ (\beta \circ \sigma) \circ x = \beta \circ x \mid \sigma \in G \} \\ & \text{let } \tau = \beta \circ \sigma \\ & = \{ \tau \circ x = \beta \circ x \mid \tau \in G \} \end{aligned}

由拉格朗日定理：

∣G∣=∣stabG(x)∣⋅[G:stabG(x)] |G| = |\text{stab}_G(x)| \cdot [G:\text{stab}_G(x)]

[G:stabG(x)][G:\text{stab}_G(x)] 实际上就是本质不同的陪集种数。回忆前文提到了∣orbG(x)∣| \text{orb}_G(x) | 实际上等价于仅考虑作用于 xx 时 GG 中本质不同的置换种数，因此：

[G:stabG(x)]=∣orbG(x)∣ [G:\text{stab}_G(x)] = |\text{orb}_G(x)|

便得到了轨道-稳定子定理 (oribt-stabilizer theorem)。

设有限群 GG 作用于集合 MM ，x∈Mx \in M ，则：

∣G∣=∣stabG(x)∣⋅∣orbG(x)∣ |G| = |\text{stab}_G(x)| \cdot |\text{orb}_G(x)|

Burnside 引理

内容

设有限群 GG 作用于有限集 MM 上，则轨道数：

∣M/G∣=1∣G∣∑σ∈G∣fix(σ)∣ | M/G | = \frac{1}{|G|} \sum\limits_{\sigma \in G} |\text{fix}(\sigma)|

其中 fix(σ)\text{fix}(\sigma) 代表 σ\sigma 的不动元构成的集合：

fix(σ)={x∣x∈M,σ∘x=x} \text{fix}(\sigma) = \{ x \mid x \in M, \sigma \circ x = x \}

证明

回顾：

stabG(x)={σ∣σ∈G,σ∘x=x}fix(σ)={x∣x∈M,σ∘x=x} \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}

首先有一个引理：

∑x∈M∣stabG(x)∣=∑σ∈G∣fix(σ)∣ \sum\limits_{x \in M} | \text{stab}_G(x) | = \sum\limits_{\sigma \in G} | \text{fix}(\sigma) |

发现等号左边实际上是对于集合 MM 内的每一个元素 xx ，看有多少置换 σ\sigma 满足 σ∘x=x\sigma \circ x = x ；而等号右边是对于群 GG 内每一个置换 σ\sigma ，看有多少元素 xx 满足 σ∘x=x\sigma \circ x = x 。换句话说，等号两边本质上都是求集合 {(σ,x)∣σ∈G,x∈M,σ∘x=x}\{ (\sigma, x) \mid \sigma \in G, x \in M, \sigma \circ x = x \} 的大小，因此是相等的。

接下来证明 Burnside 引理就很容易了：

每个轨道对轨道数贡献为 11 ，故 x∈Mx \in M 对答案的贡献为 1∣orbG(x)∣\frac{1}{| \text{orb}_G(x) |} ：

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

Pólya 计数法

Burnside 引理启示我们要求轨道数，本质上还是要看不动元的数量之和。进一步，考虑在没有额外限制的情况下，对于置换 σ\sigma 什么样的染色方案会称为不动元。

显然置换 σ\sigma 可以被分解成若干个轮换，如：

σ=(a0…at)⋅(b0…bs)⋅… \sigma = (a_0 \enspace \dots \enspace a_t) \cdot (b_0 \enspace \dots \enspace b_s) \cdot \dots

每一次置换作用时，每个轮换内的元素都会变成其右边的元素。故若要成为不动元，每个轮换内元素的颜色必然相同。这样一来，不动元数量之和其实就只与 σ\sigma 所能被分解成的轮换个数相关了。

记染色可选的颜色数为 mm ， c(σ)c(\sigma) 为置换 σ\sigma 被分解为不交轮换乘积的个数，则由乘法原理：

fix(σ)=mc(σ) \text{fix}(\sigma) = m^{c(\sigma)}

故：

∣M/G∣=1∣G∣∑σ∈Gmc(σ) | M/G | = \frac{1}{|G|} \sum\limits_{\sigma \in G} m^{c(\sigma)}

这就是算法竞赛中常见的 Pólya 计数法。

常见题型

Hmm… 感觉这一部分的当时幻灯片说的还是比较清楚的，这里就不额外补充了（犯懒qwq）……