感性理解 Pólya 定理

WeLikeStudying · 2022-02-27 17:48:13 · 算法·理论

• 今天，我由于数学太差，决定绕开群论来学习 Pólya 定理。
• 当然后面还是得搞理论。

引入

• 在组合问题中，有时要求把经过一些转换后相同的方案看作本质相同的状态，并要求计数本质不同的状态个数。
• 我们先来看一个简单的例子：用 k 种颜色给一个 2\times 2 的正方体染色，旋转后相同的方案被视为同一种。
• 我们把旋转 0,90,180,270 度的情况分别计算。
• 旋转 0 度不变的方法是所有的 k^4 种方案。
• 旋转 90,270 度不变的方法是所有格子都只染一种颜色，分别 k 种。
• 旋转 180 度不变的方法是对角线上的所有格子都染一种颜色，分别 k^2 种。
• 容易发现它们的平均数 \dfrac{k^4+k^2+2k}4 就是答案。
• 考虑为什么可以这样计算：考虑该图，左边的被 0 度的情况重复算了四次，中间的被 0 度分别算了 2 次，180 度算了 2 次，右边的被 0,90,180,270 度分别算了一次，所以每种情况都是算了 4 次，加起来除以 4 便是答案。
• 把每种情况都算相同的次数，然后除以这个数值，就是 Burnside 引理的思想。
• 在这个有趣的思想之后，我们来看它的推导。

借鉴

• 这篇，这篇，以及组合数学引论。
• 没用的东西专业的群论知识我尽量不写，因为作者很懒便于理解。
• 以下的内容极其不专业。

群

• 定义集合 S 与二元运算 \times 满足： \forall a,b\in S,a\times b\in S \forall a,b,c\in S,(a\times b)\times c=a\times( b\times c) \exists e\in S,\forall a\in S,a\times e=a \forall a\in S,\exists b\in S,a\times b=e
• 即封闭性，结合律，单位元，逆元（其中 a 的逆元为 a^{-1}），称 S 在 \times 运算下是个群。

简单定理

• 单位元唯一：e_1,e_2 是单位元则 e_1\times e_2=e_1=e_2。
• 逆元唯一：a\times b=e=a\times c\to b=c。
• 对于任意有限群，设 a^b 是 b 个 a 相乘的结果，则对于每个 a 都存在 \text{ord}(a) 满足 a^{\text{ord}(a)}=e，且 a^{-1}=a^{\text{ord}(a)-1}。
• 直接构造 a^0,\cdots,a^n，根据鸽巢原理肯定有两个相等，设 a^x=a^y 则 a^{y-x}=e，非常合理对吧。

置换群

• 置换是一个排列，置换的乘法就是把 i 换成 p_i。
• 置换不满足交换律，但满足结合率，单位元是 i=p_i，逆元也很好求，所以 n 元置换组成的结合与乘法直接成群。
• 我们用环表示置换，即把 i\to p_i 的边表示出来形成的多个环写出来。
• 我们也喜欢用几个基本置换，把大小为 1 的置换隐去，表示所有置换。
• 置换还可以和整数运算，具体细节十分简单就不重点提及，我们通过把集合标号成整数的方式来实现它。

例题 1

• 给定一个置换，求有多少个置换的 n 次方等于该置换。
• 将置换表示成环，发现一个大小为 k 的环在 n 次方后会裂解为 \gcd(n,k) 个大小为 k/\gcd(n,k) 的环。
• 考虑原置换的所有大小相同的环。
• 那么接下来问题就是这个样子：将 t 个有标号球分组，大小为 i 的组的贡献是 W(i)=(i-1)!k^{i-1}（钦定第一个小环直接连的 i-1 个节点表示整个环），且贡献相乘，要求每组盒子的大小满足某个条件，求所有情况的贡献的和。
• 设 f(t) 为使用了 t 个环的方案数，则： f(t)=\sum_{i=1}^t[\gcd(ik,n)=i]C(t-1,i-1)W(i)f(t-i)
• 注意环内部无序，所以组合数设为 C(n-1,i-1)。
• 注意到你发现这要求 i\mid n，所以枚举量是 O(n\sigma_0(n)) 的，代码。

前置知识

• 我们研究的问题是在一个集合 |S| 内的元素，通过置换群 |G| 的置换，形成的等价类个数的问题，请务必注意这点。
• 不动点：设 k\times p=k 则元素 k 是置换 p 下的不动点，p 形成的集合组成的置换群为 Z_k 为 k 不动置换类，经过 p 的不动点组成集合 C_p。
• 等价类：设 E_k 为元素 k 经过置换群 G 中的元素能到达的集合，由于群的特性，等价类中任何一个元素的等价类都是该等价类，而且每个元素至少是完全图的连边，都可以一步到达。
• 注意不动置换类是置换群，等价类是元素集合。
• 等价类和不动点定理：|Z_k|\times |E_k|=|G|，即使得 k 不动的置换个数，乘上 k 的等价类个数，恰好是置换总个数。
• 我们设 E_k=\{a_1,\cdots a_m\}，再对每个 a_i 瞎弄一个置换 p_i，使得 k\times p_i=a_i，然后让 G_i=Z_k\times p_i（也就是让每个置换和该置换搞下形成新的置换群），你发现对于 i\ne j，G_i\cap G_j=\varnothing，且 |G_i|=|Z_k|，剩下的唯一问题在于证明 G_i 不交。
• 由于显然 G_1\cup\cdots\cup G_m\subseteq G，而对于任意 p\in G，一定存在 k\times p=a_i，所以 G\subseteq G_1\cup\cdots\cup G_m，所以 |Z_k|\times |E_k|=|G|。

Burnside 引理

• 对于 |S| 内元素形成的等价类个数 l： l=\frac 1{|G|}\sum_{p\in G}|C_p|
• 也就是等价类个数为在各个置换下不动的元素个数的平均数。
• 设 f(i,j) 表示元素 i 在置换 j 的作用下是否不动，返回 0/1。 \sum_{i\in S}f(i,j)=|C_j| \sum_{j\in G}f(i,j)=|Z_i|
• 因此： \sum_{i\in S}|Z_i|=\sum_{j\in G}|C_j|
• 设 l 个等价类分别为 E_1,\cdots,E_l。
• 原式直接变成： \sum_{p\in G}|C_p|=\sum_{i\in S}|Z_i|=\sum_{i=1}^l|Z_i||E_i|=l|G|
• 证明完毕，对于染色问题（很非形式化的表达）我们还有个小定理。

Pólya 定理

• 给 S 中的元素染个色！假设有 n 种元素，每种元素有 m 种染色方法，设 G 是这 n 种元素的置换群，则染色形成的等价类个数： \frac1{|G|}\sum_{p\in G}T(p)
• 这个怎么理解？咱们当然用上面那个定理，搞一个有 m^n 个元素的集合 S'，然后把映射也挪到上面，变成群 G'。
• 此时答案是： l=\frac 1{|G'|}\sum_{p\in G}|C_p|
• 你发现 |C_p| 很熟悉，就是 T(p)，然后你发现 G' 只是元素变成了更长的排列，大小根本就没变，然后就证完了。
• 等等，如何求 T(p) 呢？还记得循环拆解吗？你发现每个循环必须颜色相同并且只有这个条件，设 d(p) 为 p 置换的循环个数，完整的定理叫做： \frac1{|G|}\sum_{p\in G}m^{d(p)}

习题 1

• 纯纯模板题，你掐指一算，发现循环移位 k 能够拆成 \gcd(k,n) 个循环，所以答案是： \frac1n\sum_{i=1}^nm^{\gcd(i,n)}
• 强行枚举指数（它一定是 n 的约数）我们得到： \frac1n\sum_{d|n}m^d\varphi(n/d)
• 连莫比乌斯反演都不用，真的惊呆了，可以强行使用二次筛法做到亚指数复杂度，代码。
• 一定要注意这个定理只能在成群的条件下使用，否则会出现严重的错误。

习题 2

• 图同构判定都是 Open 的你直接跳到计数？还给出了 n\le 60 的奇葩范围，我也是醉了，果断打表，表，这个表足足给到了 n\le 87，如果你有能耐打它对某个数取模的结果，那也是可以的，代码，当然，这种做法太不讲武德了。
• 这个提示也告诉你只要你掌握了理论上能跑出来的做法就不需要担心常数了（虽然这题加大了难度，还更改了模数，为我们提供了一个先进示范）。
• 容易发现这个问题可以转化成边染色问题，而置换可以理解成对点进行重排，但是这个置换群的大小是 n!，甚至无法逐个枚举。
• 考虑每个点置换形成的一堆环，显然，环的大小分别相同的时候的时候，贡献（这个置换的不动点个数）肯定相同，而环的大小各不相同的情况有多少呢？这个数列（还有这题）告诉我们，大概有 \frac1{4n\sqrt3} e^{\pi\sqrt{2n/3}}，是奇妙的亚指数复杂度，在 n=60 时只有 966467 个状态。
• 问题在对于一堆数如何求它形成的置换个数，由于个数固定，我们可以先组合划分，再求原排列，但是还要考虑相同个数的问题，如果有多个相同的话还要乘回来，这个排列又是固定的，容易算的。
• 问题还在于求这类置换的不动点个数，我们可以暴力并查集染色，也可以利用圆圈，对圈内与圈外分别讨论：对于圈内的边所连两点的最短距离相同的一定在同一个等价类，对于圈外的容易发现它和公约数有关，代码，有色图代码。

习题 3

• 置换是套路的置换，枚举置换然后发现最终还是分成大小为 n/\gcd(n,i) 的环。
• 如果 m/\gcd(n,i) 不是整数，那么显然不存在。
• 你发现或许需要特判。
• 否则，我们需要满足小环的最长子段长度不超过 k。
• 问题是将 m 个白色魔力珠插入到 n 个黑色魔力珠内，使得连续黑色魔力珠长度不超过 k，设方案为 F(n,m)。
• 考虑断环为链，设链上的问题为 G(n,m)，则枚举第一个白魔力珠和最后一个白魔力珠的间隙，问题被转化为： F(n,m)=\sum_{i=0}^k(i+1)G(n-i,m-1)
• 对于链上的问题，不考虑 k 的限制，答案即 C(n+m-1,m)，而如果考虑 k 的限制应该如何？
• 还记得容斥吗？钦定 i 个地方的元素超过 k，那么式子就是： G(n,m)=\sum_{i=0}(-1)^iC(m,i)C(n-i\cdot (k+1)+m-1,m-1)
• 这意味着钦定的位置都被放上了 k+1 个球，容易用 O(n) 的时间复杂度计算 F(n,m)。
• 建议仔细复盘一下组合数学。
• 因此，原问题的复杂度即为 O(n+\sigma_1(\gcd(n,m)))，代码。

习题 4

• 虽然看上去只是加上了一点点限制，但问题的解决的确困难了许多：要求所有点的度数都为偶数。
• 进行套路转换之后，问题变成：在一个置换环下不动的连边方案，仍然要求所有点的度数都为偶数。
• 套路地对环内环间进行讨论，你发现对于环内的情况，只有一种情况，存在一种连边能够改变整个环的奇偶性：环的大小为偶数的时候。
• 而在环间，情况也是类似，即要么不改变，要么就改变整个环所有点的奇偶性。
• 因此，现在问题变成：有 n 个点和一些操作可以翻转点的颜色（翻转一个点或者两个点），问让点颜色不动的翻转方案数，这是一个经典的问题，方法如下：
• 将操作看成边，不连通的情况分开讨论。
• 容易发现边操作不会改变颜色个数的奇偶性，所以点操作总共只能操作偶数个。
• 对于一个连通图，任意找出一棵生成树，首先考虑只对树边进行操作的情况：对于任何一种染色方案，你发现如果有奇数个黑点则不可能染色，而我们总存在恰好一种方案可以贪心地把除了根以外的节点染成白色（从叶节点开始暴力），所以你发现约束条件只有点染色必须在这个连通分量染偶数个，其它的完全没有限制！
• 因此这个问题终于可以完成了！可以通过的复杂度！代码。