Burnside 引理学习笔记

在讲解 Burnside 引理之前,先要引入置换和群的概念。

置换

什么是置换?严格意义上定义,置换可以被认为是一个从自身映射到自身的双射函数。在组合数学中,通常指从 [ 1 , n ] [1,n] [1,n] 映射到 [ 1 , n ] [1,n] [1,n] 的双射函数。通俗的来说,就是将 1 − n 1-n 1−n 重新用 1 − n 1-n 1−n 的一个排列重新赋值。通常可以用以下的方式来表示一个置换:

( 1 2 3 4 5 3 1 2 5 4 ) \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 1 & 2 & 5 & 4\\ \end{pmatrix} (13​21​32​45​54​)

这里使用了一个特殊的五元置换。但是这种写法较为繁琐,通常我们会使用一个更加简单的方式来表示一个置换。考虑对每一个 ( i , a i ) (i,a_i) (i,ai​) 连边,然后跑一遍并查集,可以得到若干个等价类,即连通块。我们使用这些等价类来简洁的表示一个置换。例如,在上面的例子中,我们可以用 ( 1 , 2 , 3 ) ( 4 , 5 ) (1,2,3)(4,5) (1,2,3)(4,5) 来表示这个置换。显然,一个置换的等价类个数至多为 n n n,至少为 1 1 1。通常用 c 1 ( g ) c_1(g) c1​(g) 来表示置换 g g g 的等价类个数。

群是一个集合 G G G,包含一些元素和若干个运算,满足以下四条性质:

  1. 封闭性: ∀ g i , g j ∈ G \forall g_i,g_j \in G ∀gi​,gj​∈G,对于给定的运算 ⋅ \cdot ⋅,有 g i ⋅ g j ∈ G g_i\cdot g_j \in G gi​⋅gj​∈G。
  2. 结合律: ∀ g i , g j , g k ∈ G \forall g_i,g_j,g_k \in G ∀gi​,gj​,gk​∈G,对于所有的运算 f f f,有 ( g i ⋅ g j ) ⋅ g k = g i ⋅ ( g j ⋅ g k ) (g_i \cdot g_j) \cdot g_k=g_i \cdot (g_j \cdot g_k) (gi​⋅gj​)⋅gk​=gi​⋅(gj​⋅gk​)。
  3. 有单位元:对于运算 ⋅ \cdot ⋅, ∃ e ∈ G \exists e \in G ∃e∈G, ∀ g ∈ G \forall g \in G ∀g∈G, e ⋅ g = g ⋅ e = g e \cdot g = g \cdot e =g e⋅g=g⋅e=g。
  4. 有逆元:对于运算 ⋅ \cdot ⋅, ∀ f ∈ G \forall f \in G ∀f∈G, ∃ g ∈ G \exists g \in G ∃g∈G, f ⋅ g = g ⋅ f = e f\cdot g=g\cdot f=e f⋅g=g⋅f=e。

一个常见的例子就是模 k k k 意义下的 [ 0 , k − 1 ] [0,k-1] [0,k−1]。对于运算 + , × +,\times +,×,其中元素操作后依然还在这个集合中,满足封闭性;显然 + , × +,\times +,× 都具有结合律;对于 + + +,其单位元为 0 0 0,对于 × \times ×,其单位元为 1 1 1。对于 + + +,任意一个元素 a a a 的逆元为 ( k − a ) m o d    k (k-a) \mod k (k−a)modk;对于 × \times ×,任意一个元素的逆元为其乘法逆元。

置换群

置换群指的是一个由置换作为群元素的群。因而它一定具有一个单位元——即恒等变换, ∀ i ∈ [ 1 , n ] , e ( i ) = i \forall i \in [1,n],e(i)=i ∀i∈[1,n],e(i)=i。由逆元的存在,因而对于任意一个置换 g ∈ G g\in G g∈G, G G G 中一定存在一个反函数 g − 1 g^{-1} g−1,使得 g ⋯ g − 1 = e g \cdots g^{-1}=e g⋯g−1=e。由于函数的结合律因而满足了群对结合性的要求。

Burnside 引理

对于一个置换群 G G G,其等价类个数 L L L 满足以下关系式:

L = 1 ∣ G ∣ ∑ i = 1 s c 1 ( g i ) L=\frac{1}{|G|} \sum_{i=1}^{s} c_1(g_i) L=∣G∣1​i=1∑s​c1​(gi​)

其中 ∣ G ∣ = s |G|=s ∣G∣=s, c 1 ( g i ) c_1(g_i) c1​(gi​) 表示在 g i g_i gi​ 下等价类个数。感性认识这个式子,即是等价类个数等于各置换的平均等价类个数。此式还有另一种理解,即等价类个数等于总个数除以平均等价类大小,其具体证明基于这一思想。

“轨道大小 * 稳定化子数 = 变换个数”。轨道大小即经过这一置换群中所有置换的操作后, [ 1 , n ] [1,n] [1,n] 中任一元素 k k k 可以变化到的数的集合,记位 E k E_k Ek​。稳定化子数即为对于该元素 k k k,所有满足 f ( k ) = k f(k)=k f(k)=k 的置换 g g g 构成的集合 Z k Z_k Zk​。可以证明, ∣ E k ∣ ∣ Z k ∣ = ∣ G ∣ |E_k||Z_k|=|G| ∣Ek​∣∣Zk​∣=∣G∣。

但是在通常的实践中,我们通常不是将 [ 1 , n ] [1,n] [1,n] 的集合视为元素,而是将具体方案视为元素。因而,此式的另一种理解即为,总的去重方案数 t = 1 ∣ G ∣ ∑ i = 1 s D ( g i ) \displaystyle t=\frac{1}{|G|} \sum_{i=1}^{s} D(g_i) t=∣G∣1​i=1∑s​D(gi​),其中 D ( g i ) D(g_i) D(gi​) 表示在 g i g_i gi​ 置换下有多少种方案不变。

更特殊化的,我们会研究一种旋转等价类。设圆环长度为 n n n,在这种情况下, ∣ G ∣ = n |G|=n ∣G∣=n,其置换可以一般化的表示为:

g k = ( 1 2 3 ⋯ n − 1 n k k m o d    n + 1 ( k + 1 ) m o d    n + 1 ⋯ ( k + n − 2 ) m o d    n + 1 ( k + n − 1 ) m o d    n + 1 ) , g_k=\begin{pmatrix} 1 & 2 & 3 & \cdots & n-1 & n \\ k & k \mod n +1 & (k+1)\mod n+1 & \cdots & (k+n-2)\mod n+1 & (k+n-1)\mod n+1 \\ \end{pmatrix}, gk​=(1k​2kmodn+1​3(k+1)modn+1​⋯⋯​n−1(k+n−2)modn+1​n(k+n−1)modn+1​),

容易证明,在这种置换下,其等价类个数为 gcd ⁡ ( k − 1 , n ) \gcd(k-1,n) gcd(k−1,n),并且其等价类是按照模 n n n 的余数进行划分。记 f ( n ) f(n) f(n) 为长度为 n n n,不考虑任何重复条件的方案总数,那么对于一个置换 g k g_k gk​,其不变的方案总数为 f ( n gcd ⁡ ( k − 1 , n ) ) \displaystyle f(\frac{n}{\gcd(k-1,n)}) f(gcd(k−1,n)n​)——即,只有长度为 n gcd ⁡ ( k − 1 , n ) \displaystyle \frac{n}{\gcd(k-1,n)} gcd(k−1,n)n​ 的序列才在该置换下不变。套用 Burnside 引理可得,总的方案数为 ∑ k = 1 n f ( gcd ⁡ ( k − 1 , n ) ) \displaystyle \sum_{k=1}^{n} f({\gcd(k-1,n)}) k=1∑n​f(gcd(k−1,n))。

通常在处理这类问题的时候,不是枚举 k k k,而是枚举公约数 d d d,即 n n n 的因子。考虑公约数 d d d 对应的 f ( d ) f(d) f(d) 对答案的贡献次数。引入欧拉函数,容易证明,次数即为 φ ( n d ) \displaystyle \varphi(\frac{n}{d}) φ(dn​)。因而原式可以进一步化简为 ∑ d ∣ n φ ( n d ) f ( d ) \displaystyle \sum_{d|n} \varphi(\frac{n}{d}) f(d) d∣n∑​φ(dn​)f(d)。

接下来考虑另一个特殊化的问题:给定一个置换群 G G G,现有 n n n 个珠子要染成 m m m 种颜色,问方案总数。考虑每一个置换 g i g_i gi​,只有当同一个等价类中全部元素均染成同一种颜色时,才在该置换下不变。因而总的方案数为 L = 1 ∣ G ∣ ∑ i = 1 s m c 1 ( g i ) \displaystyle L=\frac{1}{|G|} \sum_{i=1}^{s} m^{c_1(g_i)} L=∣G∣1​i=1∑s​mc1​(gi​)。这就是 Polya 定理。

上一篇:F-Beta-Score


下一篇:Linux下awk理解