Burnside 和 Polya 入门

· · 算法·理论

抽象代数前置

【Burnside 引理】

问题引入

涂色 2\times 2 的方格。旋转相同算一种。有多少种本质不同染色方案？

可以数出有 6 种。

以此为例介绍 Burnside 引理。

设一种染色方案为 x，g_{a} 为一种变换，表示将某种染色方案顺时针旋转 a 度，则 "旋转相同" 就是 x^{(g_0,g_{90},g_{180},g_{270})} 算同一种。

考虑：

Burnside 引理告诉我们，本质不同的方案数即这四种情况的平均数，\dfrac{16+2+4+2}{4}=6。

数学定义

令 X 为着色方案的集合，G 为一个作用在 X 上的变换群。

定义 X^{(g)}=\{x|x\cdot g=x,x\in X\}。即对于 g，找所有被 g 作用后不变的 x。

Burnside 引理结论：|X/G|=\dfrac{1}{|G|}\sum_{g\in G}|X^{(g)}|。

（X/G 表示 G 作用在 X 上后的等价类个数，在群论中 "等价类" 也称作 "轨道 (orbit)"）

证明

需要一些前置定理。

Lagrange 定理

设 H 是 G 的子群。\{aH|a\in G\} 会成为 G 的划分。 （\{aH|a\in G\} 是 "陪集"，a 这个元素对 H 里每个元素运算得到的集合）

Lagrange 定理：[G:H]=|G|/|H|。（[G:H] 表示 \{aH|a\in G\}，即陪集的集合）

即 |G|=[G:H]\cdot |H|。

Burnside 证明

定义 O_x=\{x'|\exists g\in G,g\cdot x=x',x'\in X\}=\{gx|g\in G\}。理解 x 为一种着色方案，O_x 即 x 所在的轨道。

定义 G_x=\{g|g\in G,g\cdot x=x\}。即 x 的稳定化子，就是作用到 x 后不变。注意分辨 X^{(g)} 与 G_x。

观察 1：G_x 是 G 的子群。

证明 H 是 G 子群的思路：① 证明 a,b\in H\Rightarrow ab\in H。 ② a\in H\Rightarrow a^{-1}\in H。

证明 1：

证毕。

观察 2：O_x 与 G_x 的所有陪集形成一一映射。

（轨道元素个数与稳定化子陪集构成一一映射）

证明 2：

理清定义。（下面变换作用在状态上用 \cdot，变换复合用 *）

$S=G_x$ 所有陪集 $=\{aG_x|a\in G\}$。 然后开始证明。来一个引理： **引理**：任取一个 $f$ 使得 $f\cdot x=x_i$，有 $fG_x=G_i=\{g|g\in G,g(x)=x_i\}$。 **引理证明**： 反证法。假设 $fG_x\neq G_i$。因为 $f\cdot x=x_i$，而 $\forall f'\in G_x$，都有 $f'\cdot x=x$，所以 $(f\cdot f')\cdot x=f\cdot (f'\cdot x)=f\cdot x=x_i$。所以 $fG_x\subseteq G_i$。 又因为 $fG_x\neq G_i$，所以一定有 $|fG_x|<|G_i|$。根据子群与陪集的性质，$|fG_x|=|G_x|$，所以 $|G_x|<|G_i|$。 但是考虑逆变换 $f_*$ 使得 $f_*\cdot x_i=x$，陪集 $f_*G_i$ 其实就是 $G_x$（变换一次又逆变换回去了）。所以 $|f_*G_i|=|G_x|$。根据子群与陪集的性质，$|G_i|=|f_*G_i|$。 于是有 $|G_i|>|G_x|=|f_*G_i|=|G_i|$，矛盾，反设不成立。引理得证。 --- 下面开始正式证明。 对于每个 $x_i\in O_x$，根据 $O_x$ 的定义，存在某个 $f_i\in G$ 使 $f_i\cdot x=x_i$。 我们任取某个 $f_i$，并记 $f_i$ 与 $G_x$ 构成的陪集为 $P_i=\{f_i\cdot f|f\in G_x\}$。 于是我们把 $O_x$ 映射到 $|O_x|$ 个陪集 $P_i$。我们会说明这些 $P_i$ 构成的集合等于 $S$。 反设有 $f_*\in G$，使得 $f_*G_x$ 不等于任何一个 $P_i$。 设 $f_*(x)=x_p$。根据引理，$P_p$ 包含了所有 $f(x)=x_p$ 的 $f$，矛盾。所以 $\{P_i\}=S$，得证。 ### 推论： 根据拉格朗日定理有 $|G|=|O_x|\cdot |G_x|$。 ### 正式证明： $$\begin{aligned} \sum_{g\in G}|X^{(g)}|&=|\{(g,x)|g\cdot x=x\}|\\ &=\sum_{x\in X}|G_x|=\sum_{x\in X}\dfrac{|G|}{|O_x|}\\ \end{aligned} \Rightarrow \dfrac{1}{|G|}\sum_{g\in G}|X^{(g)}|=\sum_{x\in X}\dfrac{1}{|O_x|} $$ 而 $\sum_{x\in X}\dfrac{1}{|O_x|}$ 其实就是 $X/G$ 的轨道数。因为一个轨道里每一个数贡献轨道大小的倒数，所以一个轨道贡献 $1$。 # 【Polya 定理】 考虑 $|X^{(g)}|$ 有没有其他的计算方式。 考虑 $g180$ 对 $2\times 2$ 的作用： $$ \begin{bmatrix} a&b\\ c&d \end{bmatrix}\Rightarrow \begin{bmatrix} d&c\\ b&a \end{bmatrix} $$ 我们发现，这可以视作两个轮换：$(a,d),(b,c)$。所以问题转化为：给 $a,b,c,d$ 着色，同一轮换里同色的方案数。 记 $k$ 为颜色数，$A$ 为所有格子的集合。记 $C_A(g)$ 为把 $g$ 看作置换，$A$ 会形成的轮换数。 有：$|X^{(g)}|=k^{C_A(g)}$。 ## Polya 定理 $|X/G|=\dfrac{1}{|G|}\sum_{g\in G}k^{C_A(g)}$。 根据 Burnside 引理，$|X/G|=\dfrac{1}{|G|}\sum_{g\in G}|X^{(g)}|$，而 $|X^{(g)}|=k^{C_A(g)}$，所以 Polya 定理成立。 ## 区分 Burnside 引理是 $g$ 作用在 $X$ 上（着色方案），Polya 定理是 $g$ 作用在 $A$ 上（格子）。 # 【题目】 ## 【[P4980：项链计数](https://www.luogu.com.cn/problem/P4980)】 > $n$ 个珠子一串，$k$ 种颜色。旋转相同。求本质不同的着色方案数 $T_{n,k}$。 这个问题有很多拓展，例如每种颜色只能用一次、禁止循环节等。 结论：$T_{n,k}=\dfrac{1}{n}\sum_{d|n}\varphi(d)k^{n/d}$。 考虑 Polya 定理。 $A=\{1,2,\dots,n\}$，$G=\{g_1,\dots,g_n\}$。 根据 Polya 定理，答案为： $$ \dfrac{1}{|G|}\sum_{g\in G}k^{C_A(g)}=\dfrac{1}{|G|}\sum_{i=1}^{n}k^{C_A(g_{i})} $$ 考虑 $C_A(g_i)$ 是多少。记 $p=gcd(i,n)$，则 $i\bmod p$ 相等的在同一个轮换里，所以 $C_A(g_i)=p$。 $$\begin{aligned} &=\dfrac{1}{|G|}\sum_{i=1}^{n}k^{gcd(i,n)}\\ &=\dfrac{1}{|G|}\sum_{d|n}k^d\cdot |\{i|1\le i\le n,gcd(i,n)=d\}|\\ &=\dfrac{1}{|G|}\sum_{d|n}k^d\cdot |\{j|1\le j\le n/d,gcd(j,n/d)=1\}|\\ &=\dfrac{1}{|G|}\sum_{d|n}k^d\cdot \varphi(n/d)\\ \end{aligned} $$ ## 【[P4916：魔力环](https://www.luogu.com.cn/problem/P4916)】 > $n$ 个珠子一串，黑白染色。要求恰好 $m$ 个黑色，且最长黑色段长度 $\le k$。旋转相同，求本质不同方案数。$n,m,k\le 10^5$。 这题有对染色方案的限制，不能用 Polya 定理，只能用 Burnside 引理。因为 Burnside 就是根据染色方案的。 首先，还是有 $G=\{g_1\sim g_n\}$。关键问题在于怎么求 $|X^{(g_i)}|$。 令 $(x_1\sim x_n)$ 表示一种着色方案。需要计数：$x$ 满足题目的要求且 $x$ 在 $g_i$ 下保持不变。 考虑 $x$ 在 $g_i$ 下保持不变是什么意思。令 $d=gcd(g_i,n)$，这个条件等价于 $x$ 以 $d$ 为周期。 于是只需要考虑 $x_1\sim x_d$ 的选法个数，使得里面有 $\dfrac{m}{d}$ 个 $1$，且展开后连续 $1$ 个数 $\le k$。 这个怎么做？这是一个组合计数问题。 首先理一下问题：求长度为 $n$ 的 $01$ 序列，$1$ 有 $a$ 个，$1$ 段长度 $\le k$，认为首尾相连。 先把 $0$ 排成一排，让 $1$ 插入空隙之中。环做不了，必须断环为链，枚举首尾的空隙一共有多少个 $1$。所以方案数可以写作 $\sum_{i=0}^{k}(i+1)Put(a-i,(n-a)-1,k)$。其中 $Put(a,b,k)$ 表示把 $a$ 个球放入 $b$ 个盒子，每个盒子个数 $\le k$ 的方案数。 有容量的放球问题本来只能指数做。但是这里因为每个盒子的上限都一样，所以容斥时对于 $|S|$ 相同的情况可以一起计数。 $Put(a,b,k)=\sum_{i=1}^{\min(a/k,b)}(-1)^i\binom{b}{i}\binom{a-ik+b-1}{b-1}$. ## 【图的同构计数（无标号图计数）】 > 求 $n$ 个点的无向简单图个数。如果能通过将点的编号做置换变成相同的，认为是相同的图。 先用数学语言描述一下变化。若存在置换 $P=(p_1,\dots,p_n)$ 使得 $(i,j)\in G\iff (p_i,p_j)\in G'$，则 $G$ 和 $G'$ 是同构的。 因为没有对置换的特殊限制，考虑 Polya 定理。 把一个图认为是完全图里的边黑白染色得到（黑表示选，白表示不选）。问题转化为一个边的黑白染色计数问题。 考虑如何描述 $A,G$。$A$ 是 $\binom{n}{2}$ 条边的集合，$G$ 是 $n!$ 个点的置换的集合。即 $A=\{e_{i,j}|i<j\}$，$G=\{\text{1 到 n 的所有排列}\}$。 （$g$ 作用到点上之后，$A$ 里的边的编号也要跟着变） 换句话说，$G$ 是 $\dfrac{n(n-1)}{2}$ 条边的对称群的 $n!$ 阶置换群。 问题在于如何求 $C_A(g)$。(注意 $A$ 是边的集合，所以轮换也是边的轮换) 因为 $g$ 是一个置换，相对复杂，先考虑对于 $g$ 的一个轮换内部的边会形成多少个轮换。 手玩一下，观察发现一个大小为 $t$ 的轮换内部的边会形成 $[\dfrac{t}{2}]$ 个轮换。 ![](https://img2024.cnblogs.com/blog/3387368/202412/3387368-20241205194534144-1331347834.png) 这是为什么呢？记两个点 $a,b$ 在轮换中的距离 $dis(a,b)$ 为轮换几次之后 $a$ 变成 $b$。记 $a+d$ 为 $a$ 在轮换上往后走 $d$ 步到的点 我们发现，对于一个固定的 $d$，所有两端距离为 $d$ 的边会形成一个轮换。也就是 $(a,a+d),(a+1,a+d+1),\dots,(a-1,a+d-1)$ 会形成轮换。这是比较显然的。 而 $d$ 有多少种取值？**注意不是 $t$ 种！** 因为 $d=x$ 和 $d=t-x$ 是相同的。所以 $d$ 有 $[\dfrac{t}{2}]$ 个取值，每个取值有一个轮换，所以一共有 $[\dfrac{t}{2}]$ 个。 再考虑轮换之间的边。设两个轮换为 $a_1\sim a_j,b_1\sim b_k$。 手玩一下，观察发现对于两个长度 $j,k$ 的轮换，它们之间会形成 $gcd(j,k)$ 个轮换。 具体证明：假设某条边 $(a_x,b_y)$ 在 $t$ 次之后回到本身，那么 $t\bmod j=0,t\bmod k=0$，最小的 $t$ 即是该轮换的长度，显然 $t=\mathrm{lcm}(j,k)$。这个长度和 $x,y$ 无关！而两轮换一共连了 $jk$ 条边，所以一共有 $jk/\mathrm{lcm}(j,k)=gcd(j,k)$ 个轮换。 那么：若 $g$ 作用在 $V$ 上的轮换长度分别为 $l_1,l_2,\dots,l_s$，那么 $C_A(g)=\sum_{i}[\dfrac{l_i}{2}]+\sum_{i<j}gcd(l_i,l_j)$。 如果暴力枚举 $g$，这复杂度就 $O(n!)$ 了；但是我们发现 $l_1\sim l_s$ 其实是 $n$ 的一个拆分，而 $\{l\}$ 相同的 $g$ 结果相同，所以只需要枚举 $n$ 的拆分，然后计算有多少个 $g$ 能对应到这个拆分即可。 那对于一个拆分，怎么计算有多少个置换，其轮换长度刚好是这个拆分？ $1\sim n$ 随便放有 $n!$ 种方案，长度为 $len$ 的轮换会贡献 $len!$ 次重复，所以分配每个元素进轮换里有 $\dfrac{n!}{\prod len!}$。 同时对于相同长度的轮换，它们的元素可以整体交换。设 $c_i$ 为 $i$ 长度的轮换个数，于是又有 $c_i!$ 次重复，再除以 $\prod c_i!$。 然后对于一个轮换内部，就是一个圆排列。 整理一下，对于一个拆分 $(l_1,l_2,\dots,l_k)$，其方案数为 $\dfrac{n!}{\prod l_i\prod c_i!}$。 # 【带权 Burnside 引理】 如果着色方案 $X$ 有权值呢？（**权值符合同轨道内权值相等的性质**） **带权 Burnside 引理**：$ans=\dfrac{1}{|G|}\sum_{g\in G}w(X^{(g)})$，其中 $w(X^{(g)})$ 表示 $\sum_{x\in X^{(g)}} w(x)$。 证明： $\sum_{g\in G}w(X^{(g)})=\sum_{g\in G}\sum_{x\in X^{(g)}}w(x)=\sum_{x}\sum_{g\in G_x}w(x)=\sum_{x}w(x)\cdot |G_x|$。 由拉格朗日定理，$|G_x|\cdot |O_x|=|G|$，所以 $\sum_{x}w(x)\cdot |G_x|=\sum_{x}w(x)\cdot \dfrac{|G|}{|O_x|}$。 所以 $\dfrac{1}{|G|}\sum_{g\in G}w(X^{(g)})=\dfrac{1}{|G|}\sum_{x}w(x)\cdot\dfrac{|G|}{|O_x|}=\sum_xw(x)\cdot \dfrac{1}{|O_x|}=\sum_x w(x)=ans$。 # 【带权 Polya 定理（两种形式）】 ## 形式 1 形式 1（积）：假设颜色 $c=1\sim k$ 有权重 $w_c$，着色方案 $x$ 的权重 $w(x)$ 为每个格子颜色权重的**积**。 **带权 Polya 定理 1**：所有本质不同方案的权重总和 $=\dfrac{1}{|G|}\sum_{g\in G}S_1^{l_1(g)}\cdots S_n^{l_n(g)}$。 这里 $S_j=\sum_{c}w(c)^{j}$，$l_j(g)$ 表示 $g$ 的轮换分解中，长度为 $j$ 的轮换个数。 证明： 可以先考虑当所有颜色权重 $=1$ 的时候。此时 $S_j=\sum_{c}1^j=k$，所以 $\sum_{g\in G}S_1^{l_1(g)}\cdots S_n^{l_n(g)}=\sum_{g\in G}k^{l_1(g)+l_2(g)+\cdots+l_n(g)}=\sum_{g\in G}k^{C_A(g)}$。发现这是退化到了无权 Polya 定理的版本。 然后是有权版本。考虑 $g\in G$，设有 $r$ 个轮换，记作 $A_1\sim A_r$。若 $A_1\sim A_r$ 分别着色为 $c_1\sim c_r$ 时，我们产生了一个着色方案 $x$，其权重 $w(x)=w(c_1)^{|A_1|}\cdots w(c_r)^{|A_r|}$。所以 $$\begin{aligned} \sum_{x\in X^{(g)}}w(x)&=\sum_{g\in G}\sum_{c_1,\dots,c_r\in [k]}w(c_1)^{|A_1|}\cdots w(c_r)^{|A_r|}\\ &=\sum_{g\in G}\prod_{i=1}^{r}(\sum_{j=1}^{k}w(j)^{|A_i|})\\ &=\sum_{g\in G}\prod_{j=1}^{n}(\sum_{i=1}^{k}w(i)^j)^{l_j(g)}\\ &=\sum_{g\in G}\prod_{j=1}^{n}S_j^{l_j(g)} \end{aligned}$$ ## 形式 2 形式 2（和）：假设颜色 $c=1\sim k$ 有价值 $v_c$，着色方案 $x$ 的价值 $v(x)$ 为每个格子颜色价值的**和**。 求价值为 $m$ 的轨道个数 $T_m$。（这个比总价值更强，如果求了这个，总价值就是 $\sum m\cdot T_m$） 定义 $w(x)=t^{v(x)}$。这里 $t$ 是一个自由变量/参数，我们使用关于 $t$ 的多项式来求解。 （为什么要这样做呢？因为 $v(x)$ 是求和的形式，而转化成 $t^{v(x)}$ 后求和就变成乘积了，可以套用形式一的做法） 目标：$[t^m]\sum_{x\in X}\dfrac{t^{v(x)}}{|O_x|}$。 $$\begin{aligned} [t^m]\sum_{x\in X}\dfrac{t^{v(x)}}{|O_x|}\\ &=\sum_{x\in X}\dfrac{w(x)}{|O_x|}=\text{所有方案 X 的 w 之和}\\ &=\dfrac{1}{|G|}\sum_{g\in G}\prod_{i=1}^{n}S_i^{l_1(g)}\text{（形式一的结论）}\\ \end{aligned}$$ 回顾一下，$S_j=\sum_{c}w(c)^j=\sum_{c}t^{v(c)\cdot j}$。 再引入 $f(t)=\sum_{i=0}^{+\infty}f_i\cdot t^i$，其中 $f_i$ 表示价值为 $i$ 的颜色个数。 那么 $S_j=\sum_{c}t^{v(c)\cdot j}=\sum_{i}f_i\cdot t^{i\cdot j}=\sum_{i}f_i(t^j)^i=f(t^j)$。 再把 $S_j$ 代回原式，则 $T_m=[t^m]\dfrac{1}{|G|}\sum_{g}\prod_{i=1}^{n}f(t^i)^{l_i(g)}$。 ## 形式 2 Ex 当每种颜色的价值不再是一个数，而是一个 $d$ 维向量 $\vec{v(x)}$，也能使用 Polya 定理。 定义 $\displaystyle f(t_1,t_2,\dots,t_d)=\sum_{i_1,\cdots,i_d}(\prod_{j=1}^{d}t_j^{i_j})\cdot f_{(i_1,i_2,\dots,i_d)}$。这里 $f_{(i_1,i_2,\dots,i_d)}$ 表示价值为 $(i_1,i_2,\dots,i_d)$ 的颜色个数。 有：$T_{(i_1,i_2,\dots,i_d)}=[t_1^{i_1}\cdots t_d^{i_d}]\dfrac{1}{|G|}\sum_{g\in G}\prod_{i=1}^{n} f(t_1^i,t_2^i,\dots,t_d^i)^{l_i(g)}$。 # 【题目】 ## 【强制颜色个数的项链计数】 > 有 $k$ 种颜色，求长为 $n$ 的项链个数，使得颜色 $i$ 恰好用 $n_i$ 次。 结论：$\displaystyle ans=\dfrac{1}{n}\sum_{d|gcd(n_1,\dots,n_k)}\varphi(d)\cdot\binom{\frac{n}{d}}{\prod_{i=1}^{k}\frac{n_i}{d}}$。