Together: Find's Blog

关于群论的一些东西

尽管Pólya是一个很偏的东西, 但还是花了两三天的时间大概的学了一下, 搞了两道sgu上的题. 因为没有系统的学, 所以很多东西还是了解的不透彻.

sgu282 Isomorphism
一道用来实践Pólya原理的好题. 给一个有n个结点的完全图, 求用m种颜色染色的不同方案, 重新排列点的序号后重合的方案算一种.

这道题可以很容易看出需要用Pólya原理, 但是不同的置换方案超过52!(每一种点的置换方案唯一的对应一种边的置换方案). 于是我们需要将点置换分类别, 将置换按循环节长度排序, 如(1)(234)(5678)就是一种”格式”为 1-3-4 置换方案, 如果一种置换表示为 s1-s2-s3-…-sk, 显然 s1+s2+s3+…+sk=n. 于是这是n的一个划分. 通过搜索我们知道53的划分并不多. 当有了一个特定的置换”格式”, 我们可以很容易的用组合数学知识算出有多少种对应的点置换, 对于”格式” s1-s2-s3-…-sk, 有 n!/(s1!*s2!*s3!*…*sk!)/(t1*t2*…*tr) * (s1-1)!*(s2-1)!*(s3-1)!*…*(sk-1)! = n!/(s1*s2*s3*…*sk)/(t1*t2*…*tr) 种, 其中t1, t2, …, tr是相邻重复的sk的个数, 如 1-3-3-4-5-5-5-6 就有 t=(1,2,1,3,1). 由于对Pólya原理的理解不对, 我到这儿以为只要将点置换的个数及循环节数套进公式就可以了, 但这是错的, 回想Pólya原理的证明, 它的证明是建立在Burnside定理基础上的, Burnside定理中对象是不同的染色方案, 染色方案是针对边的, 所以在Pólya原理中置换群中的对象也必须是边 (而不是点).

下一个问题是如何通过一个点置换求出它相对应的边置换的循环节数. 可以证明:
1) 一个长度为 s 的点置换循环节对应 [s/2] 个边置换循环节;
2)两个长度分别为 s 和 t 的点置换对应 gcd(s, t) 个边置换循环节.
前者的证明是抓住某一个点为顶点的边出现在边置换中的规律, 后者是根据每一个对应的边置换的长度都是 s 和 t 的最小公倍数证明, 在这儿就不细写了.

还有一个问题, 在模运算中除法是很难做的, 但是在这道题的计算中除法模运算相当的多. 因为 p 是一个大于 n 的素数, 我们可以证明数 a 除以一个数 c 和乘以 c^(p-2) 取模 p 同余, 简证如下:

a * c^(p-2) = a * c^(-1) * c^(p-1)
根据费马小定理, c^(p-1) mod p = 1, 所以 a * c^(p-2) 与 a * c^(-1) 取模p同余.

到这里这个问题就解决了, 将方案数和每个方案的循环节数算出来直接套Pólya原理的公式就可以了, 尽可能多的预处理出需要的数据.

sgu139 Help Needed!
求15数码问题是否有解.

漫天飞的解题报告基本上就是两种解法, 记0到它应在的位置的曼哈顿距离为r, 一种将矩阵看作序列求出逆序对数x, 如果与r同奇偶则有解, 否则无解; 另一种是将每一个不在原位的数字与它原位的数字交换, 统计达到目标需做的交换次数y, 如果与r同奇偶则有解, 否则无解.

两种解法都要考虑 x/y 是否与 r 同奇偶, 我们可以联想到群论中的奇置换和偶置换. 考虑方法2, 它是从两个角度考察置换的奇偶性, 如果奇偶性不同, 显然无解 (奇置换不可能表示成偶置换), 方法1其实和方法2一样, 从某一个数开始按一定的规则与其相邻的数互换直到没有以它为其中一个元素的逆序对, 此时它的相对位置便是正确的, 接着再从当前情况的第一个存在逆序对的数开始做同样的操作, 直接序列中不存在逆序对, 这个在纸上画画也可以找到一定的规则. 到这里, 必要性容易得到, 但充分性呢? 我一直没有想出一个一定可以达到目标的置换方案, 求大牛指点.