【笔记】Burnside 引理，Pólya 定理

OI-Wiki

Burnside 引理

数学描述见 Wiki，和实际问题对应起来就行

为了方便我后来的脑子理解，这里首先确定问题为：

对若干元素进行染色（即一个 A 到 B 的映射），并给出一系列等价判定规则（即对于两个染色方案，判断是否存在某种置换，在对元素进行该置换后，根据映射结果是否相同确定这两个方案是否等价），求本质不同的方案数（即等价类的个数）

所有的判定规则，即置换群 G = {a_1, a_2, ...}；对于一个置换 a_k，记所有染色方案根据这个置换得到的新的映射结果不变的个数为 \(c_1(a_k)\)
则等价类的个数等于：

\[\frac{1}{|G|}\sum_{a_i\in G}{c_1(a_i)} \]

例题，可以见Wiki或者这里也有一个

Pólya 定理

我们换一个方式计算 \(c_1(a_k)\)
设颜色个数 m（=|B|），C(a) 表示置换 a 能拆成的不相交的循环置换的数量，则 \(c_1(a_k) = m^{C(a_k)}\)，即：

\[\frac{1}{|G|}\sum_{a_i\in G}{m^{C(a_i)}} \]

这个的含义就是，若置换后映射结果不变，等价于每个循环置换内的那些位置都同色

放一个模板题
发现答案就是$$\frac{1}{n}\sum^{n}_{i=1} n^{(i, n)}$$

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