《离散数学》课件 第17章 群.ppt

*********************************自同态与自同构EndG：G的自同态的集合AutG：G的自同构的集合InnG：G的内自同构的集合内自同构fx：G?G,fx(a)=xax?1关系：InnG?AutG?EndGEndG为独异点AutG为群InnG为AutG的正规子群IG=fe属于InnG实例Z6={0,1,2,3,4,5}，G=Z6,?,fp:Z6?Z6,fp(x)=(px)mod6f0(x)=0,f1=IG,f2(0)=f2(3)=0,f2(1)=f2(4)=2,f2(2)=f2(5)=4f3(0)=f3(2)=f3(4)=0,f3(1)=f3(3)=f3(5)=3f4(0)=f4(3)=0,f4(1)=f4(4)=4,f4(2)=f4(5)=2f5(0)=0,f5(1)=5,f5(2)=4,f5(3)=3,f5(4)=2,f5(5)=1EndG={f0,f1,…,f5}，AutG={f1,f5}InnG={f1}******************************n元置换的轮换指数轮换指数：，Ck(?):k-轮换的个数例如指数为1321314050607080=132131不同指数的个数是如下方程的非负整数解的个数x1+2x2+…+nxn=n例如：A={1,2,3}上的置换?1=(1),?2=(12),?3=(13),?4=(23),?5=(123),?6=(132)轮换指数为13：?1；1121：?2,?3,?4；31：?5,?6*n元置换的对换表示任意轮换都可以表成对换之积对换可以有交表法不唯一，但是对换个数的奇偶性不变奇置换、偶置换奇置换：表成奇数个对换之积偶置换：表成偶数个对换之积奇置换与偶置换之间存在一一对应，因此各有n!/2个?*置换的乘法与求逆置换的乘法：函数的合成例如：8元置换?=(132)(5648)，?=,则??=(15728)(3)(4)(6)=(15728)置换求逆：求反函数?=(132)(5648)，??1=(8465)(231),令Sn为{1,2,…,n}上所有n元置换的集合.Sn关于置换乘法构成群，称为n元对称群.Sn的子群称为n元置换群.例3元对称群S3={(1),(12),(13),(23),(123),(132)}3元交代群A3={(1),(123),(132)}*置换群中元素的阶与子群元素的阶k阶轮换(i1i2…ik)的阶为k?=?1?2…?l是不交轮换的分解式，则|?|=[|?1|,|?2|,…,|?l|]子群{(1)},Sn，n元交代群An例如S3,子群6个(1),S3,(12),(13),(23),A3=(123)*置换群的实例*不同构的图的计数G={(1),(12),(13),(23),(123),(132)}对三角形的边着黑红两色方案数对应了3顶点不同构的图的个数*着色方案构成的轮换在G的作用下着色方案计数，用Polya定理(第23章)可