Loading... ## 0x00 Burnside's lemma 这里需要一点群论的知识，设 $G$ 是一个置换群群，将作用在集合 $X$ 上，有以下结论： $$ \left|X/G\right|=\frac{1}{\left|G\right|}\sum_{g\in G} \left|X^g\right| $$ - 其中 $X/G$ 表示集合 $X$ 在群 $G$ 作用下的本质不同元素集合，那么 $\left|X/G\right|$ 则表示本质不同元素个数，即轨道数。 - $g$ 表示置换群 $G$ 中的一个置换。 - $X^g$ 表示集合 $X$ 在置换 $g$ 变换下，$X$ 集合中的不动点，$\left|X^g\right|$ 自然表示不动点数。 对于这个题来说 $X$ 就是 $n$ 个点的简单无向图集合，一共 $2^{{n\choose 2}}$ 个。$G$ 就是点标号的置换的集合，即排列的集合，一共 $n!$ 个。$g$ 就是一个排列，$\left|X^g\right|$ 则表示按照 $g$ 对图重标号后，有多少个图和原来一样。 若两个图同构，说明可以通过重标号一个图的方式得到另一个图，所以说 $\left|X/G\right|$ 就等于有多少个不同构的数。这样转化重点就是计算 $\left|X^g\right|$。 ## 0x01 计算 $\left|X^g\right|$ 假设有一个 $g$，怎么计算 $\left|X^g\right|$，显然只需要关注边的情况，什么情况下一个图在 $g$ 变换后与原图相同呢？假设现在有两个点 $u,v$，则他们重编号映射后就是 $g_{u},g_{v}$，由于要和原图相同，所以 $u,v$ 的连边情况和原图要是相同的。这意味着在 $g$ 的变化下有一些边是等价的，对于某一个等价类，要么全连上要么全不连，假设有 $k$ 个等价类，则有 $2^k$ 个图是不动点，即 $\left|X^g\right|=2^k$。 ## 0x02 计算 $k$ 寻找等价类的过程就是从某一条边 $u\leftrightarrow v$ 出发，然后寻把 $g_{u}\leftrightarrow g_{v}$ 这条边合并到一个等价类，然后 $g_{g_u}\leftrightarrow g_{g_v}$ 合并，相当于是 $u,v$ 每次分别走到 $g$ 变换的点去，然后重复过程，直到回到最初的点，自然想到把 $g$ 拆成若干个置换环。现在分类讨论 $u,v$ 所在置换环的情况： 1. $u,v$ 在同一个置换环中，设置换环长度为 $b$，显然 $u,v$ 同时走 $b$ 步之后会回到最初的点，并且过程中 $u,v$ 在置换环上的间距保持不变，那么在每一个等价类对应一个间距，故共有 $\left\lfloor\frac{b}{2}\right\rfloor$ 个等价类。 2. $u,v$ 不在同一个置换环中，设置换环长度分别为 $b_1,b_2$ 和刚才一样，每次 $u,v$ 都分别走到 $g$ 变换的点去，要走 $\text{lcm}(b_1,b_2)$ 才能回到最初出发的边，也就是等价类里面一共有 $\text{lcm}(b_1,b_2)$ 条边。而两个置换环之间一共能连出 $b_1b_2$ 条边，所以一共有 $\frac{b_1b_2}{\text{lcm}(b_1,b_2)}=\gcd(b_1,b_2)$ 个等价类。 设当有 $m$ 个置换环，置换环长度分别为 $b_i$，根据上面的推论有： $$ k=\sum_{i=1}^m\left\lfloor\frac{b_i}{2}\right\rfloor+\sum_{i=1}^m\sum_{j=1}^{i-1}\gcd(b_i,b_j) $$ ## 0x03 统计排列 直接枚举排列显然是不行的，但是发现若排列的置换环长度 $b$ 序列相同，贡献也是相同的，于是直接枚举 $b$，即 $n$ 的一个整数拆分。考虑计算有多少个排列的置换环长度是 $b$，先考虑把 $n$ 个数划分到每一个置换环里面，再考虑置换环内部排列方式。随便放有 $n!$ 个排列，但是每一个置换环内部的排列先不计算，所以要除去 $b_i!$，但是长度相同的置换环交换还是同样的情况，所以也要出去，设长度为 $i$ 的置换环有 $c_i$ 个，就是要除 $c_i!$，所以划分方案一共是： $$ \frac{n!}{\prod (b_i!)\prod (c_i!)} $$ 现在考虑置换环内部的排列情况，显然就是圆排列，有 $(b_i-1)!$ 个，最终就是： $$ \frac{n!\prod (b_i-1)!}{\prod (b_i!)\prod (c_i!)}=\frac{n!}{\prod b_i\prod (c_i!)} $$ 把前面提到的式子整理一下： $$ \begin{align} \left|X/G\right|&=\frac{1}{\left|G\right|}\sum_b \frac{n!2^k}{\prod b_i\prod (c_i!)}\\ &=\frac{1}{n!}\sum_b \frac{n!2^k}{\prod b_i\prod (c_i!)}\\ &=\sum_b \frac{2^k}{\prod b_i\prod (c_i!)}\\ k&=\sum_{i=1}^m\left\lfloor\frac{b_i}{2}\right\rfloor+\sum_{i=1}^m\sum_{j=1}^{i-1}\gcd(b_i,b_j) \end{align} $$ ## 0x04 扩展问题 这道题中每一个图相当于是对边染色了，出现的染白，没出现的染黑，不妨多搞几个颜色。$n$ 个点的无向完全图，有 $m$ 中颜色，可以给边随意染色，问可以染出多少个本质不同的图。要解决这个问题我们回到计算 $\left|X^g\right|$ 一步，最后的统计 $2^k$ 就是再说染黑还是染白，自然有 $m$ 种颜色就是 $m^k$。 $$ \begin{align} \left|X/G\right|&=\sum_b \frac{m^k}{\prod b_i\prod (c_i!)}\\ k&=\sum_{i=1}^m\left\lfloor\frac{b_i}{2}\right\rfloor+\sum_{i=1}^m\sum_{j=1}^{i-1}\gcd(b_i,b_j) \end{align} $$ 于是就得到了 P4128 一题做法。 最后修改：2024 年 04 月 25 日 © 允许规范转载 打赏 赞赏作者 赞 如果觉得我的文章对你有用，请随意赞赏