离散数学ii李占山6.3置换群

1、v 6.3.1 置换的定义置换的定义 v 6.3.2 置换的轮换表法置换的轮换表法 v 6.3.3 置换的顺向圈表示置换的顺向圈表示 v 6.3.4 置换的奇偶性置换的奇偶性 v定义定义. . 设设m是一个非空的有限集合，是一个非空的有限集合，m的的一个一对一变换称为一个一个一对一变换称为一个置换置换。v设设m=a1,a2,an,则则m的置换的置换可简记为可简记为 ，bi=(ai)，i=1,2,n 结论：结论：m的置换共有的置换共有n！个。！个。 m上的置换称为上的置换称为n元置换。元置换。 特别地，特别地， 若若(ai)=ai, i=1,2,n,则则为为n元恒等置换。元恒等置换。 sn: n

2、！个置换作成的集合。！个置换作成的集合。nnbbbaaa2121nnbbbaaa2121设设m=1，2，3，则有，则有3！=6个个3元置换，元置换，所有元素不动：所有元素不动：1一个元素不动：一个元素不动：2 34 0个元素不动：个元素不动：5 6故，故，s3 = 1，2，3，4，5，6321321231321123321312321132321213321对对m中任意元素中任意元素a及及m的任意两个置换的任意两个置换，规定规定（a）=（a）。）。例例. 设设 ，则则= ， = = 43124321214343211243432121344321v满足结合律：满足结合律：()=()，, sn。

3、vsn中有单位元中有单位元: n元恒等置换，设元恒等置换，设为为0，有：，有：0=0 ，snv每个每个n元置换在元置换在sn 中都有逆元素中都有逆元素: = 12121nnbbbaaannaaabbb2121n元置换的全体作成的集合元置换的全体作成的集合sn对置换的乘法作对置换的乘法作成一个群，称为成一个群，称为n 次对称群。次对称群。 n=1，m=a， s1= = 在置换的乘法作成在置换的乘法作成1 1次对称群，为次对称群，为abelabel群。群。 n=2, n=2, m=a，b, s2= , .= , .在置换在置换的乘法作成的乘法作成2 2次对称群，为次对称群，为abelabel群。群

4、。 当当n n 3 3时，时，s sn n不是交换群。不是交换群。 aababaabba轮换轮换. 设设是是m的置换，若可取到的置换，若可取到m的元素的元素a1, ,ar 使使(a1)a2,(a2)=a3,(ar-1)=ar,(ar)=a1，而而不变不变m的其余的元素（自己变换到本身），的其余的元素（自己变换到本身），则则称为一个轮换，称为一个轮换， 记为记为 （a1 a2 ar ） l例 =（134）=（341）=（413） 651423654321)2)(46)(135(416523654321 fm的两个轮换的两个轮换 =(a1ar)和和=(b1bs)说说 是不相杂或不相交，如果是不相杂

5、或不相交，如果 a1,ar和和b1,bs 都不相同都不相同(即即a1, ,arb1,bs= )结论结论：若若和和是是m的两个不相杂的轮换，的两个不相杂的轮换，则则=.证明：证明：设设=（a1ar），），=（b1bs），）， 和和不相杂。命不相杂。命为为m的任意元的任意元若若a1,ar，设，设=ai，则，则 ()=(ai)=(ai)=ai+1， ()=(ai)=(ai+1)= ai+1 。 i=r时时,ai+1应改为应改为a1。 故故,()=()。同理可证，同理可证，若若 b1,bs， ，也有，也有（）=（）。）。设设 a1,ar,b1,bs, 于是，于是， （）=（）=， （）=（）=。 综上

6、，综上，（）=（），故），故 =。 定理定理6 6.3.2 任意置换任意置换恰有一法写成不相杂的恰有一法写成不相杂的轮换乘积。轮换乘积。即，任意置换即，任意置换可以写成不相杂的可以写成不相杂的轮换的乘积（可表性），如果不考虑乘积的顺轮换的乘积（可表性），如果不考虑乘积的顺序，则写法是唯一的序，则写法是唯一的(唯一性唯一性)。证明：证明： （1）可表性。）可表性。设设是是m上置换，任取上置换，任取a1m。若若（a1） = a1，则有轮换（，则有轮换（a1）。）。设设（a1）= a2， （a2）= a3，。由于。由于m有限，故到某一个元素有限，故到某一个元素ar，(ar)必然不必然不能再是新的元素

7、能再是新的元素,即即(ar) a1,ar。由于由于是一对一的，已有是一对一的，已有（ai）= ai+1，i=1，2， ，r-1，所以，所以(ar)只能是只能是a1。于是得到一个轮换（于是得到一个轮换（a1ar）。）。 若若m已经没有另外的元素，则已经没有另外的元素，则就等于这个就等于这个轮换，否则设轮换，否则设b1不在不在a1，ar之内，则同之内，则同样作法又可得到一个轮换（样作法又可得到一个轮换（b1bs）。因）。因为为a1，ar各自已有变到它的元素，所各自已有变到它的元素，所以以b1，bs中不会有中不会有a1，ar出现，即出现，即这两个轮换不相杂。若这两个轮换不相杂。若m的元素已尽，则的元

8、素已尽，则就等于这两个轮换的乘积，否则如上又可就等于这两个轮换的乘积，否则如上又可得到一个轮换。如此类推，由于得到一个轮换。如此类推，由于m有限，有限，最后必得最后必得=(a1ar)(b1bs) (c1ct) (1) 即即表成了不相杂的轮换的乘积。表成了不相杂的轮换的乘积。 （2）唯一性）唯一性.设设又可表为不相杂的轮换的乘积如下：又可表为不相杂的轮换的乘积如下：=(a1ar)(b1bs) (c1ct) (2)考虑考虑(1)(1)式中任意轮换式中任意轮换( (a1ar) )。 不妨设不妨设 a1 a1ar ，且，且a1a。于是，于是，a2=（a1）=（a1）= a2， a3=（a2）=（a2）

9、= a3，证明证明 可见，（可见，（a1ar）必和（）必和（a1ar）完全相同。这就是说，（完全相同。这就是说，（1）中的任意轮）中的任意轮换必出现在（换必出现在（2）中，同样（）中，同样（2）中的任）中的任意轮换必出现在（意轮换必出现在（1）中，因之，（）中，因之，（1）和（和（2）一样，最多排列的方法不同，但）一样，最多排列的方法不同，但不相杂的轮换相乘适合交换律，所以排不相杂的轮换相乘适合交换律，所以排列的次序本来是可以任意颠倒的。列的次序本来是可以任意颠倒的。例例. 设设m m=1，2，3，4，m m的的2424个置换可写个置换可写成：成：i i；(1 2),(1 3),(1 4),(

10、2 3),(2 4),(3 4)(1 2),(1 3),(1 4),(2 3),(2 4),(3 4)；(1 2 31 2 3),(1 3 21 3 2),(1 2 41 2 4),(1 4 21 4 2),(1 3 41 3 4),(1 4 31 4 3),(2 3 42 3 4),(2 4 32 4 3)；(1 2 3 41 2 3 4),(1 2 4 31 2 4 3),(1 3 2 41 3 2 4),(1 31 3 4 2 4 2),(1 4 2 31 4 2 3),(1 4 3 21 4 3 2),(1 2)(3 4),(1 3)(2 4),(1 4)(2 3)(1 2)(3 4)

11、,(1 3)(2 4),(1 4)(2 3)。轮换的长度轮换的长度 其中所含的元素个数。其中所含的元素个数。 （a1a2ar）长度为）长度为r。对换对换 长度为的轮换。长度为的轮换。结论结论. 任意轮换可以写成对换的乘积。任意轮换可以写成对换的乘积。(a1a2ar)(a1ar)(a1ar)(a1 a3)(a1a2) (3)证明：对证明：对r进行归纳，当进行归纳，当r=2时命题显然成立，假设时命题显然成立，假设r=t时结论为真，考虑时结论为真，考虑=(a1a2arat+1)的情况。令的情况。令1=(a1at+1)， 2=(a1a2at)，下面证明，下面证明= 1 2。l任取ls,若l a1,a2

12、,at-1，不妨设l=am,则(l)= (am)=am+1， 1 2(l)= 1 (am+1)=am+1；l若若l=at，则，则(l)=at+1= 1(a1)= 1 (2(at)= l1 2(at)= 1 2(l)；l若若l=at+1，则，则(l)= (at+1)= a1=1 (at+1)= l1 (2(at+1)= 1 2(l)；l若若l a1,a2,at+1，则l(l)=l= 1(l)= 1 (2(l)= 1 2(l)，即，即l= 1 2 =(a1at+1) 2。由归纳假设，。由归纳假设， 2=(a1a2at)，可表为可表为(a1at)(a1at-1)(a1a2)，所以，所以= (a1at

13、+1) (a1at)(a1at-1)(a1a2)，归纳法完成。，归纳法完成。有兴趣的同学可以采用直接证明的方法有兴趣的同学可以采用直接证明的方法进行证明。进行证明。推论推论. 对任意置换，有一法对任意置换，有一法(未必只有一未必只有一法法)可将其写成一些对换的乘积。可将其写成一些对换的乘积。( () )=( (1 2)()(1 3)()(1 3) )=( (2 3)()(1 3)()(2 3) )。先把置换表成不相杂轮换之乘积，然后用先把置换表成不相杂轮换之乘积，然后用一组顺向圈来表示一组顺向圈来表示每个顺向圈的长度，即圈上所含的元素个每个顺向圈的长度，即圈上所含的元素个数，就是该圈所表示的轮

14、换的长度。数，就是该圈所表示的轮换的长度。 一个一个n元置换对应一组顺向圈，这组圈的长元置换对应一组顺向圈，这组圈的长度之总和为度之总和为n；反之，一组顺向圈表示一置；反之，一组顺向圈表示一置换，置换的元素个数就是组中各图长度之换，置换的元素个数就是组中各图长度之总和。总和。 l 1 3l 2 4 n元置换元置换对应图形表达式对应图形表达式 （图型）（图型）g = =1z1 +2z2 + +rzrzi表示长度为表示长度为i的圈的圈, ,而而zi的系数的系数i表示如此的表示如此的zi的个的个数数; ;诸诸为非负整数为非负整数,01n,n=0或或1； 1+22+rr = n niiiz1设设表为表

15、为k个不相杂的轮换的乘积个不相杂的轮换的乘积(包包括长度为括长度为1的轮换在内的轮换在内) )，长度分别为，长度分别为r1，r2，rk。若若 =n-k为奇数（偶数），则称为奇数（偶数），则称为为奇奇置换（偶置换）。置换（偶置换）。例如例如 = =（134）是偶置换）是偶置换 是奇置换是奇置换kjjr1) 1(651423654321)2)(46)(135(416523654321 f因每个长度为因每个长度为r的轮换可写成的轮换可写成r-1个对换的乘个对换的乘积：积：(a1a2ar)(a1ar)(a1ar)(a1 a3)(a1a2) 于是于是可写成可写成 =n-k 个对换的乘积。个对换的乘积。

16、结论：结论：奇置换可表为奇数个对换之积，奇置换可表为奇数个对换之积， 偶置换可表为偶数个对换之积。偶置换可表为偶数个对换之积。 kjjr1) 1(l定理定理6 6.3.3 每个置换都能分解为对换的乘每个置换都能分解为对换的乘积，但偶置换只能分解为偶数个对换的积，但偶置换只能分解为偶数个对换的乘积，奇置换只能分解为奇数个对换的乘积，奇置换只能分解为奇数个对换的乘积。乘积。证明证明. .只只需证明需证明 “只能分解只能分解”。任取任取ssn n，设，设等于等于k个轮换之积，这些个轮换之积，这些轮换分别含轮换分别含r1，r2，rk个元素，于是个元素，于是可以写成可以写成 个对换之积，个对换之积，定义

17、置换定义置换的符号的符号sgnsgn如下：如下： sgnsgn= = kjjr1) 1(kjjr1)1() 1(kjjr1)1() 1( 显然，偶置换的符号为显然，偶置换的符号为1 1，奇置换的符，奇置换的符号为号为-1-1。首先证明首先证明 sgn=sgnsgnsgn=sgnsgn （4 4） 设设等于等于k个个不相杂不相杂轮换之积，轮换之积，等于等于h h个个不相杂轮换之积，且不相杂轮换之积，且写成对换乘积时最写成对换乘积时最后一个对换为（后一个对换为（a ba b）。）。以（以（a ba b）乘）乘而看其变化。而看其变化。(1 1)若若a a和和b b在在的两个不同的轮换之内的两个不同的

18、轮换之内: = =（aaaa1 1a as s）（）（bbbb1 1b bi i） 则则 （abab）= =（aaaa1 1a as sbbbb1 1b bi i） 若若为为h个不相杂轮换之积，则（个不相杂轮换之积，则（abab）为（为（h-1）个）个不相杂轮换之积不相杂轮换之积,故，故，sgnsgn(abab)= = (-1-1)n-(h-1) = -(-1= -(-1)n-h = -sgn= -sgn(2)若若a和和b在在的同一个轮换之内的同一个轮换之内: =（aa1asbb1bi）则（则（ab）=（aa1as）（）（bb1bi） 故，故， sgnsgn(abab)= = (-1-1)n-

19、(h+1) = -(-1= -(-1)n-h = -sgn= -sgn补充证明l(ab)=(ab)(aa1as)(bb1bi)l=.1112111211111211121111121111111isissisiissisiisisisbbbaaaabbaabbbaaabbbaaabbbaaabbabaabbbaaabbbaaabbbaaababbaabbbaaabbabaabbaaba 总之，以一个对换乘总之，以一个对换乘则将则将sgn变号，变号，今今等于（等于（n-k）个对换之积，故以）个对换之积，故以乘乘将将sgn变号（变号（n-k）次，即）次，即sgn= (-1)n-ksgn=sgnsg

20、n因此，因此，和和的奇偶性与其乘积的奇偶性与其乘积的奇偶的奇偶性之关系如下：性之关系如下： 偶偶偶偶= =偶，偶， 奇奇奇奇= =偶，偶， 奇奇偶偶= =奇，奇， 偶偶奇奇= =奇。奇。 因为对换是奇置换，所以只有奇数个因为对换是奇置换，所以只有奇数个对换之积是奇置换，偶数个对换之积是偶对换之积是奇置换，偶数个对换之积是偶置换。置换。 l定理定理6 6.3.4 设设m的元数为的元数为n，若，若n1，则奇置，则奇置换的个数和偶置换的个数相等，都等于换的个数和偶置换的个数相等，都等于 。证明：证明：命命 1，2，m （5）为为m的所有偶置换，由于的所有偶置换，由于n1，故可取到一，故可取到一个对换

21、个对换，而作下列乘积：，而作下列乘积： 1，2，m （6）显然显然i是奇置换，而且诸是奇置换，而且诸i互不相同，互不相同，即（即（6）中无重复元素。反证，若）中无重复元素。反证，若i=j，则以则以-1左乘得左乘得i=j，矛盾，这说明，矛盾，这说明m的的奇置换不少于偶置换奇置换不少于偶置换。2! n 反之，若反之，若为为m的任意奇置换，则的任意奇置换，则-1为偶置换，故必等于某一个为偶置换，故必等于某一个i，-1=i，因而，因而=i，这说明，这说明m的的任意奇置换必在（任意奇置换必在（6）中）中，（，（6）就是）就是m的的所有奇置换，所有奇置换，m的奇置换不多于偶置换。的奇置换不多于偶置换。于是

22、奇置换的个数和偶置换的个数相等，于是奇置换的个数和偶置换的个数相等，各占置换总数各占置换总数n！的一半。！的一半。 定义定义之奇偶性的整数之奇偶性的整数 = n-k称为称为的定性的定性数数。定理定理6.3.5 设设n元置换元置换有图型有图型g=则则之定性数等于之定性数等于=证明证明.n=1+22+rr+nn k=1+2+r+n n-k=2+（r-1）r+（n-1）n =nrrrz1nrrr2) 1(kjjr1) 1(nrrr2) 1(例子l图1是一个22的方格图形，它可以围绕中心旋转，也可以围绕对称轴翻转，但要求经过这样的变动以后的图形要与原来的图形重合（方格中的数字可以改变）。例如，当它绕中心逆l时针旋转900以后，原来的数字1，2，l3，4分别变为2，3，4和1，可以把l这个变化看作是1，2，3，4上的 图1l一个置换（4321）。下面给出所有