重修 Burnside & Pólya（Polya）

长长长文警告（可能只是公式多）。

可能不会讲 Polya。

P4980 【模板】Pólya 定理

本人の题解

本人几年前就跟着某数学老师学了这个，但是当时我还太年轻啊 qwq，所以来重修了。

以下是个人的见解。

让我们荡起双桨翻开《组合数学引论》Page 210，也就是说，默认你会了群论和置换。

这里我们用 OI 的语言来翻译：置换中的点就是每种状态（我们最终要求状态有多少种不同的等价类），置换群就是一些操作的集合，其中每种操作都会让状态转移（并且转移的形状是多个有向环），而且这些操作是传递闭包的。

下文设 \(D=\{1,\dots,n\}\)（相当于给 \(n\) 种状态标号），\(G\) 为作用在 \(D\) 上的置换群，两群间 \(A\le B\) 表示 \(A\) 是 \(B\) 的子群。

k-不动置换类

定义状态 \(k\) 的不动置换类

\[Z_k=\{\sigma\ |\ \sigma \in G,\sigma(k)=k\} \]

通俗地讲，就是让 \(k\) 这个状态不变（仍然是 \(k\)）的那些变换。

我们有

\[k\in D\implies Z_k\le G \]

等价类

定义 \(k\) 和 \(l\) 等价当

\[\exists\sigma\in G\ \text{s.t.}\ \sigma(k)=l \]

极大的一堆等价的就是等价类。

对了，一个置换左乘一个置换类为这个置换和置换类中每一个置换叠加构成的类，即

\[\sigma \Pi=\{\sigma \pi|\pi\in\Pi\} \]

右乘同理。

(A)

\[\color{blue}{ |\sigma\Pi|=|\Pi| }\]

假若 \(\sigma\pi_1=\sigma\pi_2\)，由于置换群有逆元（相当于在有向环上倒着走一步），得出 \(\sigma^{-1}\sigma\pi_1=\sigma^{-1}\sigma\pi_2\)，即 \(\pi_1=\pi_2\)。构成单射，得证。

下面我们考察一个状态 \(k\)，设 \(|E_k|=l,E_k=\{a_1(=k),a_2,\dots,a_l\}\)。

任意找 \(l\) 个置换（必然有，因为在等价类里）\(\{p_1,\dots,p_l\}\ \text{s.t}\ p_i(k)=a_i\)。

(B)

\[\color{blue}{ p_iZ_k\cap p_jZ_k=\emptyset\quad(i\ne j) }\]

\(p_iZ_k\) 中的任何元素都把 \(k(=a_1)\) 带到 \(a_i\)（\(Z_k\) 不让她动，\(p_i\) 把她带走），而同理 \(p_jZ_k\) 把 \(k\) 带到 \(a_j\)，你说咋可能有交呢对吧。

(C)

\[\color{blue}{ G=\cup_{i=1}^lp_iZ_k }\]

On the one hand:

\[p_iZ_k\in G\implies \cup_{i=1}^lp_iZ_k\in G \]

On the other hand:

任取 \(\pi\in G\) 我们只要证明她在某个 \(p_iZ_k\) 即可。

由于等价类的定义，设 \(\pi(k)=a_m(\in E)\)，并且

\[p_m^{-1}\pi(k)=p_m^{-1}(a_m)=k \]

所以

\[p_m^{-1}\pi\in Z_k \]

\[\pi\in p_mZ_k \]

原命题得证。

(D)

\[\color{blue}{ |E_k|\cdot|Z_k|=|G|\quad(k\in D) }\]

由 (A)(B)(C) 可以快速得到

\[\begin{aligned} |G|&=|p_1Z_k|+|p_2Z_k|+\dots+|p_lZ_k| \\&=l\cdot|Z_k| \\&=|E_k|\cdot|Z_k| \end{aligned}\]

(E)

\[\color{blue}{ |Z_k|=|Z_i|\quad(j\in E_i) }\]

由 (D)

\[|Z_k|=|Z_i|=\frac{|G|}{|E_k|} \]

快速证明。

当然有另一种方法：

由于 \(i,k\) 等价，所以存在 \(\pi(k)=i\)。

由 (A)（左乘右乘）：

\[|Z_k|=|\pi Z_k\pi^{-1}| \]

在 \(Z_k\) 中任取一项置换 \(z\)，则

\[\pi z\pi^{-1}(i)=\pi z(k)=\pi (k)=i \]

所以

\[\pi Z_k\pi^{-1}\subseteq Z_i \\ |\pi Z_k\pi^{-1}|\le|Z_i| \\ |Z_k|\le|Z_i| \]

将 \(k,i\) 两项 swap 后重复上述证明过程，即得到

\[|Z_k|\ge|Z_i| \]

结合两式后原命题得证。

(Burnside)

\[\color{blue}{ ans=\frac{1}{|G|}\sum_{\pi\in G}c_1(\pi) }\]

其中 \(ans\) 为 \(D\) 由 \(G\) 诱导出来的等价类个数，\(c_1(\pi)\) 表示置换 \(\pi\) 作用下保持不变的状态个数（角标 \(1\) 表示长度为 \(1\) 的环，因为这些状态在 \(\pi\) 置换时形成自环），换一种说法

\[c_1(\pi)=\sum_{k\in D}[\pi\in Z_k] \]

(Burnside Proof)

首先，

\[ans=\sum_{k\in D}\frac{1}{|E_k|} \]

因为这样每一个等价类对 \(ans\) 的贡献均为 \(1\)。

而由 (D) 得到

\[\begin{aligned} ans&=\sum_{k\in D}\frac{1}{|E_k|} \\&=\sum_{k\in D}\frac{Z_k}{|G|} \\&=\frac{1}{|G|}\sum_{k\in D}Z_k \\&=\frac{1}{|G|}\sum_{\pi\in G}c_1(\pi) \end{aligned}\]

最后一步其实是改变了计数方式：计数「某置换不改变某状态」从状态角度转变为置换角度。

即得证。

例题

就是开头给的例题。

为防止混淆，我们设珠子的颜色数为 \(m\)，虽然在这道题里 \(=n\)。

我们发现这个项链的置换群为 \(\{cy_0,cy_1,cy_2,\dots,cy_{n-1}\}\) 其中 \(cy_i\) 表示将项链顺时针旋转 \(i\) 格。

不妨设 \(cy_n=cy_0\)（反正是一个东西）（为了方便接下来的 \(\gcd\)）。

我们先搞定 \(c_1(cy_i)\quad(1\le i\le n)\)。

易发现

\[c_1(cy_i)=m^{\gcd(i,n)} \]

也就是将链子每 \(\gcd(i,n)\) 个划分，每一段都要相同。

然后就是 Burnside 了：

\[\begin{aligned} ans&=\frac{1}{|G|}\sum_{\pi\in G}c_1(\pi) \\&=\frac{1}{n}\sum_{i=0}^{n-1}c_1(cy_i) \\&=\frac{1}{n}\sum_{i=1}^{n}c_1(cy_i) \\&=\frac{1}{n}\sum_{i=1}^{n}m^{\gcd(i,n)} \\&=\frac{1}{n}\sum_{d|n}\sum_{i=1}^{n/d}m^d[\gcd(i,\frac{n}{d})=1] \\&=\frac{1}{n}\sum_{d|n}m^d\sum_{i=1}^{n/d}[\gcd(i,\frac{n}{d})=1] \\&=\frac{1}{n}\sum_{d|n}m^d\varphi(\frac{n}{d}) \end{aligned}\]

（显然使用了莫比乌斯反演，或你说是 \(\varphi\) 的定义也行）

关于如何解决剩下这个东西我那篇 Luogu 的题解应该讲得够清楚了。

拓展

P3307 [SDOI2013]项链 这道题项链支持翻转，稍难搞。