《《群置换循环》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《群置换循环》PPT课件.ppt（26页珍藏版）》请在三一办公上搜索。
1、第四章 Polya计数定理,4.1 群、置换、循环4.2 Burnside引理和Polya定理,4.1 群、置换、循环,群的概念 置换群 循环,考虑下面的计数问题：把一个22的方格棋盘用蓝或白两色涂色，如果棋盘可以随意转动，问有多少种不同的涂色方案？,若棋盘固定不动，有24=16种不同的涂色方案。,但当棋盘可转动时，其中的一些方案可以变成另一些方案。,1.群的概念,群论是现代数学非常重要的分支，群论产生的开端非常平凡，但是群论的创立者却充满了传奇。,是二次方程,的求根公式。,我们熟知的公式,人们试图对次数更高的方程得到类似的求解公式。,公元前1600年的巴比伦数学家已知道如何解二次方程，尽管他
2、们没有使用我们现在的代数符号去表达方程及其解。,形如 ax3+bx2+cx+d=0的三次方程的求根公式直至16世纪才被发现，它是由意大利数学家费罗(Ferro)和丰塔那(Fontana)彼此独立得到的。,1545年,卡尔达塔(Cardano)在他的大术(ArsMagna)一书中公开发表了丰塔那的方法。这部书还讲述了费拉里(Ferrari)求解四次方程的方法。,但事情的发展似乎突然停了下来。虽然有很多数学家作出了努力，其中包括18世纪中叶伟大的瑞士数学家欧拉(Euler)，但没有一个人能找出五次方程的求根公式。,拉格朗日(Lagrange)在1770年猜测：这样的求根公式不存在。,1824年，挪
3、威数学家阿贝尔(Abel)证明了拉格朗日的猜想是正确的。,但是虽然没有通用公式，有些特殊的五 次方程有求根公式，那么自然会问：如何判定一个给定的五次方程是否有这样的求根公式？,阿贝尔去世(1829年，26岁)前一直在竭尽全力地研究这个问题。,在这一时期，碰巧还有一位年轻人也在勤奋地钻研这个问题，而且最终取得了成功，他就是伽罗华(Galois)。,可是这位年轻人获得的非凡成果，在他因决斗去世11年后才开始得到数学界的承认。,伽罗华1811年10月降生于巴黎近郊。,14岁那年因考试不及格而重上三年级。,15岁参加声望很高的巴黎高等工科大学的入学考试时，伽罗华失败了，不得不进入普通的师范学校。,就是
4、在这所学校，伽罗华写出了他的第一篇关于连分数的数学论文，显示了他的能力。,他的下两篇关于多项式方程的论文遭到法国科学院的拒绝。更糟的是，两篇论文手稿还莫名其妙地被丢失了。,1829年7月，他在巴黎高等工科大学的入学考试中再次失败.怀着沮丧之情，伽罗华于1830年初又向科学院提交了另一篇论文，这次是为竞争一项数学大奖。,科学院秘书傅立叶(Fourier)将其手稿拿回家去审读，不料在写出评审报告前去世了，此文再也没有找到。,三失手稿，加之考巴黎高等工科大学两度失败，伽罗华遂对科学界产生排斥情绪，变成了学生激进分子，被学校开除。,担任私人辅导教师谋生，但他的数学研究工作依然相当活跃。在这一时期写出了
5、最著名的论文“关于方程可根式求解的条件”，并于1831年1月送交科学院。,到3月，科学院方面仍杳无音讯，于是他写信给院长打听他的文章的下落，结果又如石沉大海。,他放弃了一切希望，参加了国民卫队。在那里和他在数学界一样运气不佳。他刚加入不久，卫队即遭控告阴谋造反而被解散。,在1831年5月10日进行的一次抗议聚宴上，伽罗华手中举着出鞘的刀提议为国王干杯，这一手势被同伙们解释成是要国王的命；第2天他就被捕了。后来被判无罪，并于6月15日获释。,7月4日，他终于打听到他给科学院的那篇论文的命运：因“无法理解”而遭拒绝。审稿人是著名的数学家泊松(Poisson)。,7月14日他又遭逮捕并被判了六个月监
6、禁，因为他在公共场所身着已被解散的国民卫队的制服。,在获释不久，他陷入了与斯特凡妮小姐的恋情。这导致了他的早亡。这次恋爱事件不知何故引出了一场决斗。,1832年5月29日，决斗的前夜，伽罗华写了封很长的信给他的朋友舍瓦利耶(A.Chevalier)，其中大致描述了他的数学理论，从而给数学界留下了唯一一份它将蒙受何等损失的提要。,在第二天的决斗中(离25步远用手枪射击)，伽罗华的胃部中弹，24小时后去世。享年不足21岁。,伽罗华留给世界的最核心的概念是(置换)群，他被公认为是群论的创始人。,给定一个集合G=a,b,c,和集合G上的二元运算，满足如下条件：,1.封闭性：若a,bG，则存在cG使得a
7、b=c；,4.存在逆元：对G的任意元素a，恒有一个bG，使得ab=ba=e，则元素b称为元素a的逆元素，记为a-1。,2.结合律：(ab)c=a(bc)；,3.存在单位元：G中存在一个元素e，使得对于G的任意元素a，恒有 ae=ea=a；,则称集合G在运算之下是一个群，或称G是一个群。,例 G=1,-1在普通乘法下是群。,例 G=0,1,2,n-1在mod n的加法下是群。,例 二维欧式空间中的刚体旋转变换集合Ta构成群，其中,前两例群元素的个数是有限的，称为有限群；后一例群元素的个数是无限的，称为无限群。,有限群G的元素个数叫做群的阶,记做|G|。,若群G的任意二元素a,b恒满足ab=ba，
8、则称G为 交换群，或Abel群。,设G是群，H是G的子集，若H在G原有的运算之下也是一个群，则称为G的一个子群。,置换群是最重要的有限群，所有的有限群都可以用它表示。,置换：1,n到自身的1-1变换：1,n1,n，,p：i ai,(ai aj,i j),于是，a1a2an是1,n 的一个全排列。称此置换为n阶置换，它可如下表示：,2.置换群,置换的乘法运算：设,定义这两个置换的乘法为：,类似有：,显然有,于是我们定义乘法如下：,可以证明，1,n上所有的置换按上述乘法构成一个群，即满足,1.封闭性；,2.结合律；,3.有单位元：,4.有逆元：,称此群为置换群，记为Sn。,例 等边三角形的运动群。
9、绕中心转动0，120，240，绕对称轴翻转。,3.循环,下面介绍一种置换的表示方法：,称为置换的循环表示，或称为m阶循环。,(a1a2am)=(a2a3ama1)=(ama1am-1)都表示同一个置换，共有m种表示方法。,若两个循环无共同文字，则称为不相交的。,不相交的循环相乘可交换。如(132)(45)=(45)(132)。,定理：任一置换可表示为若干不相交循环的乘积。,证明：对给定的置换,从1开始得到一个循环。,若这个循环已包含所有文字，则结束；否则继续从任一文字开始重复上面的过程，直至包含所有的文字。,由于不相交的循环可交换顺序，因此置换的循环表示除了顺序之外是唯一的。,2阶循环称为对换
10、。,定理：任一循环可表示为若干对换的乘积。,例：(1 2 n)=(1 2)(1 3)(1 n)=(2 3)(2 4)(2 n)(2 1)。,其表示并不唯一。,定理：任一置换表示成对换的个数的奇偶性是唯一的。,奇置换：分解成奇数个对换的乘积，偶置换：分解成偶数个对换的乘积。,置换 循环 对换,循环置换的循环长度减1的奇偶性就是它的奇偶性。,定理：Sn中所有偶置换构成一阶为(n!)/2的子群。称为交错群，记做An。,证明：1.封闭性、2.结合律都显然。,3.单位元：注意置换的单位元是偶置换。,4.逆元：注意(i j)-1=(i j)，因此对于一般的偶置换p=(i1 j1)(i2 j2)(ik jk),则 p-1=(ik jk)(i2 j2)(i1 j1)。,令Bn=Sn/An，则|Bn|+|An|=n!。,由(i j)Bn包含于An，有|Bn|An|，,由(i j)An包含于Bn，有|An|Bn|，,因此有：|An|=|Bn|=n!/2。,
