Burnside引理 和 Polya定理
《算法艺术与信息学竞赛》群论、《算法竞赛入门经典（训练指南）》2.6置换及其应用
还未写代码
群的概念：
设G是一个集合，*是G上的二元运算，如果(G,*)满足下面的条件：
封闭性：对于任何a,b∈G,有a*b∈G;
结合律：对任何a,b,c∈G有(a*b)*c=a*(b*c);
单位元：存在e∈G,使得对所有的a∈G,都有a*e=e*a=a;
逆元：对于每个元素a∈G,存在x∈G,使得a*x=x*a=e,这个时候记x为a-1，称为a的逆元，那么则称(G,*)为一个群。
例：G={0,1,2,3,4....n-1}那么它在mod n加法下是一个群。
群元素的个数有限，称为有限群，且其中元素的个数称为阶，记为|G|,群元素的个数无限，称为无限群。
若对于群元素中的任意两个元素a,b都有ab=ba那么称G为交换群，简称Abel群。
=============================================================================================
置换：设X为一个有限集，π是X到X的一个--变换，那么称π是X上的一个置换。
例：设X={1,2,3,4....n},设π是X的一个变换，满足π：1->a1,2->a2,......n->an,其中a1,a2...an是X的一个排列，则称π是X上的一个置换。
可将π记为 1 2 ...... n
a1 a2 ......a n
同一置换用这样的表示法有n!种，但其对应的关系不变。
假设循环π只这样一个置换，满足π：a1->a2,a2->a3,.............ak->a1,但是对于其他元素保持不变，即：a->a,
可将π记为 a1 a2 ...... ak
a2 a3 ...... a1
称为k阶循环，K为循环长度。
每个置换都可以写成若干个互不相交的循环的乘积，且表示是唯一的.
如 1 2 3 4 5 6
2 4 5 1 3 6 ，则可以表示为(124)(35)(6),置换的循环节数是上面的循环个数，上面的例题的循环节数为3.
=============================================================================================
定义：设G是有限集X上的置换群，点a,b∈X称为"等价"的，当且仅当，存在π∈G使得π(a)=b，记为a~b，这种等价条件下，X的元素形成的等价类称为G的轨道，它是集X的一个子集，G的任意两个不同的轨道之交是空集，所以置换群G的轨道全体是集合X的一个划分，构成若干个等价类，等价类的个数记为L。
Zk (K不动置换类)：设G是1…n的置换群。若K是1…n中某个元素，G中使K保持不变的置换的全体，记以Zk，叫做G中使K保持不动的置换类，简称K不动置换类。
Ek(等价类)：设G是1…n的置换群。若K是1…n中某个元素，K在G作用下的轨迹，记作Ek。即K在G的作用下所能变化成的所有元素的集合。.
这个时候有：|Ek|*|Zk|=|G|成立(k=1,2,.....n)。
C(π)：对于一个置换π∈G,及a∈X，若π(a)=a，则称a为π的不动点。π的不动点的全体记为C(π)。例如π=(123)(3)(45)(6)(7)，X={1,2,3,4,5,6,7};那么C(π)={3,6,7}共3个元素。
Burnside引理：L=1/|G|*(Z1+Z2+Z3+Z4+......Zk)=1/|G|*(C(π1)+C(π2)+C(π3)+.....+C(πn))(其中k∈X,π∈G)。
Polya定理：设G={π1，π2，π3........πn}是X={a1，a2，a3.......an}上一个置换群，用m中颜色对X中的元素进行涂色，那么不同的涂色方案数为：1/|G|*(mC(π1)+mC(π2)+mC(π3)+...+mC(πk)). 其中C(πk)为置换πk的循环节的个数。
评论 (0)
