资源描述：
《Burnside引理和Polya定理.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、Burnside引理&Polya定理——bywzj1.知识回顾2.若干概念3.Burnside引理4.Polya定理免责申明1.由于本人在此之前不会用ppt(技术比***还渣,我做了一天一夜才做了六张)，所以谢绝吐槽ppt.2.由于本人的表达能力很渣渣，所以请领会精神.3.感谢大家砸场，请在砸场时间内举起板砖.4.谢绝吐槽一切无关内容，谢绝闭目养神.5.如果本章使你世界观崩溃,认知不能等请在砸场时间或课后提出疑问.1.知识回顾群:给定一个集合G={a,b,c,…}和一个运算‘﹫’,并满足以下性质。⑴封闭性：若a,b∈G,则有a﹫b∈G。⑵结合律成立：对于任意a,b,c∈G,恒有(a﹫b)﹫
2、c=a﹫(b﹫c)⑶存在单位元：G中存在单位元e,对任意a∈G,有a﹫e=e﹫a=a⑷存在逆元：对任意a∈G,有b∈G,使a﹫b=b﹫a=e,记b为a-1则称集合G在﹫运算下是一个群。置换:集合G={1,2,…,n}到自身的一个双射函数:p=G→G称为一个n次置换，记作：置换群:结合群和置换的概念，将置换作为集合G的元素，将置换的连接作为运算，就得到了置换群。很简单下面开始今天的学习Sn中任意一个置换p可分解成若干个互不相交的循环的乘积：其中k1+k2+…+kt=n。2.若干概念一.(a).共轭(è)类下面先给出置换群S3,S4。希望同学们有一些启发。S3={(1)(2)(3),(12),
3、(13),(23),(123),(132)}S4={(1)(2)(3)(4),(12),(13),(14),(23),(24),(34),(123),(124),(132),(134),(142),(143),(234),(1234),(1243),(1324),(1342),(1423),(1432),(12)(34),(13)(24),(14)(23)}设其中k阶循环出现的次数为ck，k=1,2,…,n。k阶循环出现ck次用来表示。这样置换p的格式可以表示为：显然有共轭(è)类定义：Sn中有相同格式的置换的全体构成一个共轭类定理：Sn中属于共轭类的元素个数为：大家先自己想一下，为什么是
4、这样(呵)？证明：属于共轭类的置换为：此时我们可以把共轭类的个数看成n的全排列次数n!很明显这样算是有重复的：(1)由于(a1a2…ak)=(a2a3…aka1)=…=(aka1…ak-1)都表示相同的k阶循环，重复了k次。ck个k阶循环重复了次。(2)由互不相交的ck个k阶循环乘积的可交换性引起的，ck个k阶循环重复了ck!次。因此属于共轭类的不同的置换的个数为：练一练：⑴S4中(2)2共轭类中置换的个数为多少？⑵S4中置换的个数为6的共轭类有多少？3个两个砸场时间对于此页前有任何不理解、不明白、没看完或是因本人表述不到位而要砸场的请举起板砖，开砸。NSBBSN(b)k不动置换类设G是[
5、1,n]上的一个置换群，k∈[1,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能互相变换，但不能变到34；同样的34能互相变换，但不能变到12。因此12属于同一类，34属于同一类。注意到k和l属于同一个等价类，或者说Ek=El，当且仅当存在G的某个置换把k变到l。(群的封闭性)对
6、于一般的置换群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不动置换类。则有
7、Ek
8、
9、Zk
10、=
11、G
12、,k=1,2,…nWhy???同学们先自己证明一下(呵呵呵)。证明：假设
13、Ek
14、=l，并不妨设Ek={a1=k,…,al}。记ZkPj={PPj
15、P∈Zk}，则PPj把k变到aj，这表明集合ZkPj(j=1,2,…,l)互不相交。考虑
16、它们在同一个等价类，故存在置换Pj把k变到aj。(1)显然有；(2)对任意p∈G，它必把k变到某个aj，因此pPj-1把k变到k，这说明pPj-1∈Zk，即p=PPj∈ZkPj。因此有故原来如此！Burnside引理：设G={a1,a2,…,ag}是[1,n]上的置换群。把每个置换都写成不相交的循环的乘积。则不同的等价类的个数L为：c1(ak)是在置换ak的作用下不动点的个数。[1,n]在G的作用下被分成一些等价类。3.
