Skip to main content

__debug's Home Keep it simple, stupid

Burnside 引理小结

$$N(G, \mathcal{C}) = \frac{1}{|G|} \sum_{f \in G} \mathcal{C}(f)$$

引入

上面就是著名的 Burnside 引理啦. 可以用来解决一类计数问题. 注意下面的的定义叙述的并不是非常严谨.

首先定义在置换群 \(G\) 及合成运算 \(\circ\) 需要满足:

  • 封闭性
  • 结合性
  • 单位元的唯一性
  • 逆元的唯一性

然后定义着色集 \(\mathcal{C}\) 及置换与着色的运算 \(\ast\) 需要满足对 \(G\) 中置换的封闭性.

再定义两个着色 \(c, d\) 等价, 如果存在 \(f \in G\) 使得 \(f \ast c = d\).

最后定义几个记号:

  • \(\mathcal{C}(f)\): 在置换 \(f\) 的作用下不变的着色的集合
  • \(G(c)\): 使着色 \(c\) 不变的置换的h集合
  • \(E(c)\): 与 \(c\) 等价的着色的集合

证明

首先置换的运算有一些比较符合常识的性质, 比如说消去律. 这里就不证了.

我们首先需要证明一个引理: $$|E(c)| = \frac{|G|}{|G(c)|}$$

证明:

对于 \(G\) 中的一个置换 \(f\), 若存在 \(f \ast c = g \ast c\), 那么 \(g\) 一定可以被表示为 \(f \circ h\), 其中 \(h \in G(c)\).

那么由于 \(\{f \circ h\}\) 这个集合的大小显然为 \(|G(c)|\), 于是可以得知对于每个 \(f\) 都有 \(|G(c)|\) 个置换与自己作用于 \(c\) 有相同的效果.

于是就有 \(|E(c)| = \frac{|G|}{|G(c)|}\), 证毕.

然后就可以来证明 Burnside 引理了, 其中 \(N(G, \mathcal{C})\) 表示在 \(\mathcal{C}\) 在 \(G\) 中下的非等价着色个数: $$N(G, \mathcal{C}) = \frac{1}{|G|} \sum_{f \in G} \mathcal{C}(f)$$

证明:

首先有一个性质: $$\sum_{f \in G} |\mathcal{C}(f)| = \sum_{c \in \mathcal{C}} |G(c)|$$ 因为这两个都是对满足 \(f \ast c = c\) 的有序对 \((f, c)\) 的计数.

现在对 \(G(c)\) 这一边做手脚. 将 \(|E(c)| = \frac{|G|}{|G(c)|}\) 变一下形, 我们有 \(|G(c)| = \frac{|G|}{|E(c)|}\). 再带入一下, 我们有 $$\sum_{c \in \mathcal{C}} |G(c)| = |G| \sum_{c \in \mathcal{C}} \frac{1}{|E(c)|}$$ 然后考虑每个 \(c\) 的贡献是 \(\frac{1}{|E(c)|}\), 那么每一群等价的着色的贡献就是 \(1\), 也就是说 $$\sum_{c \in \mathcal{C}} \frac{1}{|E(c)|} = N(G, \mathcal{C})$$ 然后整理得到 $$N(G, \mathcal{C}) = \frac{1}{|G|} \sum_{c \in \mathcal{C}} |G(c)| = \frac{1}{|G|} \sum_{f \in G} |\mathcal{C}(f)|$$ 证毕. (这里为什么枚举 \(f\) 而不枚举 \(c\) 呢? 因为一般情况 \(f\) 和 \(c\) 都不是一个数量级的东西…)

至于 Pólya 定理, 首先它要求着色集有 \(k\) 种颜色, 着色不能有任何限制, 并且任何一种置换都不能改变颜色数量.

然后对于每个置换 \(f\), 定义 \(f\) 的单项式为 $$\mathrm{mon}(f) = z_1^{e_1} z_2^{e_2} \dots z_n^{e_n}$$ 其中 \(e_j\) 表示将 \(f\) 轮换分解之后, 大小为 \(j\) 的轮换的个数.

再定义一个 \(G\) 的生成函数 $$P_G(z_1, z_2, \dots, z_n) = \frac{1}{|G|} \sum_{f \in G} \mathrm{mon}(f)$$

从而, 如果我们用 \(u_1, u_2, ..., u_k\) 表示 \(k\) 种颜色, 那么 $$P_G(u_1 + u_2 + \cdots + u_k, u_1^2 + u_2^2 + \cdots + u_k^2, ..., u_1^k + u_2^k + \cdots + u_k^k)$$ 这个多项式的 \(u_1^{p_1} u_2^{p_2} ... u_k^{p_k}\) 这一项的系数就是 \(u_1\) 这个颜色使用 \(p_1\) 次, \(u_2\) 这个颜色使用 \(p_2\) 次, 等等, 这样的非等价着色数.

平时很多人讲的 Pólya 定理其实是令所有 \(u_j = 1\) 了, 也就是 \(P_G(k, k, ..., k)\) 这个特殊情形, 这样会丢失每个颜色的具体信息.

应用

首先需要用到 Burnside 引理的题的难点大概分为两种方面:

  1. 着色集 \(\mathcal{C}\)
  2. 置换群 \(G\)

大部分题目的难点都是着色集, 不过也有一些题目是难在置换群的.

BZOJ3202 [SDOI2013] 项链

Description

定义每种颜色可以用一个三元组 \((x, y, z)\) 表示, 满足 \(0 < x \le y \le z \le A\) 且 \(\mathrm{gcd}(x, y, z) = 1\).

现在要用这些颜色对一个 \(N\) 个点的环染色. 循环同构, 并且相邻的点的颜色必须不同.

求不同染色方案的个数. 对 \(10^9 + 7\) 取模. 共 \(T\) 组数据.

\(T \le 10, N \le 10^14, A \le 10^7\)

Solution

这是一道数学题套数学题套数学题… 十分丧病.

首先我们要求出不同的颜色有多少种. 不难求出 \(g(d)\) 表示 \(d \mid \mathrm{gcd}(x, y, z)\) 的三元组有多少个: $$g(d) = \binom{\left\lfloor\frac{A}{d}\right\rfloor + 2}{3}$$

然后设 \(f(d)\) 为 \(d = \mathrm{gcd}(x, y, z)\), 显然有 \(g(n) = \sum_{n \mid d} f(d)\) 莫比乌斯反演一下就是: $$f(n) = \sum_{n \mid d} \mu\left(\frac{n}{d}\right) g(d)$$ 我们要求的就是 \(f(1)\). 预处理 \(\mu\) 之后显然可以 \(O(\sqrt{A})\) 来求.

接下来就是 Burnside 了. Burnside 完了之后, 转化为一个子问题:

给你一个 \(n\) 个点的环, 用 \(m\) 种颜色染色, 有多少种方案满足相邻的两个点不同色?

这貌似也是一个经典问题.

设 \(a_n\) 为 \(n\) 个点时的答案, 显然有

\begin{aligned} a_1 &= 0 \\ a_2 &= m(m - 1) \\ a_n &= a_{n - 1} (m - 2) + a_{n - 2} (m - 1), (n \ge 3) \end{aligned}

解特征方程得到通项 $$a_n = (m - 1)^n + (-1)^n (m - 1)$$

搞完啦! 不过还有一些细节问题, 比如 \(10^9 + 7 \mid n\) 的时候.

SPOJ TRANSP2

Description

一个 \(2^a 2^b\) 的二维数组在内存中的存储方式为先存第一行, 再存第二行, 以此类推. 现在你需要将其转置, 举个例子: \({\begin{bmatrix}1&2\\3&4\\5&6\end{bmatrix}}^{\mathrm {T} }\!\!\;\!=\,{\begin{bmatrix}1&3&5\\2&4&6\end{bmatrix}}\)

问最少需要交换多少次元素. 对 \(1000003\) 取模. 共 \(T\) 组数据.

\(T \le 4 \times 10^5, 0 \le a + b \le 10^6\)

Solution

矩阵转置时, 每个位置的数都会有一个唯一的目标位置, 那么将这个点数为 \(2^{a + b}\) 的有向图画出来一定是由很多环组成的. 显然最少的交换次数为 \(2^{a + b} - c\), 其中 \(c\) 表示这张图中环的个数. 但是暴力找环显然不可行, 得好好利用 \(2\) 的次幂这个条件才行.

不妨将每个点在内存中的位置表示为一个 pair, 如 \(3\) 行 \(5\) 列表示为 \((11, 101)\). 那么转置一下, 它就变成了 \((101, 11)\), 可以理解为交换横纵坐标, 但是如果把横纵坐标连在一起的话 (即 \(11101 \to 10111\)), 也可以看成是循环左移 \(a\) 位. 然后由于坐标的范围是 \(2^a\) 和 \(2^b\), 也就是说每个点都可以对应 \([0, 2^{a + b})\) 中的一个二进制数, 可以将问题转化为:

一个长度为 \(a + b\) 的环, 给每个点染上黑白两种颜色. 每次可以将一个环逆时针旋转 \(a\) 个单位, 如果一种染色方案能通过旋转变为另一种染色方案, 那么这两种方案视为同一种. 求不同的方案数.

上面这个问题的答案就是环的个数 \(c\).

这就是一个比较明显的 Burnside 了, 置换群 \(G\) 的大小为 \(\frac{\mathrm{lcm}(a + b, a)}{a} = \frac{a + b}{\mathrm{gcd}(a, b)}\).

为了叙述方便, 记 \(g = \mathrm{gcd}(a, b)\), \(n = \frac{a + b}{g}\). 根据 Burnside 引理, 有 \[\begin{aligned} N(G, \mathcal{C}) &= \frac{1}{|G|} \sum_{f \in G} \mathcal{C}(f) \\ &= \frac{1}{n} \sum_{k = 1}^{n} 2^{\mathrm{gcd}(ka, n)} \\ &= \frac{1}{n} \sum_{k = 1}^{n} \left(2^{g}\right)^{\mathrm{gcd}(k, n)} \end{aligned}\] 然后就是非常套路的枚举约数再用 \(\varphi\) 来算贡献了.

BZOJ1488 [HNOI2009] 图的同构

Description

求两两互不同构的含 \(n\) 个点的简单图有多少种.

简单图是关联一对顶点的无向边不多于一条的不含自环的图. \(A\) 图与 \(B\) 图被认为是同构的是指 \(A\) 图的顶点经过一定的重新标号以后, \(A\) 图的顶点集和边集能完全与 \(B\) 图一一对应.

\(n \le 60\)

Solution

先以划分数的复杂度枚举点置换, 然后每次搞出边置换以后 Burnside 计个数就可以了. 点置换转为边置换的时候一定要细心一点. (其实是不想写详细题解了… QAQ)

Comments

Comments powered by Disqus