Burnside 引理入门

群

给定一个集合 $G$ 和集合上的二元运算 $\circ$ ，满足

封闭性： $\forall a,b\in G,a\circ b\in G$ 。
结合律： $\forall a,b,c\in G,(a\circ b)\circ c=a\circ(b\circ c)$ 。
单位元： $\exists e\in G,\forall a\in G, a\circ e=e\circ a=a$ 。
逆元： $\forall a\in G,\exists b\in G, a\circ b=b\circ a=e$ ，记 $b=a^{-1}$ 。

称 $G$ 在运算 $\circ$ 下是一个群。如整数加法群。

置换

狭义的置换可以理解为排列。

$n$ 个元素 $1,2,\cdots,n$ 之间的一个置换

$\begin{pmatrix} 1&2&\cdots&n\\ p_1&p_2&\cdots&p_n \end{pmatrix}$

表示 $i$ 被 $p_i$ 取代，可以表示为 $i \to p_i$ 。

置换群

置换是集合的元素，运算的置换的连接。对于两个置换 $a_i,b_i$ ，他们的连接可以理解为 $i\to a_i\to b_{a_i}$ 。

Burnside 引理

对于一个集合 $S$ 以及与之相关的置换群 $G$ ，我们说将置换群 $G$ 作用于 $S$ ，意味着对于 $x, y\in S$ ，若存在 $p\in G$ 使得 $p(x) = y$ ，那么我们认为 $x$ 和 $y$ 是等价的。

记 $S/G$ ，为 $G$ 作用在 $S$ 上的轨道数，即本质不同的元素个数。

那么 Burnside 引理用于计算 $|S/G|$ ，其公式为

$|S/G|=\frac{1}{|G|}\sum_{p\in G}D(S, p)$

用 $D(S, p)$ 表示在置换 $p$ 关于 $S$ 的不动点个数，即 $D(S, p) = \sum_{e\in S}[p(e) = e]$ 。

Polya 定理

如果是处理染色问题，那么我们将置换进行轮换分解（分解成若干个环），那么每个环上的点必须染同一种颜色。假设一个置换有 $e_i$ 个大小为 $i$ 的轮换（ $1 \le i\le n$ ），那么使用多元生成函数表示置换群 $G$ 中各类轮换数目组合的置换数为 $[z_1^{e_1} \cdots z_n^{e_n}]p_G(z_1, \ldots, z_n)$ 。那么用 $m_j$ 个颜色 $j$ 染色（ $m_1 + \cdots + m_t = n$ ）的方案数可以表示为

$[x_1^{m_1} \cdots x_t^{m_t}]p_G(\{ x_1^i + x_2^i + \cdots + x_t^i \})$

He’s Circles

有一个长度为 $N$ 的环，上面写着X和E，问本质不同的环有多少种。 $N\le 2\times 10^5$ 。

这道题的环指

$\begin{pmatrix} 1&2&\cdots&n\\ 1+k&2+k&\cdots&n+k \end{pmatrix}\pmod n$

构成的置换群。（ $0$ 当成 $n$ ）其中 $0\le k<n$ 。把置换理解为若干个环的话，你发现这个置换的环数恰好为 $\gcd(k,n)$ 。如果方案中一个环上的颜色相同的话，那么作用这个置换后方案是不会变的。而总共有两种颜色，于是 $D(a_i=i+k\bmod n)=2^{\gcd(k,n)}$ 。这样就可以统计了。

HNOI2008 Cards

考虑 Burnside 引理。对于一个置换不变的方案显然在它的一个环是同色的。因对于一个置换处理出环长后，我们做一个三维背包求方案数即可。

注意，题目给的并不是一个完整的置换群，它少了一个恒等置换。

代码

Isomorphism

给定一个 $N$ 个结点的无向完全图（任意两个结点之间有一条边），现在你可以用 $M$ 种颜色对这个图的每条边进行染色，每条边必须染一种颜色。
若两个已染色的图，其中一个图可以通过结点重新编号而与另一个图完全相同，就称这两个染色方案相同。问本质不同的染色数。
$N\le 53, M\le 1000$ 。

我们要求的就是边的置换的环数。考虑将边的置换分类。

这题的置换群对点而言是一个全排列，但对于边而言就不是了。对于两个点 $i,j$ ，他们的置换为 $P_i,P_j$ ，则边的置换为 $(i,j)\to (P_i,P_j)$ 。

考虑将点的置换分类，那么每个置换可以由 $k$ 个大小分别为 $L_i$ 的环表示。

对于两个点 $i,j$ ，如果他们分别在长度为 $L_1,L_2$ 的环上，那么考虑边的置换的环数。这样的边总共有 $L_1\times L_2$ 个，而每个环的长度为 $[L_1,L_2]$ ，则环的个数为 $\gcd(L_1,L_2)$ 。

如果这两个点都在长度为 $L$ 的同一个环上，那么这样的边总共有 $\dbinom{L}{2}$ 个。

如果 $L$ 是奇数，则每个环长度为 $L$ ，则环的个数为 $\dfrac{\binom{L}{2}}{L}=\frac{L-1}{2}$ 。
如果 $L$ 是偶数，那么当 $i+\frac{L}{2}\equiv j$ 时环长为 $\frac{L}{2}$ ，其他时候环长为 $L$ 。则环的个数为 $\dfrac{\binom{L}{2}-\frac{L}{2}}{L}+1=\frac{L}{2}$ 。

综上，形如 $L_1,L_2,\cdots,L_k$ 的点置换对应的边置换的环数为

$C=\sum_{i=1}^k\left\lfloor \frac{L}{2} \right\rfloor +\sum_{i=1}^k\sum_{j=1}^{i-1}\gcd(L_i,L_j)$

然后我们要求的就是形如 $L_1,L_2,\cdots,L_k$ 的点置换的个数，我们规定 $L_i\le L_{i+1}$ 。

首先考虑多项式定理，则把 $n$ 个点分到大小分别为 $L_i$ 的集合的方案数是 $\dbinom{n}{L_1,L_2,\cdots,L_k}$ 。而每个集合内的元素构成一个环，方案数是 $\frac{L!}{L}=(L-1)!$ （圆排列），于是乘上一个 $\prod_{i=1}^k(L_i-1)!$ 。再考虑到， $L$ 长度相同的环我们是不计他们之间的顺序的，因此设长度为 $x$ 的环有 $B_j$ 个，则还得除掉一个 $\prod_{j=1}^tB_j!$ ， $t$ 表示长度本质不同的环的个数。整理一下得到

$S=\frac{n!}{\prod_{i=1}^kL_i\prod_{j=1}^tB_j!}$

根据 Burnside 引理，这部分的贡献为 $Sm^C$ 。

最后，我们怎么枚举形如 $L_1,L_2,\cdots,L_k$ 的置换？置换的数量是 $n$ 的拆分数， $n=53$ 时大概是 $3\times 10^5$ 级别的，因此直接 DFS 枚举即可。

代码

染色

对一个长度为 $n$ 的项链黑白染色，并且规定旋转、翻转、反色等操作后的方案等价。问本质不同方案数。
对 $998244353$ 取模。 $n\le 10^{12}$ 。

这道题集合了许多 Burnside 题的技巧和难点。题目本身也有很多理解方式。

一个基础的知识点是旋转和翻转构成的置换群大小是 $2n$ 。我们把反色也可以当成一种置换。容易发现这种特殊的置换是满足群的性质的。这样反色、翻转、旋转置换群大小是 $4n$ 的。考虑 Burnside 定理。

旋转不反色。显然贡献是 $\sum_{i=1}^{n}2^{(i,n)}=\sum_{d|n}\varphi\left(\dfrac{n}{d}\right)2^{d}$ 。
翻转不反色。这时要分 $n$ 奇偶考虑。 $n$ 是偶数，则贡献为 $\dfrac{n}{2}(2^{\frac{n}{2}}+2^{\frac{n}{2}+1})$ ；否则 $n$ 是奇数，则贡献为 $n2^{\left\lfloor\frac{n}{2}\right\rfloor+1}$ 。
旋转并强制反色，则我们环上是交替填色的，环长是偶数。因此贡献是 $\sum_{i=1}^{n}\left[2\mid\dfrac{n}{(i,n)}\right]2^{(i,n)}=\sum_{d|n}\left[2\mid \dfrac{n}{d}\right]\varphi\left(\dfrac{n}{d}\right)2^d$ 。
翻转并强制反色。则环长必须是偶数（2），则 $n$ 是偶数时才有贡献： $\dfrac{n}{2}\cdot 2^{\frac{n}{2}}$ 。

于是总的贡献是

$\begin{aligned} &[2\mid n]\frac{n}{2}(2^{\frac{n}{2}}+2^{\frac{n}{2}+1}+2^{\frac{n}{2}})+[2\nmid n]n2^{\left\lfloor\frac{n}{2}\right\rfloor+1}+\sum_{d|n}\varphi\left(\frac{n}{d}\right)2^d+\left[2\mid \frac{n}{d}\right]\varphi\left(\frac{n}{d}\right)2^d\\ =&n2^{\left\lfloor\frac{n}{2}\right\rfloor+1}+\sum_{d|n}\varphi\left(\frac{2n}{d}\right)2^d \end{aligned}$

这里使用了 $\varphi(2)$ 的一个小技巧。由于置换群的大小是 $4n$ ，因此答案为

$\frac{n2^{\left\lfloor\frac{n}{2}\right\rfloor+1}+\sum_{d|n}\varphi\left(\frac{2n}{d}\right)2^d}{4n}=2^{\left\lfloor\frac{n}{2}\right\rfloor-1}+\frac{\sum_{d|n}\varphi\left(\frac{2n}{d}\right)2^d}{4n}$

最后计算的时候要注意 $p\mid n$ 的情况。这时 $n$ 在模 $p$ 意义下就没有逆元了。我们把 $p$ 平方，然后在模 $p^2$ 意义下求出分子。由于在非模意义下分子是 $4n$ 的倍数，而 $p\mid n$ 。因此在模 $p^2$ 意义下分子是 $p$ 的倍数。于是我们直接分子分母模数同时除以 $p$ （ $p^2$ 变回 $p$ ）。由于 $n\le p^2$ ，因此 $p\nmid \dfrac{n}{p}$ 。则现在分母就有逆元了，可以直接算了。

参考文献

[1] 陈瑜希，Pólya 计数法的应用

文章目录

群

置换

置换群