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