当前位置 : 主页 > 编程语言 > 其它开发 >

Burnside 引理 & Pólya 定理

来源:互联网 收集:自由互联 发布时间:2022-06-20
Burnside 引理 Pólya 定理 目录 Burnside 引理 Pólya 定理 群论相关知识 半群 群 群的性质总结 例子 子群 陪集 陪集定理 置换 置换群 Burnside 引理 Pólya 定理 轨道-稳定子定理 轨道 稳定子 Bur
Burnside 引理 & Pólya 定理

目录
  • Burnside 引理 & Pólya 定理
    • 群论相关知识
      • 半群
        • 群的性质总结
        • 例子
      • 子群
      • 陪集
        • 陪集定理
      • 置换
        • 置换群
      • Burnside 引理 & Pólya 定理
        • 轨道-稳定子定理
          • 轨道
          • 稳定子
        • Burnside 引理
        • Pólya 定理
    • 例题
      • 解答
      • 代码实现
    • 引用资料

Burnside 引理 & Pólya 定理能够用来解求本质不同的方案数这类问题。

考虑到定理的证明依赖于群论,而萌新可能对群论比较陌生,因此从群论相关知识讲起。

群论知识参考了许多资料(见本文引用资料),把本人认为简洁易于理解的讲解保留了下来,而对于一些理论。证明使用了自己的讲述方法/证法,如果发现不严谨或者笔误指出请指出 orz

写这份博客的时候电脑曾经停电丢失了数据,写到一半的进度没了,我厄厄。

群论相关知识 半群
  • 集合 \(S\)\(S\) 上满足结合律的二元运算 \(\cdot\) 所形成的代数结构叫做半群,记为 \((S, \cdot)\) 或者简记为 \(S\),运算 \(x \cdot y\) 常记为 \(xy\)。对于 \(x, y\in S\),有 \(xy \in S\)(即运算 \(\cdot\)\(S\) 上满足封闭性

    运算同时满足交换律的半群称为交换半群

  • \(\forall x\in S\) 均有 \(ex = xe = x\),称 \(e\)\(x\) 的幺元。

    幺元是唯一的:若 \(e'\) 也是幺元,有 \(e' = e'e = e\)

    具有幺元的半群称为含幺半群

  • 对于含幺半群 \(S\),元素 \(y\in S\) 叫做元素 \(x \in S\)逆元,是指 \(xy = yx = 1\)

    逆元是唯一的:若 \(y'\) 也是逆元,有 \(y' = y' \cdot 1 = y'xy = 1\cdot y = y\)。把这个唯一的逆元记作 \(x ^ {-1}\)

对于每个元素均有逆元含幺半群 \(G\) 称为

若运算又满足交换律,称 \(G\) 为交换群或阿贝尔(Abel)群。

\(G\) 的元素数 \(|G|\) 称为群的

个人认为,把群看成是具有一定约束并且支持运算 \(\cdot\)集合会比较容易理解相关内容。

群的性质总结

由上文所述,群满足性质:

  • 封闭性
  • (运算满足)结合律
  • 存在幺元
  • 每个元素均有逆元

当然,如果 \(G\)\(\cdot\) 下满足上述四个性质,那么称 \((G, \cdot)\) 为一个群。

例子

上面给了半群与群的定义,现举个例子:

对于自然数集 \(N\)\((N, +)\) 为含幺交换半群,幺元为 \(0\),不是的群的原因是 \(N\) 中非 \(0\) 的数均不存在逆元。

而整数集 \(Z\) 对于加法是交换群,因为对于 \(x\in Z\)\(-x\) 为对应的逆元,事实上,它被称为整数加法群

子群

\(H \subseteq G\) 且在 \((H, \cdot)\) 为群,称 \(H\)\(G\)子群,记为 \(H \leq G\)

验证子集 \(H\)\(G\) 的子群只需验证以下三点:

  • \(1_G \in H\)
  • \(h \in H\)\(h^{-1} \in H\)
  • \(a, b \in H \Rightarrow a \cdot b \in H\)
陪集

陪集是由任意固定的 \(g\in G\)\(G\) 子群 \(H\) 生成的集合,

其中左陪集为:\(gH = \{gh | h\in H\}\)

右陪集为:\(Hg = \{hg | h\in H\}\)

陪集的性质:

  • 陪集元素个数等于子群的阶,因为:(以左陪集为例:\(gh \ne gh' \Leftrightarrow h \ne h'\)
  • \(g\in H\),由封闭性易知,陪集为 \(H\) 本身。
陪集定理

对于 \(H\) 两个左(右)陪集,要么相等,要么交集为 \(\varnothing\)

证明:

如果陪集 \(gH, g'H\) 存在交集,假设交集的一个元素为 \(gh = g'h'\)\(h, h'\in H\)),

显然有 \(gh H = g'h' H\),因为 \(hH = h'H = H\),因此 \(gH = g'H\)

利用陪集定理,我们有分拆:\(G = \cup g_iH\),叫做 \(G\) 对子群 \(H\)左陪集分解

其中左陪集的个数记为 \([G:H]\),称为子群 \(H\) 对于 \(G\)指数

进而,我们显然有:设 \(G\) 为有限群,\(H\leq G\),则 \(|G| = |H|[G:H]\)。(拉格朗日(J.Lagrange) 定理

置换

集合 \(\Sigma\) 到自身每个一一对应 \(\sigma\) 叫做 \(\Sigma\) 上的一个置换。若 \(\Sigma\) 为有限集,此置换可表示为:

\[\sigma = \begin{pmatrix} a_1 & a_2 & \dots & a_n \\ \sigma(a_1) & \sigma(a_2) & \dots & \sigma(a_n) \\ \end{pmatrix} \]

\(\sigma\) 的逆可以表示为:

\[\sigma ^ {-1} = \begin{pmatrix} \sigma(a_1) & \sigma(a_2) & \dots & \sigma(a_n) \\ a_1 & a_2 & \dots & a_n \\ \end{pmatrix} \]

两个置换 \(\sigma, \tau\) 的乘积定义为 \(\Sigma \to \Sigma\) 映射的合成:\((\sigma \tau) (a_i) = \sigma(\tau(a_i))\),其中 \(i \in [1, n]\)

例如,

\[\begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 3 & 1 \\ \end{pmatrix} \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 4 & 2 \\ \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 2 & 4 & 3 \\ \end{pmatrix} \]

轮换(循环置换)是一类特殊的置换,表示为

\[\begin{pmatrix} a_1 & a_2 & \dots & a_{n-1} & a_n \\ a_2 & a_3 & \dots & a_n & a_1 \\ \end{pmatrix} \]

每个置换均可写成一些轮换的乘积(轮换的次序可随意写),使不同轮换中没有公共元素,长为 \(1\) 的置换往往略去不写,如:

\[\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 1 & 2 & 5 & 4 & 6 \\ \end{pmatrix} = (1, 3, 2)(4, 5) = (4, 5)(1, 3, 2) \]

置换群

上面已说明置换的乘积仍为置换,且存在逆元。而对于置换的幺元显然是恒等置换(简单来说就是 \(a_i \to a_i\))。

因此我们可以定义一个 \(S(\Sigma)\) 表示 \(\Sigma\) 上全体置换构成的集合,这是一个 \(n!\) 元群,叫做集合 \(\Sigma\) 上的对称群。

而它的每个子群都叫集合 \(\Sigma\) 上的置换群

Burnside 引理 & Pólya 定理

给定集合 \(X\)置换群 \(G\)

如果感觉到十分抽象的话,不妨代入下面的情境(意义)对下文的内容进行理解:

\(A\) 表示待染色物品集合

\(B\) 表示支持染的颜色的集合

\(X\) 表示染色方案集合

\(G\) 表示支持的变换。

\(X/G\) 表示本质不同的染色方案集合

\(X^g\) 表示经过一个变换 \(g\) 后保持不变的染色方案对应的集合

比如说:给你一串共 \(n\) 个珠子,支持旋转变换 \(G\)(可以看作是置换的一种)(这意味着如果两种染色方案在旋转后一样视为本质相同),每个珠子可以被染成 \(m\) 种颜色(也就是说方案集 \(X\) 的大小为 \(m ^ n\)),求本质不同的染色方案数(也就是 \(|X/G|\)

轨道-稳定子定理 轨道

\(\forall x\in X\), 称 \(G(x) = \{g(x) | g\in G\}\)\(x\)轨道

稳定子

\(\forall x\in X\),称 \(G ^ x = \{g | g(x) = x, g\in G \}\)\(x\)稳定子

\[|G| = |G ^ x||G(x)| \]

先证明 \(G^x\)\(G\)子群

  • 封闭性:对于 \(G^x\) 的元素 \(g, g'\),有 \((gg')(x) = x\),故 \(gg'\in G^x\)
  • 结合律:由置换乘法易知成立。
  • 存在幺元:也就是恒等置换 \(I\),显然在 \(G^x\) 中。
  • 每个元素均有逆元:\(g ^ {-1}(g(x)) = I(x) = x\),同时 \(g^{-1}(g(x)) = g^{-1}(x)\),故 \(g ^ {-1} \in G ^ x\)

拉格朗日定理,\(|G| = |G ^ x| [G: G^x]\)

故下面只需证 \([G: G^x] = |G(x)|\),也就是左陪集的个数等于 \(x\) 轨道的个数。

证明:

考虑证明存在 \(G(x)\)\(G^x\) 左陪集的一一映射

注意到对于每个 \(gG^x\),有 \(gG^x(x)\) 的元素均相同,这意味着每个左陪集 \(gG^x\) 能够对应一个 \(G(x)\) 的元素 \(g(x)\);而对于不同的左陪集 \(gG^x, g'G^x\),因为 \(g\ne g'\),因此必然满足相应的 \(g'(x) \ne g(x)\)

因此有 \(G(x)\)\(G^x\) 左陪集的一一映射关系。

Burnside 引理

\[\begin{aligned} \sum_{g\in G}|X^g| &= |\{(g,x) | (g,x)\in G\times X, g(x) = x\}| \\ &= \sum_{x\in X}|G^x| (前两行的意思其实就是从两个角度刻画满足 g(x) = x 的 (x, g) 对数)\\ &= \sum_{x\in X}\frac{|G|}{|G(x)|} ( 轨道-稳定子定理) \end{aligned} \]

下面结合实际意义进行推导:

对于本质相同的一组(染色方案)\(x\),它们的轨道数都是 \(G(x)\),因此有:

\[\begin{aligned} \sum_{x\in X}\frac{1}{|G(x)|} &= |X/G| \end{aligned} \]

故我们有 Burnside 引理

\[|X/G| = \frac{1}{|G|}\sum_{g\in G}|X^g| \]

这意味着,对于实际的计数问题,在给出变换的种类数 \(|G|\) 后,我们只需要求出染色方案在各种变换下保持不动的数量的和(即 \(\sum_{g\in G}|X^g|\)),那么我们就可以求出本质不同的染色方案数了。

Pólya 定理

考虑到 Burnside 引理需要求的 \(\sum_{g\in G}|X^g|\) 在实际统计中时间复杂度较高,而很多问题都是求解 \(A\to B\) 所有可能的映射(也就是比较特殊的 \(X\))所对应的染色方案(共 \(|B| ^ {|A|}\) 种)中本质不同的数量。

那么,在这样的问题中,可以使用 Pólya 定理

\[|X/G| = \frac{1}{|G|}\sum_{g\in G}|B|^{c(g)} \]

\(c(g)\) 表示置换 \(g\) 能拆分出的循环置换数。

证明:

注意到对于置换 \(g\),对于其拆分出的每个循环置换中的颜色必须相同,根据乘法原理,可知共有 \(|B | ^ {c(g)}\)

这意味着满足在 \(g\) 作用下保持不变的方案 \(x\) 数量 \(|X^g|\) 等于 \(|B| ^ {c(g)}\)

也就是 \(|B| ^ {c(g)} = |X ^ g|\),证毕。

例题

https://www.luogu.com.cn/problem/P4980

解答

考虑使用 Pólya 定理

只需统计对于每个置换 \(g\)\(c(g)\) 值即可。

而对于本题,置换的形式就是 \(k \in [0, n-1]\)循环移位,例如 \(n=4, k=2\)

\[g = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 4 & 1 & 2 \\ \end{pmatrix} \]

那么上例的 \(c(g)\) 值就是 \(2\)

现在的问题就是:给定 \(n, k\),求相应的 \(c(g)\) 值。

其实就是求给定大小为 \(n\) 的环,能拆分成多少个步长为 \(k\) 的环,比如上面的例子就是能拆成两个环:\((1, 3), (2, 4)\)

所以考虑求每个环的大小 \(size\)(容易发现每个环大小相等),那么 \(c(g) = \frac{n}{size}\)

\(size\) 是满足 \(n | tk\) 的最小的 \(t\),所以 \(size = \frac{n}{\gcd(n, k)}\)

现在,由上述推理以及 Pólya 定理,题目所求的答案 \(Ans\) 就是:

\[Ans = \frac{1}{|n|}\sum_{k=0}^{n-1} |n|^{\gcd(n, k)} \]

当然因为直接枚举的复杂度为 \(O(TN)\),会超时。

考虑根据 \(\gcd\) 的值对上述和式进行分块,可以从枚举 \(n\) 的因子 \(d\) 入手:

\[Ans = \frac{1}{|n|}\sum_{d|n} |n|^{d} \varphi(\frac{n}{d}) \]

复杂度为 \(O(T \cdot \sqrt N \cdot logN)\),可以通过。

代码实现
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int mod=1e9+7;

int fpow(int x, int p){
	int res=1;
	for(; p; p>>=1, x=x*x%mod) if(p&1) res=res*x%mod;
	return res;
}

int gcd(int a, int b){
	return b? gcd(b, a%b): a;
}

int inv(int x){
	return fpow(x, mod-2);
}

int phi(int x){
    int res=x;
    for(int i=2;i<=x/i;i++)
        if(x%i==0){
            res=res/i*(i-1);
            while(x%i==0) x/=i;
        }
    if(x>1) res=res/x*(x-1);

    return res;
}

signed main(){
	int T; cin>>T;
	while(T--){
		int n; cin>>n;
		int res=0;
		for(int i=1; i<=n/i; i++){
			if(n%i==0){
				res=(res+fpow(n, i)*phi(n/i)%mod)%mod;
				if(n/i!=i) res=(res+fpow(n, n/i)*phi(i)%mod)%mod;
			}
		}
		cout<<res*inv(n)%mod<<endl;
	}	
	return 0;
}
引用资料

https://cp-algorithms.com/combinatorics/burnside.html

https://zhuanlan.zhihu.com/p/294221308

https://oiwiki.com/math/permutation-group/

冯克勤,李尚志,章璞.近世代数引论[M].合肥:中国科学技术大学出版社,2018

上一篇:文件输入输出处理(三)-字符流
下一篇:没有了
网友评论