Burnside 引理 简单证明

· · 算法·理论

Burnside 引理

\Huge{|X/G|=\dfrac{1}{|G|}\sum\limits_{g\in G}|X^g|}

其中 G 必须是一个置换群。

证明

为方便，这里用 n 个点的环用 m 种颜色染色的经典问题举例。

考虑一个 naive 的计算方法：因为每种不重的染色经过所有置换运算过后都会产生 |G| 的贡献所以只需要将原来 看起来不同 的染色除以 |G| 就是不重的染色了！(注：看起来不同的染色指 单位置换后的不动点，下面叫做可重染色。比如 n = 3, m = 2 时看起来不同的染色有 2^3 = 8 个：111, 112, 121, 122, 211, 212, 221, 222)

很可惜错了。因为一种染色经过两个不同置换后可能是同一个可重染色。比如 1212，其经过旋转置换后会分别变成 1212, 2121, 1212, 2121 其中 1212 和 2121 只会计算到 1 次而不是我们想要的 2 次。

因此容易想到把重复的可重染色补齐。画个图：

其中第一行的点表示所有 不重染色，即我们要算的方案。第二行为这个 不重染色 能得到的 可重染色，从第一行连过来的边权为 任意一个 可得到 这个可重染色 的置换。第三行为这个 不重染色 经过 所有置换 所得到的 可重染色，从第一行连过来的边权为 那个置换(此处为旋转次数)。因为 置换有逆，所以一条 从第一行连向第三行的边 能被唯一拆成 一条从第一行连向第二行的边 和 从第二行连向第三行的边。如此后，这些 从第二行连向第三行的边 就是使第二行不动的那些置换了。

观察发现，Burnside 引理对每一个第一行的点(即一个不重染色)刚好算了所有 从第二行连向第三行的边 的数量。再想一下正确性：每个置换对 一个第一行的点 能找出唯一一条 从第二行连向第三行的边。而因为这些置换各不相同，所以贡献也一定有效。

因此，所有置换均向 每一个 第一行的点 进行了一点的贡献。自此证毕。