染色计数

置换

置换是一个满射，例如：
$$ f(1) = 2, f(2) = 4, f(3) = 3, f(4) = 1 $$

也写做：
$$ f = \left( \begin{matrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 3 & 1 \end{matrix} \right) $$

置换可以合成。假如我们有：
$$ \begin{aligned} f = \left( \begin{matrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{matrix} \right) \\ g = \left( \begin{matrix} 1 & 2 & 3 & 4 \\ 4 & 1 & 2 & 3 \end{matrix} \right) \end{aligned} $$

那么它们按照一定顺序加合的结果是：
$$ g \circ f = \left( \begin{matrix} 1 & 2 & 3 & 4 \\ 1 & 2 & 3 & 4 \end{matrix} \right) $$

即从右至左地执行这些置换。同时上面这个置换是不变元，无论什么置换与它加合都不会变化。另外，置换的加合满足结合律，但不一定满足交换律。置换的另外一种表示方式就是置换矩阵。这也可以说明为什么置换不满足交换律。

由于置换具有这些性质，所以置换的加合运算和置换可以构成置换群。

染色

首先回答一个简单的问题：给正方形四个顶点分别染成黑色或白色的方案有多少个？显然每个顶点都有两种选择，所以答案为$2^4 = 16$。

现在做出一点限制，如果一个染过色的正方形通过旋转或者轴对称后与另外一个染过色的正方形相同，就说这两种染色是本质相同的。那么问你有多少种本质不同的染色方案。通过枚举，我们也可以知道答案是$6$。这$6$中方案如下 (本质相同的只画了一种)：

对我们而言，难以考虑的是同构的问题。假如我们给顶点标号，分别为$1$、$2$、$3$和$4$：

那么上面这个图的染色为：
$$ c_1 = \left( \begin{matrix} 1 & 2 & 3 & 4 \\ \mathrm{W} & \mathrm{B} & \mathrm{W} & \mathrm{W} \end{matrix} \right) $$

经过对称，与之同质的染色是这样的：
$$ c_2 = \left( \begin{matrix} 1 & 2 & 3 & 4 \\ \mathrm{W} & \mathrm{W} & \mathrm{B} & \mathrm{W} \end{matrix} \right) $$

事实上，这个变换可以看做是将$2$和$3$调换了一下。于是我们将这个对称定义成这样一个置换：
$$ f = \left( \begin{matrix} 1 & 2 & 3 & 4 \\ 1 & 3 & 2 & 4 \end{matrix} \right) $$

然后定义$\times$运算，表示一个染色的顶点经过一个置换后，得到的新的染色，于是有：
$$ f \times c_1 = c_2 $$

可以发现，置换的加合和上面的变换在一起时也满足结合律。

这样，我们就将颜色的同构用置换表示出来了。我们定义正方形所有的变换为一个置换，它们构成一个集合：
$$ G = \{e = p^0, p, p^2, p^3, f_1, f_2, f_3, f_4\} $$

其中$e$是置换的不变元。$p$是顺时针旋转$90^\circ$的置换：
$$ p = \left( \begin{matrix} 1 & 2 & 3 & 4 \\ 4 & 1 & 2 & 3 \end{matrix} \right) $$

而$p$的幂次就是多次旋转。$f_1$到$f_4$是沿着正方形的四条对角线的置换。可以验证这个集合和置换的加合运算构成了一个置换群。因此，对于两种染色$c_1$和$c_2$，它们本质相同当且仅当存在一个$f \in G$，满足$f \times c_1 = c_2$。

另外，设图形的所有染色方案为$C$，定义$G(c)$为$\{f : f \times c = c, \;\forall f \in G\}$，即不改变染色$c$的置换的集合。以及$C(f)$为$\{c : f \times c = c, \; \forall c \in C\}$，即经过置换后不变的所有的染色方案的集合。之后的讨论中将会用到它们。

Burnside定理

首先来考虑与$c$本质相同的染色的个数：

定理：与$c$本质相同的染色的个数为：
$$ {|G| \over |G(c)|} \tag{3.1} $$

证明：考虑每个$f \times c, f \in G$，$G(c)$中都存在$|G(c)|$个$g$, 满足$(f \circ g) \times c = f \times (g \times c) = f \times c$。即对于任意染色方案，都有$|G(c)|$种置换使得染色方案不变。所以总数为$|G| / |G(c)| $。

接下来将采用双重计数来证明下面的Burnside定理：

(Burnside定理)
设关于染色集$C$与置换群$G$上本质不同的染色方案数为$N(G, C)$，那么满足：
$$ N(G, C) = \frac1{|G|}\sum_{f \in G} |C(f)| \tag{3.2} $$

证明：我们现在来考虑满足$f \times c = c$的二元组$(f, c)$的个数。首先我们从$C(f)$的角度考虑，可以知道答案为：
$$ \sum_{f \in G} |C(f)| $$

另外，从$G(c)$的角度考虑，也可以知道答案为：
$$ \sum_{c \in C} |G(c)| $$

为了方便，我们设$A(c) = \{f \times c, \; \forall f \in G\}$，即与$c$本质相同的染色的集合。根据$(3.1)$，我们知道：
$$ |G(c)| = {|G| \over |A(c)|} $$

那么可以得到：
$$ \sum_{f \in G} |C(f)| = |G|\sum_{c \in C} \frac1{|A(c)|} $$

对右边的和式做如下的考虑：假设每个等价的集合的贡献是$1$，那么每个染色的贡献就是$1/|A(c)|$，所以上式可以改写为：
$$ \sum_{f \in G} |C(f)| = |G|N(G, C) $$

所以：
$$ N(G, C) = \frac1{|G|}\sum_{f \in G} |C(f)| $$

回到之前正方形染色的例子，我们对于每一个置换这样考虑：

1. 对于不变元$e$，总共有$2^4 = 16$中染色不变。
2. 对于$2$个顺时针旋转 (除了旋转$180^\circ$)，它们都只有全是黑或者全是白的染色不变，贡献为$2 \times 2 = 4$。
3. 对于旋转$180^\circ$，只需要满足两个相邻的顶点颜色相同即可，所以贡献为$2^2 = 4$。
4. 对于$2$个对角线对称，只要满足对角颜色相同即可，贡献为$2^3 \times 2 = 16$。
5. 对于另外$2$个对称，需要满足两边颜色相同，贡献为$2^2 \times 2 = 8$。

所以答案为$(16 + 4 + 4 + 16 + 8) / 8 = 6$。

进一步考虑计算$C(f)$。假如我们将置换写成置换环的形式，例如：
$$ f = \left( \begin{matrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{matrix} \right) $$

可以写成：
$$ f = [2\;1][4\;3] $$

可以发现，如果要满足经过置换后染色不变，那么每一个置换环内的颜色必须相同。于是，对于这一个置换环而言，计算就可以直接简便为$2^2 = 4$，而不需要去做讨论。

简单图计数

【HNOI 2009】图的同构

现在来讨论一个更加复杂的问题，就是$n$个点的本质不同的简单无向图的数量¹²。简单图是没有重边和自环的图。记为$a(n)$。

首先，我们可以直接列举可以得知：
$$ a(0) = 1, a(1) = 1, a(2) = 2, a(3) = 4 $$

更大的$n$如果采用列举的方法实在无法想象。为了能够利用Burnside定理，我们考虑将其转为一个染色问题。注意到大小为$n$的简单图的边已经全部确定，只是存在选或不选的问题。所以可以视为是这些边是染成黑色还是染成白色的问题。此外我们要将本质相同的计数去掉。如果两个图相同，那么存在一个与点编号相关的置换，使得两张图的边集是一样的。所以我们考虑所有的点的置换，总数为$n!$个，每一个将会对应到一个边的置换，即用于判定同构的置换。可以证明从点的置换转来的边的置换是一个置换群。

现在来考虑点的置换是如何转成边的置换的。由于我们已经可以根据置换环的数量来计算$C(f)$了，所以我们不需要关注置换到底长什么样，只需要知道有多少个置换环即可。对于一个边的置换，里面的每一条边的两个端点要么在点置换的一个置换环内，要么在不同的置换环内。

首先观察一下在同一个置换环内的情况：

黄色的边是置换环上的边，而红色的就是边置换中的边。由于将整条边随着置换环旋转，会得到许多一样的边，所以我们将一个点固定，来考虑另外一个点。可以发现实线的边是不同的，而虚线的边则是和实线的边是同构的。所以，对于长度为$L$的置换环，在边的置换中对应了$\lfloor L / 2 \rfloor$个置换环。

然后考虑不在同一个置换环的情况：

设两个置换环的长度分别为$A$和$B$，可以发现，每一条连接两个置换环的边，都会有$\mathrm{lcm}(A, B)$条边与它同构。而总边数为$AB$，所以这个点置换的置换环就对应了边置换中的$\gcd(A, B)$个置换环。

考虑完点置换和边置换的一一对应关系后，我们考虑来计数点置换集中有多少个置换环长度分别为$L_1, L_2, L_3, \dots$的置换。设长度为$i$的置换环的个数为$S_i$，那么这个数量是：
$$ {n! \over L_1 L_2 L_3 \cdots S_1!S_2!S_3!\cdots} $$

因为对于每个置换环，随意循环旋转都是同构的，而大小相同的置换环互相之间也是一样的，所以需要除去上面那个分母。

所以我们就可以算出所有置换的贡献，然后除以置换的总个数$n!$，就是我们的答案。

最后，我们只需要枚举置换中置换环的情况，这个其实就是$n$的分拆。利用这个方法，我们可以计算更大的$n$的方案 (但是还是难以计算近百的级别)。