【Burnside 引理】
问题引入
涂色 \(2\times 2\) 的方格。旋转相同算一种。有多少种本质不同染色方案？
可以数出有 \(6\) 种。
以此为例介绍 Burnside 引理。
设一种染色方案为 \(x\)，\(g_{a}\) 为一种变换，表示将某种染色方案顺时针旋转 \(a\) 度，则 "旋转相同" 就是 \(x^{(g_0,g_{90},g_{180},g_{270})}\) 算同一种。
考虑：
-
\(x^{g_0}=x\) 的有几种？有 \(16\) 种。
-
\(x^{g_{90}}=x\) 的有几种？有 \(2\) 种。
-
\(x^{g_{180}}=x\) 的有几种？有 \(4\) 种。
-
\(x^{g_{270}}=x\) 的有几种？有 \(2\) 种。
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\) 里每个元素运算得到的群）
所以有 \([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：
-
\(a,b\in G_x\)。由定义，\(a\cdot x=x,b\cdot x=x\)，而 \((ab)x=a(bx)=ax=x\)。所以 \(ab\in G_x\)。利用了群的结合律。
-
\(a\in G_x,ab=e\)（\(e\) 为单位元），即 \(b=a^{-1}\)。由定义 \(ax=x\)，则 \(b(ax)=bx,b(ax)=(ba)x=ex=x\)，所以 \(bx=x\)，所以 \(b\in G_x\)。
证毕。
观察 2：\(O_x\) 与 \(G_x\) 的陪集形成一一映射。
证明 2（待补）：
推论：
根据拉格朗日定理有 \(|G|=|O_x|\cdot |G_x|\)。因为 \(|O_x|=[G: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：项链计数】
\(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：魔力环】
\(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\) 里的边的编号也要跟着变。
问题在于如何求 \(C_A(g)\)。(注意 \(A\) 是边的集合，所以轮换也是边的轮换)
因为 \(g\) 是一个置换，相对复杂，先考虑对于 \(g\) 的一个轮换内部的边会形成多少个轮换。
手玩一下，观察发现一个大小为 \(t\) 的轮换内部的边会形成 \([\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=\lcm(j,k)\)。这个长度和 \(x,y\) 无关！而两轮换一共连了 \(jk\) 条边，所以一共有 \(jk/\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\) 能对应到这个拆分即可。
那对于一个拆分，怎么计算有多少个置换，其轮换长度刚好是这个拆分？答案就是 \(\dfrac{1}{2}\cdot \dfrac{n!}{\prod{l_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}}\)。
标签：cdot,dfrac,sum,Burnside,引理,Polya,轮换 From： https://www.cnblogs.com/FLY-lai/p/18584862