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