组合数学(25)

1、1第八章第八章 Polya计数法计数法14.1 置换群于对称群置换群于对称群定义：定义： 代数系统（代数系统（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，*）为群。）为群。2 为醒目起见，群中特异元素为醒目起见，群中特异元素e及求逆也常特及求逆也常特 别写出，如别写出，如(G，*)又可记为又可记为(G，*，e )。 (G， *）

2、称谓代数系统是指对）称谓代数系统是指对 a, bG，有有a*bG，即，即G中元素在运算中元素在运算“*”作用下保持作用下保持封闭性。显见正整数连同其上的加法运算构成封闭性。显见正整数连同其上的加法运算构成一代数系统一代数系统, 正整数在减法运算下不构成代数正整数在减法运算下不构成代数系统。系统。 又若仅有又若仅有(1)成立时，称代数系统成立时，称代数系统(G，*)为半群为半群；3若有若有(2)，(3)同时成立，称（同时成立，称（G，*）为幺半群、）为幺半群、 独异点。独异点。 此外，因结合律能保证左逆元就是右逆元，此外，因结合律能保证左逆元就是右逆元，右逆元就是左逆元，故条件右逆元就是左逆元，

3、故条件(3)常改为对常改为对 aG，a有左逆或有左逆或a有右逆。有右逆。 当当G为有限集时，称（为有限集时，称（G，*）为有限群；）为有限群；若若G为无限集，为无限集， 则称（则称（G，*）为无限群。有限）为无限群。有限群中群中G的基数的基数|G|常称为群的阶数。常称为群的阶数。4 为了为了不失一般性，令集合不失一般性，令集合X=1, 2, , n到到 自身的一个双自身的一个双射函数射函数f: XX称为一个称为一个n次次置换，置换， 记作：记作： 我们有：我们有：f(1)=k1; f(2)=k2; . f(n)=kn; 例：例：1,2,3的的3!=6个置换如下：个置换如下：inkifkkknf

4、)(2121或;312321;231321;3213215将将1, 2, , n的所有的所有n!个个置换构成的集合记为置换构成的集合记为Sn于是，于是，S3是由上述例子列出的是由上述例子列出的6个置换组成。个置换组成。 既然置换是函数，它们之间就能进行运算。既然置换是函数，它们之间就能进行运算。如：两个函数的复合，就等价于两个置换的如：两个函数的复合，就等价于两个置换的合成合成;123321;213321;132321nnaaangbbbnf212121;216 f 。g 是按顺序合成：是按顺序合成： (f 。g) (k)= f (g (k) 那么那么f 。g定义了定义了Sn上的一个二元运算，

5、运算上的一个二元运算，运算的结果在的结果在Sn上封闭。上封闭。nnaaanbbbngf21212121ncccngf21217 例：设例：设S4中的置换中的置换f 和和g 为为:13424321;14234321gf求：求：f 。g 和和g 。f :341243211423432113424321214343211342432114234321fggf可以看出，通常情况下合成运算交换律不成立：可以看出，通常情况下合成运算交换律不成立： f 。g g 。f8 我们通常用我们通常用幂运算幂运算来表示一个置换与自身来表示一个置换与自身 的合成运算：的合成运算： f 1 =f , f 2 = f 。f

6、 , f 3 = f 2。f , f 4 = f 3。f , f k = f 。f 。f 。f 。. 。f 。f (k个个)恒等置换恒等置换是各整数与自身的对应，记为是各整数与自身的对应，记为 (k) = k, (k = 1,2, .n)同时有：同时有： f 。= 。f = fnn.21.219逆置换逆置换是将对应中的原象与象互换位置后得到是将对应中的原象与象互换位置后得到 的新的置换。记为的新的置换。记为f 1； 如果如果f (s) = k 那么那么f 1 (k) = s ；例：求例：求S4中的置换中的置换 f 的逆置换的逆置换 。421365654321f 置换中第一行是原象，第二行是象，

7、交换置换中第一行是原象，第二行是象，交换两行后按升序重新排列即得到逆置换：两行后按升序重新排列即得到逆置换：10 显然，置换显然，置换 f 与自身逆置换与自身逆置换f 1的合成是的合成是恒等置换。恒等置换。 f 。f 1 = f 1。f = 如果如果Sn中的置换构成的非空子集中的置换构成的非空子集G满足下满足下列三条性质，则定义它为列三条性质，则定义它为置换群置换群。 2163546543216543214213651f11 i) 封闭性：如果封闭性：如果 f 和和g G, 那么那么f。g G； ii) 单位元：单位元： Sn中的恒等置换中的恒等置换 G ； iii) 逆元：对逆元：对G中的每

8、个置换中的每个置换f ,它的逆它的逆f 1 G ； 集合集合X=1,2,3,n的所有置换构成的集合的所有置换构成的集合Sn是一个置换群，称它为是一个置换群，称它为n阶阶对称群对称群。可以这样说：。可以这样说：给定给定n个元素组成的集合个元素组成的集合X, X上的部分置换所构上的部分置换所构成的群称为成的群称为n次置换群次置换群; X上所有置换构成的群上所有置换构成的群称为称为n次对称群次对称群。对称群是置换群的特殊情况。对称群是置换群的特殊情况。 12 特别地，仅仅含有恒等置换的集合特别地，仅仅含有恒等置换的集合G=是是 一个置换群。一个置换群。 每个置换群满足消去律：每个置换群满足消去律：

9、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 13例：群例：群如右表。不仅如此如右表。不仅如此, 某些部分置换某些部分置换 也可构成群也可构成群, 例如在例如在S3中中, , , 和和都是群。但都是群。但不是群。不是群。14 例例 ： 给定正三角形给定正三角形123(右图右图), 将三角形围绕将三角形围绕 重心重心O旋转旋转, 分别旋转分别旋转0、120、240。可以把每一旋转看可以把每一旋转看成是三角形的顶点成是三角形的顶点集合集合

10、1, 2, 3的置换的置换, 于是有于是有:13215旋转后置换表达式如下：旋转后置换表达式如下： 旋转120后 旋转240 后1 3, 2 1, 3 2; 1 2, 2 3, 3 113223116 )240(213321)120(132321)0(321321651旋转旋转旋转ppp 再将三角形围绕直线再将三角形围绕直线1A、2B、3C翻转。翻转。又得到顶点集合的置换如下又得到顶点集合的置换如下:17 围绕直线围绕直线1A翻转得翻转得: 1,3,2; 围绕直线围绕直线1B翻转得翻转得: 3,2,1; 围绕直线围绕直线1C翻转得翻转得: 2,1,3;得置换如下：得置换如下：)1(231321

11、)2(123321)3(312321432翻转绕翻转绕翻转绕ApBpCp18 正三角形的旋转和翻转在合成运算下可构正三角形的旋转和翻转在合成运算下可构 成群成群, 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的例子：的例子：1.432.321nn19如图所示，如图所示，n实际上就是将原图按顺

12、时针方向实际上就是将原图按顺时针方向 旋转旋转(360/8)度后角点数之间的对应关系。度后角点数之间的对应关系。15678432n实际上可视为将原图按实际上可视为将原图按顺时针方向旋转顺时针方向旋转(360/n)度后角点数之间的对应度后角点数之间的对应关系。关系。 2n实际上为原图实际上为原图的的2(360/n)旋转，更旋转，更一般的有：一般的有：20 当旋转一周后，当旋转一周后， n又重复了。因此又重复了。因此n仅有仅有n个不同的幂个不同的幂:;,.,13210nnnnnn1.1.21.1.21nkknknknkn 当反时针旋转当反时针旋转(360/n)度度后后,我们就有：我们就有：更一般地

13、有：更一般地有：从而从而 是置换群，也是循环群。是置换群，也是循环群。;11nnn1,.2 , 1 , 0;)(1nkknnkn对于),.,(1210nnnnn21 例例(二面体群二面体群) 考虑正考虑正n边形边形(各顶点依次标以各顶点依次标以 1,2., n)上的两类运算上的两类运算:第一类是绕重心第一类是绕重心O(逆时针逆时针)旋转旋转(2k)/n弧度弧度(k=0,1, , n-1)，可产生，可产生n种不同的图案，对应种不同的图案，对应于于X的的n个不同的置换。个不同的置换。第二类是当第二类是当n为奇数时绕各边的中垂线翻转为奇数时绕各边的中垂线翻转180，或当，或当n为偶数时绕各对角线及各

14、对边中为偶数时绕各对角线及各对边中垂线（共垂线（共n条）翻转条）翻转180。从而无论。从而无论n是奇数是奇数22 还是偶数，又可产生还是偶数，又可产生n种不同的图案，种不同的图案， 对应于对应于 X的的n种不同的置换。种不同的置换。 不难发现，以上不难发现，以上2n种置换在相继运动（旋种置换在相继运动（旋转或翻转）下构成一置换群，这类群常称为转或翻转）下构成一置换群，这类群常称为2n阶的阶的二面体群二面体群。 一个几何图形关于它的对称点旋转、对称一个几何图形关于它的对称点旋转、对称轴翻转、对称面反转都看成它在运动。轴翻转、对称面反转都看成它在运动。23例：正方形角点标以例：正方形角点标以1、2

15、、3、4，边标以，边标以a、b、 c、d,那么正方形存在两种类型的那么正方形存在两种类型的8个对称。个对称。1a432dcb围绕正方形中心旋转围绕正方形中心旋转0,90,180, 270,这四个运动都在这四个运动都在平面上平面上,我们称为我们称为平面对称。平面对称。再关于两条对角线、两条中再关于两条对角线、两条中位线翻转得到四个对应置换。位线翻转得到四个对应置换。它们是在空间中进行的。它们是在空间中进行的。24 对平面和空间运动产生的置换描述如下：对平面和空间运动产生的置换描述如下： 1.平面旋转得到的四个置换：平面旋转得到的四个置换：;32144321;21434321;14324321;4

16、3214321342414042.空间翻转得到的四个置换：空间翻转得到的四个置换：;12344321;34124321;41234321;23414321432125 故正方形的角点构成的对称群是：故正方形的角点构成的对称群是： 可以验证，它们中有下列关系：可以验证，它们中有下列关系： 那么我们又可以修改对称群为：那么我们又可以修改对称群为： 同理，我们用边的标示同理，我们用边的标示a,b,c,d替换点对称后也能替换点对称后也能得到边对称群。得到边对称群。,432134241404cG134122143,nn,131412134241404nncG 26 将将前面的结论推广到正前面的结论推广到

17、正n边形上去，我们边形上去，我们 能够得到能够得到n个旋转：个旋转： 和和n个翻转：个翻转： 如果如果n为偶数，则有为偶数，则有 n/2 个关于对角线和个关于对角线和n/2 个个关于中位线的翻转；如果关于中位线的翻转；如果n为奇数，则有为奇数，则有n个个关于角点与对边中点连线的翻转。关于角点与对边中点连线的翻转。关于关于1,2,3,.n的的2n个置换构成群记为：个置换构成群记为：nnnnnn,.,3210n,.,321,.,.,3211241404nnnnD27例例 (四面体群四面体群) 考虑正四面体考虑正四面体(各顶点依次标以各顶点依次标以 1,2,3, 4)，任选一顶点，不妨取，任选一顶点

18、，不妨取4,以以4与与1, 2, 3面的顶垂线为轴面的顶垂线为轴,(逆时针逆时针)旋转旋转2k/3弧度弧度(k=0, 1, 2)可得可得3种不同的图案。种不同的图案。由于四面体有由于四面体有4个顶点，个顶点， 故共可故共可产生产生34=12 种不同的图案，种不同的图案， 这些图案在以上动作（旋转）这些图案在以上动作（旋转）下构成的群称为下构成的群称为四面体群四面体群。432128 显然易见，显然易见， 四面体群的阶是四面体群的阶是12。类似的还有。类似的还有 正六面体、正八面体、正六面体、正八面体、 正十二面体及正正十二面体及正20面体群。面体群。例例(10阶二面体群阶二面体群) 如图所示，正

19、五边形的顶点标如图所示，正五边形的顶点标示以示以1,2,3,4,5。它的对称群。它的对称群 包含包含5个旋转和个旋转和5个翻转，个翻转， 它们分别是：它们分别是：14325295123454321;34512543211234554321;4512354321;2345154321;4321554321;3215454321;2154354321;1543254321;5432154321543214535251505；和30置换中的轮换置换中的轮换 轮换与对换轮换与对换 设设X=1,2,n, X上的任一置换上的任一置换f都联系着一都联系着一个有向图个有向图G=(X, E)，其中，其中i, j

20、X, (i, j)E当且仅当且仅当当f(i)=j。 由于由于f是从是从X到自身的双射函数，故对到自身的双射函数，故对iX，其入度和出度都是其入度和出度都是1。考察序列。考察序列k , f (k), f 2(k), 31 因因X为有限集，故序列中必有重复出现的为有限集，故序列中必有重复出现的 元素，不难证得最早重复出现者必为元素，不难证得最早重复出现者必为k。如若不然，设如若不然，设f t(k)是最早重复出现的元素，即是最早重复出现的元素，即有有f t(k) =f s(k)(1ts)，由最早性知，由最早性知: f t-1(k)fs-1(k)。 但这与但这与f 所具有的性质所具有的性质: ij f

21、(i)f(j)相矛盾。相矛盾。 设设f m(k) = k是最早重复出现的元素，是最早重复出现的元素，32 则称则称k, f(k), f 2(k), , f m(k)是一个是一个轮换轮换，记作，记作:( k f (k) f 2(k) f m-1(k) ) m常称为该轮换的常称为该轮换的长度长度。长度为。长度为2的轮换又称为的轮换又称为对换对换或或换位换位。显见，由。显见，由 f 决定的有向图决定的有向图G=(X, E)的每个连通分支是一个轮换，且的每个连通分支是一个轮换，且f的所有不同的的所有不同的轮换形成集合轮换形成集合X的一个划分。的一个划分。 设设:654213654321f33 则可产生

22、四个轮换则可产生四个轮换: (132)、 (4)、 (5)、 (6)。 置换常记为若干轮换的乘积形式，且如不置换常记为若干轮换的乘积形式，且如不记顺序，这种表示还是惟一的。记顺序，这种表示还是惟一的。 例如例如, f 可记可记为为f=(132)(4)(5)(6)，或更简单的记作，或更简单的记作f=(132)。 上述记法对于直接计算若干置换的乘积上述记法对于直接计算若干置换的乘积是很方便的。是很方便的。 设有如下置换：设有如下置换： f=(134)(26); g=(152)(364) ; h=(1456) 则则f 。g 。h=(134) (26) (152) (364) (1456)34 先看数

23、字先看数字1， 从右向左依次考察各轮换，从右向左依次考察各轮换， 即可得出即可得出1所经历的变换所经历的变换:143334记下（记下（14）；）； 再考察再考察4所经历的变换所经历的变换:455266记下（记下（146）；）； 再考察再考察6所经历的变换所经历的变换:611555接下去是接下去是: 564441 35因此，第一个轮换是（因此，第一个轮换是（1465）；）； 然后取出不在然后取出不在 这个轮换中的最小整数（这里是这个轮换中的最小整数（这里是2），用同），用同样方法作出第二个轮换，即样方法作出第二个轮换，即 22113 336622因此因此 f 。g 。h=(1465) (23)

24、结合以上过程不难给出一般情况下求置换的结合以上过程不难给出一般情况下求置换的不交轮换乘积表示的算法。该算法反过来即为不交轮换乘积表示的算法。该算法反过来即为36置换可表示为不交轮换之积的证明。置换可表示为不交轮换之积的证明。 对置换对置换:)5)(43)(21 (53412543215432154321,5342154312,5431254321 即不在各轮换中出现的元素保持不变。即不在各轮换中出现的元素保持不变。 (1 2), (3 4)及及(5)之间的乘积关系可解释为轮换之间的乘积关系可解释为轮换（即相应置换）间的合成运算。（即相应置换）间的合成运算。 亦即亦即:中的轮换中的轮换(1 2)

25、, (3 4)及及(5)， 可分别独立解释为可分别独立解释为37 更进一步，更进一步， 还可把轮换分解成若干对换之积，还可把轮换分解成若干对换之积， 但这种分解并不惟一，但这种分解并不惟一， 其一般分解可用归纳法其一般分解可用归纳法证明，这里从略。证明，这里从略。 如下仅给出一个例子：如下仅给出一个例子： (4 3 2 1)=(1 2)(1 3)(1 4)=(2 3)(2 4)(2 1) =(2 3)(2 4)(2 1)(1 3)(3 1)53412543215432154321,5342154312,5431254321) 5)(43)(21 (38 虽然轮换虽然轮换(4 3 2 1)可有多个不同形式对换积可有多个不同形式对换积 的分解式，但在这些分解式中，对换因子个的分解式，但在这些分解式中，对换因子个数的奇偶性却是不变的。如数的奇偶性却是不变的。如(4 3 2 1)的各种对的各种对换乘积分解式中对换的数目均为奇数。换乘积分解式中对换的数目均为奇数。 任意置换的阶等于它