《burnside引理和polya定理》由会员分享，可在线阅读，更多相关《burnside引理和polya定理（31页珍藏版）》请在金锄头文库上搜索。
1、Burnside引理&Polya定理 by wzj1.知识回顾2.若干概念3. Burnside引理4. Polya定理免责申明1. 由于本人在此之前不会用 ppt( 技术比*还渣,我做了一天一夜才做 了六张)，所以谢绝吐槽 ppt.2. 由于本人的表达能力很渣渣，所以请领会精神.3. 感谢大家砸场，请在砸场时间内举起板砖.4. 谢绝吐槽一切无关内容，谢绝闭目养神.5. 如果本章使你世界观崩溃,认知不能等请在砸场时间或课后提出疑问.1.知识回顾v群: 给定一个集合G= a, b, c, 和一个运算, 并满足以下性质。 v 封闭性：若a,bG, 则有abG。v 结合律成立：对于任意a,b,cG,
2、 恒有(ab)c=a(bc)v 存在单位元：G中存在单位元e, 对任意aG, 有ae=ea=av 存在逆元：对任意aG, 有bG, 使ab=ba=e,记b为a-1v 则称集合G在 运算下是一个群。v置换: 集合G=1, 2, , n 到自身的一个双射函数: p= GG 称为一 个n次置换，记作：v置换群: 结合群和置换的概念，将置换作为集合G的元素，将置换的 连接作为运算，就得到了置换群。Sn中任意一个置换 p可分解成若干个互不相交的 循环的乘积：其中k1+k2+kt=n。2.若干概念一. (a). 共轭()类下面先给出置换群S3 , S4。希望同学们有一些启发 。S3=(1)(2)(3) ,
3、 (1 2) , (1 3) , (2 3) , (1 2 3) , (1 3 2)S4=(1)(2)(3)(4) , (1 2) , (1 3) , (1 4) , (2 3) , (2 4), (3 4) , (1 2 3) , (1 2 4) , (1 3 2) , (1 3 4) , (1 42),(1 4 3), (2 3 4), (1 2 3 4), (1 2 4 3), (1 3 2 4),(1 3 4 2), (1 4 2 3), (1 4 3 2), (1 2)(3 4),(1 3)(2 4),(1 4)(2 3)设其中k阶循环出现的次数为ck，k=1,2,n。k阶循环出现c
4、k次用 来表示。这样置换p的格式可以表示为：显然有共轭()类定义：Sn中有相同格式的置换的全体构成一个共轭类共轭类定理：Sn中属于 共轭类的元素个数为：大家先自己想一下，为什么是这样(呵)？证明：属于 共轭类的置换为： 此时我们可以把共轭类的个数看成n的全排列次数n!很明显这样算是有重复的：(1) 由于(a1a2ak)=(a2a3aka1)=(aka1ak-1)都 表示相同的k阶循环，重复了k次。ck个k阶循环重 复了 次。(2) 由互不相交的ck个k阶循环乘积的可交换性引 起的，ck个k阶循环重复了ck!次。因此属于共轭类的不同的置换的个数为：练一练： S4中(2)2共轭类中置换的个数为多少
5、？ S4中置换的个数为6的共轭类有多少？3个两个对于此页前有任何不理解、不明白、没看完或是 因本人表述不到位而要砸场的请举起板砖，开砸。NSBBSN(b) k不动置换类设G是1,n上的一个置换群，k1,n，G中使k保 持不变的置换全体，称为k不动置换类，记为Zk。定理：置换群G的k不动置换类zk是G的一个子群 。请先自己证明一下此定理(呵呵)证明：(1) 封闭性： (2) 结合律显然；(3) 单位元：G中的单位元显然属于Zk；(4) 逆元：因此Zk是G的一个子群。(c) 等价类考虑G= (1)(2)(3)(4), (12), (34), (12)(34)。在G的作用下，12能互相变换，但不能变
6、到34； 同样的34能互相变换，但不能变到12。因此12属于同一类，34属于同一类。 注意到k和l属于同一个等价类，或者说Ek=El，当 且仅当存在G的某个置换把k变到l。(群的封闭性)对于一般的置换群G，k在G中置换的作用下的轨 迹形成一个封闭的集合，称为等价类，记为Ek。对于上例G= (1)(2)(3)(4), (12), (34), (12)(34)， 显然有E1=E2=1,2，E3=E4=3,4。二. 重要定理定理：设G是1,n上的置换群，Ek是1,n在G的 作用下包含k的等价类，Zk是k不动置换类。则有 |Ek|Zk|=|G|, k=1,2,nWhy?同学们先自己证明一下(呵呵呵)。
7、证明：假设|Ek|=l，并不妨设Ek=a1=k, ,al。记ZkPj =PPj | PZk，则PPj把k变到aj，这表明集合 ZkPj (j=1,2,l)互不相交。考虑它们在同一个等价类，故存在置换Pj把k变到aj。(1) 显然有 ；(2) 对任意pG，它必把k变到某个aj，因此pPj-1把k 变到k，这说明pPj-1Zk，即p=PPjZkPj。因此有故原来如此！Burnside引理：设G=a1,a2,ag是1,n上的置换群。把每个置换都写成不相交的循环的乘积。则不同的等价类的个数L为：c1(ak)是在置换ak的作用下不动点的个数。1,n在G的作用下被分成一些等价类。3.Burnside引理同
8、学们先自己想一下为神马是这样(呵呵呵呵)。先举一个例子验证一下Burnside引理。还是置换群G=e，(12)，(34)，(12)(34)，又有c1(a1)=4，c1(a2)=2，c1(a3)=2，c1(a4)=0，我们已经知道E1=E2=1,2，E3=E4=3,4，即L=2 。ajaj1, k =k, 0, k k.Sjk=故由Burnside引理可知：L=(4+2+2+0)/4=2。如左表分析：其中：1 2 3 4 c1(aj) (1)(2)(3)(4) 1 1 1 1 4 (1) (12)(3)(4) 0 0 1 1 2 (1) (2) (1)(2)(34) 1 1 0 0 2 (1)
9、(2) (12)(34) 0 0 0 0 0 (2)|Zk| 2 2 2 2 8Sjk k aj 42 12 12证明：设：G把1,n分成的L个不同的等价类为 F1,FL，即若i，j同属于一个等价类，则Ei=Ej，故|Ei|=|Ej|。这表明，若i属于某一个等价类Fk，则Ei=Fk。这样又由于|Ei|Zi|=|Ej|Zj|=|G|，可得|Zi|=|Zj|。因此有：这样就证明了Burnside引理。例题1 4个相同格子，用白蓝两种颜色着色，有多 少种不同的方案？经过旋转90或180后相同的方案 算同一种。1. 不动：a1=(1)(2)(16)； 2. 逆90度：a2=(1)(2)(3 4 5 6
10、)(7 8 9 10)(11 12)(13 14 15 16)； 3. 顺90度：a3=(1)(2)(6 5 4 3)(10 9 8 7)(11 12)(16 15 14 13)； 4. 180度：a4=(1)(2)(3 5)(4 6)(7 9)(8 10)(11)(12)(13 15)(14 16)；因此不同的方案数为： (16+2+2+4)/4=6。显然有16种涂色方案,我们设每种为一个元素，而 每一种旋转就是一个置换：这样原问题就转化成了求置换群G=a1,a2,a3,a4的 等价类个数了。对于此页前有任何不理解、不明白、没看完或是 因本人表述不到位而要砸场的请举起板砖，再砸。NSBBSN
11、利用Burnside引理要首先列出所有nm种可能的染色 方案，然后找出在每个置换下保持不变的方案数。显然当m或n很大的时候，这个方法会非常繁琐。我们希望找到其它的方法来计算c1(ak)。 那就是Polya定理3. Polya定理因为我不想再呵了，所以就直接讲证明了。从分析前例开始： a1=(1)(2)(16)； a2=(1)(2)(3 4 5 6)(7 8 9 10)(11 12)(13 14 15 16)；a4=(1)(2)(3 5)(4 6)(7 9)(8 10)(11)(12)(13 15)(14 16)；a3=(1)(2)(6 5 4 3)(10 9 8 7)(11 12)(16 15
12、 14 13)；对于a2和a3，在它们的作用下保持不变的图像是1和2 ，其共同点就是4个格子染同一种颜色(白或蓝)。b a c d而在a4的作用下保持不变的图像是1,2,11,12，其共同 点是对角格子颜色相同(白白、蓝蓝、白蓝、蓝白)。注意到a2,a3,a4分别表示逆时针转90,270,180度 。如果这些旋转是直接作用在棋盘上，对应的置 换为a2=(abcd)，a3=(dcba)，a4=(ac)(bd) 。这表明：在置换ai的作用下保持不变的那些图像， 是在置换ai中同一个循环节内的格子染相同的颜色 所得到的图像。这样如果我们用c(ai)表示置换ai的循环节数，则有其中2代表白蓝两种颜色。
13、一般的如果有n个对象，m种颜色，共有mn种图像。 对于某个转动群，设它作用在这些图像上所对应的 置换群为G=a1,ag，直接作用在染色对象上的置 换群为G=a1,ag，则有这样Burnside引理就变成了如下的Polya定理：定理(Polya定理)：设G是n个对象的一个置换群。 用m种颜色去对这n个对象进行染色，则不同的方案 数为(在置换群G的作用下变成相同的方案算是同一 种方案)：其中G=a1,ag，c(ai)表示置换ai的循环节数。例2 等边三角形的三个顶点用红绿蓝三种颜色来着 色，有多少种不同的方案？保持不变的变换群包括：(1) 沿中心旋转0，120，240度；(2) 沿三条中线的翻转。
14、因此由Polya定理可知不同的方案数为：12 3例3 对正四面体的四个顶点用四种不同的颜色来着 色，有多少种不同的方案？使正四面体重合的运动群包括：因此由Polya定理可知不同的方案数为：12 34(1) 保持不变； (2) 沿过顶点和对面中心点的直 线旋转120，240度； (3) 沿过对边中点的直线旋转180度。即例4 对正六面体的六个面用红蓝两种颜色来着色， 有多少种不同的方案？ 使正六面体的六个面保持不变的运动群包括： (1) 不变置换： (1)(2)(3)(4)(5)(6)； (2) 沿对面中心轴转动90，270度：(3) 沿对面中心轴转动180度：(1)(2 3 4 5)(6)，
15、(1)(5 4 3 2)(6) (同类共6个)；(1)(2 4)(3 5)(6) (同类共3个)； (4) 沿对边中点轴转动180度：(1 6)(2 5)(4 3) (同类共6个) ；(5) 沿对角线轴转动120，240度：(3 4 6)(1 5 2)，(6 4 3)(2 5 1) (同类共8个) 。故例5 对正六面体的八个顶点用两种颜色着色，有多 少种不同的方案？ 使正六面体的八个顶点保持不变的运动群包括： (1) 不变置换： (1)(2)(3)(4)(5)(6)(7)(8)； (2) 沿对面中心轴转动90，270度：(3) 沿对面中心轴转动180度：(1234)(5678)， (4321)(8765) (同类共6个)；(13)(24)
