群论

正如大家所知，我是一个蒟蒻，所以我滚来学群论了QAQ 群论其实是个很厉害的东西，不知道比反演什么的简单到哪里去了。 啊，学渣苦，学渣累。——Friedrich Taylor

首先我们要知道什么是群。 群的定义：给定一个集合G={a,b,c,…}和集合上的二元运算” ∗ ”,满足以下四条性质： 1.封闭性：∀a,b∈G,∃c∈G,a∗b=c 2.结合律： ∀a,b,c∈G,(a∗b)∗c=a∗(b∗c) 3.单位元： ∃e∈G，∀a∈G,a∗e=e∗a=a 4.逆元： ∀a∈G,∃b∈G,a∗b=b∗a=e,记b=a−1 则称集合G在运算” ∗ ”下是一个群，可以简称为G是群。 顺便普及一下关于群的两个定理 1.如果(G,∗)是群，则 ∀g∈G,g∗G=G∗g=G 其中 g∗G={g∗h|h∈G} 2.如果(G, ∗ )是群，H是G的非空子集，且(H,∗)也是群，那么称H为G的子群。 根据定理2可以判断子集是否为一个子群： HH=H且H−1=H 等价于H是G的子群。

在学习了群的基础概念后，我们还需要一个知识补丁。 n个元素之间的置换 (1a12a23a3......nan) 表示1被1到n中的某个数 a1 取代，直到n被1-n中的某个数 an 取代，且 a1,a2,...,an 互不相同。 置换群的元素是置换，运算是置换连接。 e.g.(13213244)(14233241)=(13213244)(32142341)=(12243341) 貌似我们可以验证置换群的确是群。 具体的简单感性认知如下 1.封闭性： (1a12a2......nan)(a1b1a2b2......anbn)=(1b12b2......nbn) 2.结合律： {(1a12a2......nan)(a1b1a2b2......anbn)}(b1c1b2c2......bncn)=(1a12a2......nan){(a1b1a2b2......anbn)(b1c1b2c2......bncn)} 3.单位元： e=(1122.......nn) 4.逆元： (1a12a2......nan)−1=(a11a22......ann)

我们都知道大名鼎鼎的Polya定理： L=1|G|∑si=1mc(gi) 其中 L 表示本质不同的方案数，|G|表示置换数, c(gi) 表示置换i中循环节的个数,m表示染色的方案数。 首先介绍一下循环的概念： (a1,a2,...,an)=(a1a2a2a3......an−1anana1) 被称为n阶循环 两个循环 (a1,a2,...an) 与 (b1,b2,...bn) 互不相交，当且仅当 ai≠bj ，其中 i,j=1,2,...,n . 例如： (1321324554)=(123)(45) 对于这个置换，其循环节数为2. e.g. 等边三角形三顶点分别用红绿蓝三种颜色着色，有多少种不同的方案？其中的置换操作为： （1）沿中心旋转 0∘ , 120∘ , 240∘ （2）沿三条中线翻转 解：易知对于沿中心旋转 0∘ ，置换为 (112233) ，循环节数为3 沿中心旋转 120∘ ，置换为 (122331) ，循环节数为1 沿中心旋转 240∘ ，置换为 (132132) ，循环节数为1 沿三条中线翻转的置换分别为 (112332) ， (122133) ， (122133) ，循环节数均为2 根据Polya定理可以知道不同的方案数 L 为 16(33+31+31+32+32+32)=10

Burnside引理是群论中的一个结论，可以用来计算等价类的个数，即 L=1|G|∑sj=1D(aj) 其中 D(aj) 表示在置换 aj 下不变的染色方案的个数。 同样我们可以用Burnside引理来解决上述等边三角形的问题 沿中心旋转 0∘ 时，所有的 33 种染色方案均不变 沿中心旋转 120∘ 或 240∘ 时，只有三点颜色相同的染色方案才不变色 分别沿三条中线对折时，分别有 32 种方案不变色 所以L为 16(33+31+31+32+32+32)=10 相信大家都应该发现了：要得到在置换下稳定不动的方案，只需把置换的每个循环节染上相同的颜色即可，所以 D(aj)=mc(aj) 那么我们如何证明Burnside引理呢？ 我们先引进一个定理( x )： |Ek|∗|Zk|=|G|,k=1,2,...,n Ek ：设 G 是1,2,…,n的置换群，若k是1,2,…,n中的某个元素, k 在G作用下的轨迹，即 k 在G作用下能够变化成的所有元素的集合，称之为 k 的等价类。 Zk：设 G 是1,2,…,n的置换群，若k是1,2,…,n中的某个元素, G 中使k保持不变的置换的全体，记做 Zk ，称之为 G 中使k不动的置换类。 我们通过又一个例题来最终”推导”出Burnside引理 e.g. 对2 ∗ 2的方块进行黑白染色，能得到多少不同的图像？ 其中的置换操作为： 旋转0∘,90∘,180∘,270∘ 解：我们很容易根据burnside引理或者是Polya定理亦或是手推都能得到最后的方案一定是6种。那么我们继续无聊但有必要地推导一下： 总方案数： 24 =16种 设方案1为四格均白，则有 |E1|∗|Z1|=1∗4=4 设方案a为只有右上角一个黑格，其馀皆白，则有 |Ea|∗|Za|=4∗1=4 设方案b为右上左下皆为黑格，左上右下均为白格，则有 |Eb|∗|Zb|=2∗2=4 所以定理 x 是可以直观感知的 现在我们推一推Burnside 接下来我们研究每种方案在各个置换下不变的次数之和 设ai为第i种置换,n表示方案数，s表示置换数 设 Sij={0,当ai∉Zj，即方案j在置换ai下变动了1,当ai∈Zj，即方案j在置换ai下保持不变 由 Si,1+Si,2+...Si,n=D(ai) 以及 S1,i+S(2,i)+...+S(s,i)=Zk 由此可得 ∑nj=1Zj=∑si=1∑nj=1Si,j=∑si=1D(ai) 也就是 ∑nj=1Zj=∑si=1D(ai) 或者我们继续假设n个方案中总共有L个等价类 那么 n=E1+E2+...+EL 同时，当 i,j 属于同一等价类时，有 |Zi|=|Zj| 所以可以如是推导： ∑si=1D(ai)=∑nj=1Zj=∑Li=1∑j∈Ei|Zk|=∑Li=1|Ei|∗|Zi|=∑Li=1|G|=L∗|G| 很明显我们求的就是L 所以 L=1|G|∑sj=1D(aj) ,Burnside引理得证

（1）Cipher(Central Europe 1995) 题面见链接(http://poj.org/problem?id=1026 ) 题意：对于一个长度为n的字符串，有一个数组表示第i个字符放到那个位置。输入多个字符串，问这样操作k次后的字符串的形态 题解：暴力肯定是药丸的。 我们可以这样做：对于每个数组，求其循环节，再用总操作数依次模每个字符所在循环节长度后再暴力求解即可

（4）Magic Bracelet(POJ2888) 题面见链接(http://poj.org/problem?id=2888) 题意：n个元素m种颜色，某些颜色不能匹配，求染色方案数对9973取模。其中的置换操作为顺时针旋转 1,2,...n−1 个元素。 题解：因为有限制所以只能用Burnside引理。 但是因为n达到了 109 ，显然不能暴力枚举 观察发现 ∑Ni=1e[gcd(i,N)=k]=ϕ(N/k) 所以我们只需要枚举 1 到n√中能整除 n n的数即可 同时因为n过大我们也需要矩阵快速幂优化 注意这道题卡模运算常数