第十四章Polya计数法置换群于对称群.ppt
《第十四章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及其逆元也常
2、特 别写出,如(G,*)又可记为(G,*,e )。,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
3、个置换如下:,6,将1, 2, , n的所有n!个置换构成的集合记为Sn 于是,S3是由上述例子列出的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
4、1 2,9,可以看出,通常情况下合成运算交换律不成立: 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 。 。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 的逆置换 。,置换中第一行是原象,第二行是
5、象,交换两行后按升序重新排列第一行即得到逆置换:,12,显然,置换 f 与自身逆置换f 1的合成是恒等置换 f 。f 1 = f 1。f = 如果Sn中的置换构成的非空子集G满足下列三条性质,则定义它为置换群。 i) 封闭性:如果 f 和g G, 那么f。g G; ii) 单位元: Sn中的恒等置换G ;,13,iii) 逆元:对G中的每个置换f ,它的逆元 f 1G ; 集合X=1,2,3,n的所有置换构成的集合Sn是一个置换群,称它为n阶对称群。可以这样说:给定n个元素组成的集合X, X上的部分置换所构成的群称为n次置换群; X上所有置换构成的群称为n次对称群。对称群是置换群的特殊情况。,
6、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个置换构成的集合是: S3 =p1, p2, p6 在合成运算下构成置换群(S3, ) 。,16,例:群如右表。不仅如此, 某些部分置换 也可构成群, 例如在S3中, , 和都是群。但 不是群。,17,例 : 给定正三角形123(右图), 将三角形围绕 重心O逆时针旋
7、转, 分别旋转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,1; 围绕直线1C翻转得: 2,1,3;得置换如下:,21,正三角形的旋转和翻转在合成运算下可构 成群, S3, 就代表这个群。 例:设n是一个正整数, n表示1,2,3,n的置换,它定义为:
8、 则当 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个不同的幂:,当反时针旋转(360/n)度后,我们就有: 更一般地有: 从而 是置换群,也是循环群。,24,例(二面体群) 考虑正n边形(各顶点依次标以 1,2., n)上的
9、两类运算: 第一类是绕重心O(逆时针)旋转(2)/n弧度可产生n种不同的图案,对应于X的n个不同的置换。 第二类是当n为奇数时绕各边的中垂线翻转180,或当n为偶数时绕各对角线及各对边中垂线(共n条)翻转180。从而无论n是奇数还是,25,偶数,又可产生n种不同的图案, 对应于X的n种 不同的置换。 不难发现,以上2n种置换在相继运动(旋转或翻转)下构成一置换群,这类群常称为2n阶的二面体群。 一个几何图形关于它的对称点旋转、对称轴翻转、对称面反转都看成它在运动。,26,例:正方形角点标以1、2、3、4,边标以a、b、 c、d,那么正方形存在两种类型的8个对称。,1,a,4,3,2,d,c,b
10、,围绕正方形中心旋转0,90, 180, 270,这四个运动都在平面上,我们称为平面对称。 再关于两条对角线、两条中位线翻转得到四个对应置换。它们是在空间中进行的。,27,对平面和空间运动产生的置换描述如下: 1.平面旋转得到的四个置换:,2.空间翻转得到的四个置换:,28,故正方形的角点构成的对称群是: 可以验证,它们中有下列关系: 那么我们又可以修改对称群为: 同理,我们用边的标示a,b,c,d替换点对称后也能得到边对称群。,29,将前面的结论推广到正n边形上去,我们 能够得到n个旋转: 和n个翻转: 如果n为偶数,则有 n/2 个关于对角线和n/2 个关于中位线的翻转;如果n为奇数,则有
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第十四 Polya 计数 置换 对称
链接地址:https://www.31doc.com/p-2573081.html