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

《polya计数法14置换群于对称群》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十四章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*

2、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的基数

3、G

4、常称为群的阶数。为了不失一般性，令集合X={1,2,…,n}到自

5、身的一个双射函数f:X→X称为一个n次置换，记作：4我们有：f(1)=k1;f(2)=k2;……..f(n)=kn;例：{1,2,3}的3!=6个置换如下：5将{1,2,…,n}的所有n!个置换构成的集合记为Sn于是，S3是由上述例子列出的6个置换组成。既然置换是函数，它们之间就能进行运算。如：两个函数的复合，就等价于两个置换的合成6f。g是按顺序合成：(f。g)(k)=f(g(k))g。f是按顺序合成：(g。f)(k)=g(f(k))那么f。g定义了Sn上的一个二元运算，运算的结果在Sn上封闭。7例

6、：设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我们通常用幂运算来表示一个置换与自身的合成运算：f1=f,f2=f。f,f3=f2。f,f4=f3。f,……fk=f。f。f。f。………..。f。f(k个)9恒等置换是各整数与自身的对应，记为ττ(k)=k,(k=1,2,…..n)同时有:f。τ=τ。f=f逆置换是将对应中的原象与象互

7、换位置后得到的新的置换。记为f–1；如果f(s)=k那么f–1(k)=s；10例：求S4中的置换f的逆置换。置换中第一行是原象，第二行是象，交换两行后按升序重新排列第一行即得到逆置换：11显然，置换f与自身逆置换f–1的合成是恒等置换f。f–1=f–1。f=τ如果Sn中的置换构成的非空子集G满足下列三条性质，则定义它为置换群。i)封闭性：如果f和gG,那么f。gG；ii)单位元：Sn中的恒等置换τG；12iii)逆元：对G中的每个置换f,它的逆元f–1G；集合X={1,2,3,……n}的所有置

8、换构成的集合Sn是一个置换群，称它为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=h14例：{1,2,3}的3!=6个置换如下：由这6个置换构成的集合是：S3={p1,p2,…,p

9、6}在合成运算◇下构成置换群(S3,◇)。15例：群如右表。不仅如此,某些部分置换也可构成群,例如在S3中,<{p1,p2},◇>,<{p1,p3},◇>,<{p1,p4},◇>和<{p1,p5,p6},◇>都是群。但<{p1,p2,p3},◇>不是群。16例：给定正三角形123(右图),将三角形围绕重心O逆时针旋转,分别旋转0°、120°、240°。可以把每一旋转看成是三角形的顶点集合{1,2,3}的置换,于是有:13217旋转后置换表达式如下：旋转120°后旋转240°后13,21

10、,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正三角形的旋转和翻转在合成运算下可构成群,〈S3,◇〉就代表这个群。例：设n是一个正整数,ρn表示{1,2,3,…n}的置换，它定义为：则当i=1,2,….,n-1;时有ρn(i)=i+1且ρn(n)=1。考虑将1到