Polya计数法14置换群于对称群

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第十四章 Polya计数法,14.1 置换群于对称群,第9章到13章的知识, 属于离散数学不讲。,定义：(,G,，*)称谓,代数系统,是指对,a, b,G,，有,a*b,G,，即,G,中元素在运算“ * ”作用下保持封闭性。显见正整数连同其上的加法运算构成一代数系统, 正整数在减法运算下不构成代数系统。,1,定义： 代数系统(,G,，*)若满足以下条件： ,(1) 结合律：对,a, b, c,G, (,a*b,)*,c,=,a,*(,b*c,)； (2)有幺元：,e,G,，使对,a,G,，,e*a,=,a*e,=,a,；,(3) 逆元： 对,G,中幺元,e,及,a,G,，,a,-1,G,使,a,-1,*,a,=,a* a,-1,=,e,， 则称(,G,，*)为,群,。,为醒目起见，群中特别元素,e,及其逆元也常特 别写出，如(,G,，*)又可记为(,G,，*，,e,)。,2,又若仅有(1)成立时, 称代数系统(,G,，*)为,半群,;,若有(2)，(3)同时成立，称(,G,，*)为,幺半群,、,或者,独异点,。 ,此外，因结合律能保证左逆元就是右逆元，右逆元就是左逆元，故条件(3)常改为对,a,G,，,a,有左逆元或,a,有右逆元。,3,当,G,为有限集时，称(,G,，*)为,有限群,；若,G,为无,限集， 则称(,G,，*)为,无限群,。有限群中,G,的基数 |,G,| 常称为群的,阶数,。,为了不失一般性，令集合,X,=1, 2, ,n,到自身的一个双射函数,f: X,X,称为一个,n,次置换，记作：,4,我们有：,f,(1)=,k,1,;,f,(2)=,k,2,; .,f,(,n,)=,k,n,;,例：1,2,3的3!=6个置换如下：,5,将,1, 2, ,n,的所有,n,!个置换构成的集合记为,S,n,于是，,S,3,是由上述例子列出的,6个置换组成。,既然置换是函数，它们之间就能进行运算。,如：两个函数的复合，就等价于两个置换的,合成,6,f,。,g,是按顺序合成： (,f,。,g,),(,k,)=,f,(,g,(,k,),g,。,f,是按顺序合成： (,g,。,f,),(,k,)=,g,(,f,(,k,),那么,f,。,g,定义了,S,n,上的一个二元运算，运算的结果在,S,n,上封闭。,7,例：设,S,4,中的置换,f,和,g,为:,求：,f,。,g,和,g,。,f,:,(,g,。,f,),(1)=,g,(,f,(1)=,g,(,3)=3；1,3,3,(,g,。,f,),(4)=,g,(,f,(4)=,g,(,1)=2；4,1,2,8,可以看出，通常情况下合成运算交换律不成立：,f,。,g,g,。,f,我们通,常用,幂运算,来表示一个置换与自身的合成运算：,f,1,=,f,f,2,=,f,。,f,f,3,=,f,2,。,f,f,4,=,f,3,。,f,f,k,=,f,。,f,。,f,。,f,。,.,。,f,。,f,(,k,个),9,恒等置换,是各整数与自身的对应，记为,(,k,) =,k, (,k,= 1,2, .,n,),同时有:,f,。,=,。,f,=,f,逆置换,是将对应中的原象与象互换位置后得到的新的置换。记为,f,1,；,如果,f,(,s,) =,k,那么,f,1,(,k,) =,s,；,10,例：求,S,4,中的置换,f,的逆置换,。,置换中第一行是原象，第二行是象，交换两行后按升序重新排列第一行即得到逆置换：,11,显然，置换,f,与自身逆置换,f,1,的合成是,恒等置换,f,。,f,1,=,f,1,。,f,=,如果,S,n,中的置换构成的,非空子集,G,满足下列三条性质，则定义它为,置换群,。,i) 封闭性：如果,f,和,g,G, 那么,f,。,g,G,；,ii) 单位元：,S,n,中的恒等置换,G,；,12,iii) 逆元：对,G,中的每个置换,f,它的逆元,f,1,G,；,集合,X,=1,2,3,n,的,所有置换,构成的集合,S,n,是一个置换群，称它为,n,阶,对称群,。可以这样说：给定,n,个元素组成的集合,X,X,上的,部分置换,所构成的群称为,n,次置换群,;,X,上,所有置换,构成的群称为,n,次对称群,。对称群是置换群的特殊情况。,13,特别地，仅仅含有恒等置换的集合,G,=,是,一个置换群。,每个置换群满足消去律：,f,。,g,=,f,。,h,g,=,h,对等式左合成,f,1,：,f,1,。(,f,。,g,),=,f,1,。(,f,。,h,),(,f,1,。,f,),。,g,= (,f,1,。,f,),。,h,),。,g,=,。,h,g,=,h,14,例：1,2,3的 3!= 6个置换如下：,由这6个置换构成的集合是：,S,3,=,p,1,p,2,p,6,在合成运算下构成置换群(,S,3, ) 。,15,例：群如右表。不仅如此, 某些部分置换,也可构成群, 例如在,S,3,中, 和都是群。但,不是群。,16,例 ： 给定正三角形123(右图), 将三角形围绕,重心O逆时针旋转, 分别旋转0、120、240。可以把每一旋转看,成是三角形的顶点,集合1, 2, 3的置换,于是有:,1,3,2,17,旋转后置换表达式如下：,旋转120后 旋转240 后,1,3, 2,1, 3,2,; 1,2, 2,3, 3,1,1,3,2,2,3,1,18,再将三角形围绕直线1,A,、2,B,、3,C,翻转。又得到顶点集合的置换如下:,19,围绕直线1,A,翻转得: 1,3,2;,围绕直线1,B,翻转得: 3,2,1;,围绕直线1,C,翻转得: 2,1,3;得置换如下：,20,正三角形的旋转和翻转在合成运算下可构,成群, ,S,3, 就代表这个群。,例：设,n,是一个正整数,n,表示1,2,3,n,的置换，它定义为：,则当,i,=1,2,.,n,-1; 时有,n,(,i,) =,i,+1且,n,(,n,) = 1。考虑将1到,n,的整数均匀地放到正,n,边形的,n,个角点上。我们下面做一个,n,=8的例子：,21,如图所示，,8,实际上就是将原图按顺时针方向,旋转(360/8)度后角点数之间的对应关系。,1,5,6,7,8,4,3,2,8,2,实际上可视为将原图按顺时针方向旋转2,(360/8)度后角点数之间的对应关系。更一般的有：,22,当旋转一周后，,n,又重复了。因此,n,仅有,n,个不同的幂:,当反时针旋转,(360/,n,)度,后,我们就有：,更一般地有：,从而 是置换群，也是,循环群,。,23,例(二面体群) 考虑正,n,边形(各顶点依次标以,1,2.,n,)上的两类运算:,第一类是绕重心O(逆时针)旋转(2,)/,n,弧度可产生,n,种不同的图案，对应于,X,的,n,个不同的置换。,第二类是当,n,为奇数时绕各边的中垂线翻转180，或当,n,为偶数时绕各对角线及各对边中垂线(共,n,条)翻转180。从而无论,n,是奇数还是,24,偶数，又可产生,n,种不同的图案， 对应于,X,的,n,种,不同的置换。 ,不难发现，以上2,n,种置换在相继运动(旋转或翻转)下构成一置换群，这类群常称为2,n,阶的,二面体群,。,一个几何图形关于它的对称点旋转、对称轴翻转、对称面反转都看成它在运动。,25,例：正方形角点标以1、2、3、4，边标以,a,、,b,、,c,、,d,那么正方形存在两种类型的8个对称。,1,a,4,3,2,d,c,b,围绕正方形中心旋转0,90,180, 270,这四个运动都在平面上,我们称为,平面对称,。,再关于两条对角线、两条中位线翻转得到四个对应置换。它们是在空间中进行的。,26,对平面和空间运动产生的置换描述如下：,1.平面旋转得到的四个置换：,2.空间翻转得到的四个置换：,27,故正方形的角点构成的对称群是：,可以验证，它们中有下列关系：,那么我们又可以修改对称群为：,同理，我们用边的标示,a,b,c,d,替换点对称后也能得到边对称群。,28,将前面的结论推广到正,n,边形上去，我们,能够得到,n,个旋转：,和,n,个翻转：,如果,n,为偶数，则有,n,/2 个关于对角线和,n,/2 个关于中位线的翻转；如果,n,为奇数，则有,n,个中垂线的翻转。,关于1,2,3,.,n,的2,n,个置换构成群记为：,29,例 (四面体群) 考虑正四面体(各顶点依次标以,1,2,3, 4)，任选一顶点，不妨取4,以4与1, 2, 3面的顶垂线为轴, (顺时针)旋转2/3弧度可得3种不同的图案。,由于四面体有4个顶点， 故共可产生34=12 种不同的图案， 这些图案在以上动作(旋转)下构成的群称为,四面体群,。,4,3,2,1,30,显然易见， 四面体群的阶是12。类似的还有,正六面体、正八面体、 正十二面体及正20面体群。,例(10阶二面体群) 如图所示，正五边形的顶点标示以1,2,3,4,5。它的对称群,包含5个平面旋转和5个,空间翻转，它们分别是：,1,4,3,2,5,31,32,置换中的循环,循环与对换,设,X,=1,2,n,X,上的任一置换,f,都联系着一个有向图,G,=(,X, E,)，其中,i, j,X,时, (,i, j,),E,当且仅当,f,(,i,)=,j,。即,X,上自身元素的对应。,由于,f,是从,X,到自身的双射函数，故对,i,X,，其入度和出度都是1。考察序列,i,f,(,i,),f,2,(,i,), ,f,m,(,i,) =,i,。(循环对应 ),33,例如：,X,= 1,2,3,8 ,X,上的置换关系,f,是：,其中取,对,i,= 1,，就有：,f,(,i,) =,f,(1) = 6；,f,2,(1) =,f,(,f,(1),=f,(6) =3;,f,3,(1) =,f,(,f,2,(1),=f,(3) = 5;,f,4,(1) =,f,(,f,3,(1),= f,(5) = 1;再合成下去已经构成循环。再,取,对,i,= 2,，又有：,f,(,i,) =,f,(2) = 8；,f,2,(2) =,f,(,f,(2),=f,(8) =7;,f,3,(2) =,f,(,f,2,(2),=f,(7) =2;再合成下去又构成循环。,34,图的顶点关系替代对应关系, 起点是,i, 终点是通过置换得到的,f,(,i,) ：由有向图或者置换关系能够看:1,6,3,5,1；我们可以将这个,小循环,记为,(,1 6 3 5) (无间隔点),1,6,7,2,4,3,8,5,对一般的:称,i,f,(,i,),f,2,(,i,), .,f,m,(,i,)=,i,是置换,f,的一个,循环,，,35,记作: (,i f,(,i,),f,2,(,i,) ,f,m,-1,(,i,),m,常称为该循环的,长度,。长度为2的循环又称为,对换,或,换位,。显见，由,f,决定的有向图,G,=(,X, E,)的每个,连通分支,是一个循环，且,f,的所有不同的循环够成集合,X,的一个,划分,，两个循环中没有相同的元素称为循环,不相交,。, 设:,取蓝色框的元素观察：,1321,；取链中不同,36,的元素可产生四个循环: (132), (4), (5), (6)。,置换常记为若干循环的乘积形式，且如不记顺序，这种表示还是唯一的。 例如,f,可记为,f,=(132)(4)(5)(6)，或更简单的记作,f,=(132);,这种记法是,默认没有出现的元素与自身进行对应,，该记法对于直接计算若干置换的乘积是很方便的。 设有如下置换：,f,=(134)(26);,g,=(152)(364) ;,h,=(1456) 则,-5,-2，-3,37,f,。,g,。,h,=(134) (26) (152) (364) (1456),可以肯定地说(,f,。,g,。,h,)也是一个置换,该置换能被几个循环划分;,先看数字1，从,右,向,左,依次考察各循环， 即可得出1所经历的变换:14,3,3,3,4,记下(14)；每个表示一个括号里的置换,再考察4所经历的变换:,45,5,2,6,6,38,记下(146)； 再考察5所经历的变换:,56,4,4,4,3接下去是: 61,1,5,5,5,因此，第一个循环是(1465)；这个还不包括集合的所有元素,取出不在这个循环中的最小整数(这里是2)，用同样方法作出第二个循环，即: 22,2,1,1,3 继续作: 33,4,4,4,1,因此置换划分成 ：,f,。,g,。,h,=(1465)(23) 后所有元素都出现了，从1到5再从,2,到,3,。,39,结合以上过程不难给出一般情况下求置换的不,相交循环乘积表示的算法。该算法反过来即为置换可表示为不相交循环之积的证明。,对置换:,中的循环(1 2), (3 4)及(5)， 可分别独立解释为,40,即不在各循环中出现的元素自身对应保持不变。,(1 2), (3 4)及(5)之间的乘积关系可解释为循环(即相应置换)间的合成运算。 亦即:,更进一步，还可以把循环分解成若干,对换,的积的形式，但这些分解式太复杂，我们不讲。,41,由循环的基本原理，我们可以得到循环长,度与化为恒等置换的关系；例如：置换,f,中,的循环(132)的长度是3，那么循环(132)与自身3次合成运算后就化为恒等置换。,42,定义：如果置换,f,的,k,次自身合成：,f,k,=,;则称,正整数,k,是,置换的阶,。,定理：任意置换的阶等于它的不相交循环的长,度的最小公倍数,n, (取最大的循环次数)。,事实上，若设,k,l,m,是循环,f,k,f,l, ,f,m,的长度，,k,l,m,的最小公倍数为,n,，且置换,f,能由循环,f,k,f,l, ,f,m,划分，则：,43,即：,f = f,k,。,f,l,。 。,f,m,=(,a,1,a,2,a,k,) 。(,b,1,b,2,b,l,) 。(,c,1,c,2,c,m,),则：,f,n,=,f,n,k,。,f,n,l,。 。,f,n,m,=,。,。 。,=, 故知,f,的阶为,n,。,例:去掉大小王后,52张扑克牌加以编码1,2,52，则这副牌连续洗8次后又恢复到原来牌序。,解:第一次洗牌前可用置换,P,0,表示为:,44,第一次洗牌后用置换,P,1,表示为：,观察第一次洗牌后的置换,P,1,：1单独构成循环；第一行中的奇数原象2,k+,1 (,k,=1,2,3,25)与第二行的象有关系：,45,P,1,( 2,k+,1 ) =,k,+1,第一行中的偶数原象2,k,(,k,=1,2,3,25)对应,第二行的象有关系：,P,1,(2,k,) = 26+,k,所以我们从2开始寻找循环的元素：,2271433179532,先得到,P,1,的两个循环(1)和(2 27 14 33 17 9 5 3); 以此类推，再从4开始寻找循环，(3已出现),46,428404649251374;得到,第三个循环(4 28 40 46 49 25 13 7);,再开始从6寻找循环(1-5已经出现):,629158304121116;得到第三个循环(6 29 15 8 30 41 21 11);同样可以再进行下去得到下列循环：(10 31 16 34 43 22 37 19) ；,(12 32 42 47 24 38 45 23)； (18 35)；, (20 36 44 48 50 51 26 39) ；(52)；,47,我们一共找到九组循环，用这九个循环将,P,1,表 示如下：,P,1,=(1)(2 27 14 33 17 9 5 3)(,4,28 40 46 49 25 13 7),(,6,29 15 8 30 41 21 11)(,10,31 16 34 43 22 37 19),(,12,32 42 47 24 38 45 23) (,18,35), (,20,36 44 48 50 51 26 39) (52),其中，有2个1-循环，1个2-循环，6个8-循环，,48,由于各循环长度的最小公倍数:,(1, 1, 2, 8, 8, 8, 8, 8, 8) = 8，,故知扑克牌洗8 次后又会恢复到原来的牌序。,这使我们明白为什么正规桥牌比赛中，洗牌的次数必须是在3-4次，不得超越。因为洗牌的的目的是要将前次牌型的次序打乱而避免选手拿到相似的牌。,49,总 结,本次课我们复习置换及其置换群的有关知识，并且增加了置换中的循环等概念。,置换群在“离散数学”中讲了一点，这里再学习是为下几次课打基础。,50,本次授课到此结束,作业如下:,P,375,1, 11,1.,设,求：1),f,。,g,；,g,。,f,;,2),f,-1,g,-1,；,51,3),f,2,g,5,；,4),f,。,g,。,f,；,5),g,3,f,。,g,3,。,f,- 1,；,11.求正六边形的顶点对称群。(12阶二面体群D,6,),下次上课内容：14.2 Burnside定理,52,