《《组合数学群论》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《组合数学群论》PPT课件.ppt（61页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、黑板上的排列组合黑板上的排列组合用六种不同颜色涂一用六种不同颜色涂一正方体，一面一色，正方体，一面一色，且每面颜色不同，会且每面颜色不同，会有多少种涂法？有多少种涂法？用六种不同颜色涂一正方体，用六种不同颜色涂一正方体，一面一色，一面一色，不同面可以同色不同面可以同色，会有多少种涂法？会有多少种涂法？6*5*P(4,4)/4/6=302第四章 Burnside引理和Plya定理组合计数中遇到的困难找出问题通解的表达式困难引入母函数区分讨论的问题类型困难,区分同类性,避免重复和遗漏容斥原理避免重复计数如何区分同类举例红蓝两种颜色给正方形的四个顶点着色,存在多少种不同的方案?2 24 4若允许正方
2、形转动,有多少种方案?分类：按红色点分类0个红点 1种1个红点 1种2个红点 2种3个红点 1种4个红点 1种共共6 6种种3群群(group)5伽罗华（伽罗华（Galois）variste Galois(18111832)引入群论群论新名词并奠定了群论基础非常彻底地把全部代数方程可解性问题，转化或归结为置换群及其子群结构分析的问题,得出五次以上一般代数方程根式不可解，以及用圆规、直尺(无刻度的尺)三等分任意角和作倍立方体不可能等结论。刘维尔在1846才领悟到其手稿中迸发出的天才思想，他花了几个月的时间试图解释它的意义 他被公认为数学史上两个最具浪漫主义色彩的人物之一他被公认为数学史上两个最具
3、浪漫主义色彩的人物之一 他的死使数学的发展被推迟了几十年 这个人是上帝派来的，在人世间匆匆转了一圈，仅仅21年，却一不小心，开启了数学的一个新时代.伽罗华在圣佩拉吉监狱中写成的研究报告中写道：“把数学运算归类，学会按照难易程度，而不是按照它们的外部特征加以分类，这就是我所理解的未来数学家的任务，这就是我所要走的道路。”64.1 群的概念(1)群群(group)(group)定义定义 给定集合G和G上的二元运算 ，满足下列条件称为群。(a)封闭性(Closure)：若a,bG,则存在cG,使得ab=c.(b)结合律(Associativity)：任意a,b,cG,有(ab)c=a(bc).由于结
4、合律成立，(ab)c=a(bc)可记做abc.(c)有单位元(Identity)：存在eG,任意aG.ae=ea=a.(d)有逆元(Inverse)：任意aG,存在bG,ab=ba=e.记为b=a-1.74.1 群的概念(2)简单例子例例 G=1,-1在普通乘法下是群。证：1)封闭性：11=1(-1)(-1)=1(-1)1=-1 1(-1)=-1 2)结合律：成立 3)单位元：1 4)逆元素：1的逆元是1，-1的逆元是-1例例 G=0,1,2,n-1在mod n的加法下是群.证：1)封闭性：除以n的余数只能是0,1,2,n-1，故封闭性成立 2)结合律：成立 3)单位元：0 4)逆元素：对任意
5、元素a有(a+(n-a)mod n=0,a的逆元a-1=n-a84.1 群的概念例例 二维欧氏空间所有刚体旋转T=Ta构成群。其中Ta=cosa sina -sina cosa 证：1)封闭性：2)结合律：成立(TT)T=T(TT)=TTT 3)单位元：T0=4)逆元素：Ta的逆元即T-aTbTa=cosb sinb cosa sina -sinb cosb -sina cosa =cosacosb-sinasinb sinacosb+cosasinb -sinacosb-cosasinb cosacosb-sinasinb =cos(a+b)sin(a+b)=T(b+a)-sin(a+b)c
6、os(a+b)10 0 194.1 群的概念前两例群元素的个数是有限的，所以是有限群；后一例群元素的个数是无限的，所以是无限群。有限群G的元素个数叫做群的阶,记做|G|。设G是群,H是G的子集,若H在G原有的运算之下也是一个群,则称为G的一个子群。若群G的任意二元素a,b恒满足ab=ba。则称G为交换群，或Abel群。104.1 群的概念(a)单位元唯一 e1e2=e2=e1(b)消去律成立 ab=ac b=c,ba=ca b=c(c)每个元的逆元唯一 aa-1=a-1a=e,ab-1=ba-1=e,aa-1=ab-1,a-1=b(d)(ab.c)-1 =c-1 b-1a-1.c-1 b-1a
7、-1.abc=e114.1 群的概念(e)G有限，aG，则存在最小正整数r，使得ar =e.且a-1=ar-1 .证证 设|G|=g,则a,a2,ag,ag+1G,由鸽巢原理其中必有相同项。设am=al,1mlg+1,e=al-m,1l-mg，令l-m=r.则有ar=ar-1a=e.即a-1=ar-1.既然有正整数r使得ar=e,其中必有最小者，不妨仍设为r.r称为a的阶。易见 H=a,a2,ar-1,ar=e在原有运算下也是一个群。12着色问题的等价类红蓝两种颜色给正方形的四个顶点着色,存在多少种不同的方案?2 24 4若允许正方形转动,有多少种方案?转动的表示？Rotate 90o(123
8、4)(4123)12434132134.2 置换群 置换群是最重要的有限群，所有的有限群都可以用之表示。1 2 na1 a2 an置换：1,n到自身的1-1映射称为n阶置换。1,n目标集上的置换表示为(),a1a2an是1,n中元的一个排列。1 2 3 43 1 2 43 1 4 22 3 4 1n阶置换共有n!个，同一置换用这样的表示可有n!个表示法。例如 p1=()=()，n阶置换又可看作1,n上的一元运算，一元函数。144.2 置换群置换乘法 P1=(),P2=()P1P2=()()=()P2P1=()()=().P2P1P1P2.置换不满足交换律但是满足结合律1 2 3 43 1 2
9、41 2 3 43 1 2 41 2 3 44 3 2 13 1 2 42 4 3 11 2 3 42 4 3 11 2 3 44 3 2 14 3 2 14 2 1 31 2 3 44 2 1 3154.2 置换群(1)置换群(permutation group)1,n上的由多个置换组成的集合在上面的乘法定义下构成一个群,则称为置换群。(a)封闭性 ()()=()(b)可结合性()()()=()=()()()(c)有单位元 e=()(d)()-1=()1 2 na1 a2 ana1 a2 anb1 b2 bn1 2 nb1 b2 bn1 2 na1 a2 ana1 a2 anb1 b2 bn
10、1 2 na1 a2 ana1 a2 anb1 b2 bn1 2 nc1 c2 cnb1 b2 bnc1 c2 cnb1 b2 bnc1 c2 cn1 2 n1 2 n1 2 na1 a2 ana1 a2 an1 2 n164.2 置换群例 等边三角形的转动群。不动绕中心转动120o绕对称轴翻转。12 31 2 31 2 3P1=(),1 2 33 1 2P3=(),P2=(),1 2 32 3 11 2 31 3 2P4=(),1 2 33 2 1P5=(),1 2 32 1 3P6=(),12 3 12 3 12 323174.2 置换群1,n上的所有置换(共n!个)构成一个群，称为n阶对
11、称群(Symmetric group)，记做Sn.集合1，2，3的三个元素置换群组成S3注意：一般说1,n上的一个置换群，不一定是指Sn.但一定是Sn的某一个子群。P1=()P2=()P3=()12 3 1 2 3 1 2 31 2 3 2 3 1 3 1 2P4=()P5=()P6=()12 3 1 2 3 1 2 31 3 2 3 2 1 2 1 3184.3循环、奇循环与偶循环(a1a2am)称为m阶循环；(a1a2am)=(a2a3ama1)=(ama1am-1)有m种表示方法。若两个循环无共同文字，称为不相交的，不相交的循环相乘可交换。如(132)(45)=(45)(132).若p=
12、(a1a2an),则pn =(1)(2)(n)=e.如p=(123)p2=(321)p3=(1)(2)(3)123454315212345312541234552314于是()=(14523)()=(132)(45),()=(154)(2)(3).a1a2am-1ama2 a3am a1(a1a2am)=()称为置换的循环表示。Rotate 90o(1234)(4123)（1-4-3-2-1)12434132194.3循环、奇循环与偶循环定理定理 任一置换可表成若干不相交循环的乘积。证证 对给定的任一置换p=()，从1开始搜索1ai1ai2aik1得一循环(1 ai1 ai2aik),若(1
13、ai1 aik)包含了1,n的所有文字，则命题成立。否则在余下的文字中选一个，继续搜索,又得一循环。直到所有文字都属于某一循环为止。因不相交循环可交换，故除了各个循环的顺序外，任一置换都有唯一的循环表示。1 2 na1 a2anppppp204.3循环、奇循环与偶循环共轭类一般可以把Sn中任意一个置换p分解为若干不相交的循环乘积。P=(a1 a2ak1)(b1 b2bk2).(h1 h2hkl)其中k1+k2+kl=n，设k阶循环出现的次数为 ck,用(k)ck表示，则Sn中置换的格式为(1)c1(2)c2(n)cn例：(1)(2 3)(4 5 6 7)的格式是(1)1(2)1(4)1Sn中有
14、相同格式的置换全体构成一个共轭类。kCk=n nk=1214.3循环、奇循环与偶循环定理定理1 Sn中属(1)c1(2)c2 (n)cn共轭类的元素的个数为 n！C1!C2!Cn!1 2 n C1 C2 Cn证证(1)C1(2)C2(n)Cn 即即()()()()()()_/1个个 _/2个个 _/n个个_ _/C1个个_ _/C2个个_ _/Cn个个(1)一个长度为一个长度为k的循环有的循环有k种表示种表示,(a1a2ak)=(a2a3aka1)=(aka1ak-1)Ck个长度为个长度为k的循环重复了的循环重复了kCk次；次；(2)互不相交的互不相交的Ck个循环进行全排列有个循环进行全排列有
15、Ck!种表示种表示.1,2,n的全排列共有的全排列共有n!个，给定一个排列，装入格式得一置换，个，给定一个排列，装入格式得一置换，除以前面的重复度得除以前面的重复度得 n!/(C1!C2!Cn!1C12C2 nCn )个不同的置个不同的置换换.224.3循环、奇循环与偶循环S4=(1)(2)(3)(4),(12),(13),(14),(23),(24),(34),(123),(124),(132),(134),(142),(143),(234),(243),(1234),(1243),(1324),(1342),(1423),(1432),(12)(34),(13)(24),(14)(23).
16、例例4 S4中中(2)2 共轭类有共轭类有4!/(2!22 )=3 (12)(34),(13)(24),(14)(23).(1)1(3)1 共轭类有共轭类有4!/(C1!C3!1131)=8 (123),(124),(132),(134),(142),(143),(234),(243),(1)2(2)1 共轭类有共轭类有4!/(2!1!12 21)=6(12),(13),(14),(23),(24),(34)n！C1!C2!Cn!1 2 n C1 C2 Cn234.3循环、奇循环与偶循环例例 一副扑克牌，一分为二，交错互相插入(洗牌)，这样操作一次相当于一个置换p。i =p(i+1)/2,i=
17、1,3,5,51.i/2+26,i=2,4,6,52.p=(),第i个位置被i 号牌占据.iipp51.5 3 1 52.6 42先放1,再放27,放2,放281272283292652p=(1)(2 27 14 33 17 9 5 3)(4 28 40 46 49 25 13 7)(6 29 15 8 30 41 21 11)(10 31 16 34 43 22 37 19)(12 32 42 47 24 38 45 23)(18 35)(20 36 44 48 50 51 26 39)(52)如此操作多少轮，所有的牌又恢复原顺序？p8=e1阶循环阶循环2个个2阶循环阶循环1个个8阶循环阶循
18、环6个个244.3循环、奇循环与偶循环2阶循环叫做对换定理定理 任一循环都可以表示为对换的积。(1 2 n)=(1 2)(1 3)(1 n)证明：设（1 2 n-1)=(1 2)(1 3)(1 n-1)(1 2 3n-1)(1 n)每个置换的分解形式不是唯一的(1 2 n)=(2 3)(2 4)(2 n)(2 1)(1 2 3)=(12)(13)=(12)(13)(31)(13)1 2 3 n-1 1 2 3n-1 n2 3 4.1 n 2 3n-1 1=()()1 2 3 n-1 n 2 3n-1 1 n2 3 4.1 n 2 3n-1 n 1=()()1 2 3 n-1 n2 3 4.n
19、1=()=(1 2 3.n)254.3循环、奇循环与偶循环任一置换表示成对换的个数的奇偶性是唯一证明：设f的表达式为设l,k(lk)为正整数常数，则有其中A为不含有xk和xl项的部分若将l和k换位，(l k)f=-f 每次对换都改变f的符号，则对应的分解的奇偶性是唯一的。f=(xi-xj)i=5都是单群，从而不是可解群。1884年16族有限李群:离散域上的矩阵组成的群 Sophus Lie 挪威数学家菲利克斯菲利克斯克莱因克莱因德国数学家德国数学家 1872年几何与群的联系 18个有限单群家族+26个单独存在的有限单群 分类结构分析：1872年的Sylow定理。使数学家开始明白有限群更深层的结
20、构1892年的Hlder：真正明确提出对有限单群的分类所有的有限单群？100年过去了 百年的征程当1983年Gorenstein宣称有限单群分类定理被证明之时，群论学界可是欢呼雀跃。整个证明散落在各期刊的500多篇论文之中，合计过万页，每篇论文都对某种特殊情况进行了处理。问题是，他弄错了。他以为一类名为“拟薄群”（quasi-thin group）的类别已经被处理好了，但事实上没有。直到2004年，由Aschbacher和Smith撰写的一篇一千多页的论文才将这个情况完全处理妥当，从而填补了这个漏洞。此时，有限单群分类定理，这个有限群理论的圣杯，才正式被圆满证明。18个有限单群家族，再加上26
21、个散在单群，这就是所有的有限单群。魔群魔群最大的散在单群魔群（Monster Group）魔群是在1973年被Fischer和Griess分别独立发现的。最大的散在单群，“魔群”这个名字就源于它庞大的体积。魔群的准确元素个数是，也就是大概8*1053个。太阳系的原子个数也就是大约1057个，仅仅高了两个数量级。如果我们用线性空间和矩阵变换来表示魔群的话，我们至少需要一个196883维的线性空间，Griess提出了一个名为Griess代数的代数结构，而魔群恰好就是这个代数结构的自同构群。换句话说，魔群恰好刻画了Griess代数的所有对称性。Griess代数的维度是196884，比196883多1
22、。冥冥中的联系冥冥中的联系Griess代数的维度是196884，比196883多1模形式理论中，有一个特殊的函数占据着相当重要的地位，它叫j不变量 傅立叶级数，其中每个系数都是整数 巧合？联系？1979年，Conway和Norton提出了“魔群月光猜想”（monsterous moonshine）。存在一个基于魔群的无限维代数结构，通过魔群的不可约线性表示，它恰好给出了j不变量的所有傅立叶系数，而魔群每一个元素在这个代数结构上的作用，都自然地给出了与某个群相关的模形式。1992年由Brocherds完成证明证明同时包含了数学和物理，其中用到了弦论中的No-ghost定理来构造证明中必不可少的一
23、个代数结构；1998年Brocherds由于这个证明获得了菲尔兹奖。通过这个定理架起的桥梁，数学家们也发现了魔群、模函数和弦理论之间更多的千丝万缕的联系。甚至有人过于疯狂地设想，魔群也许就代表着我们这个宇宙终极的对称性。58伽罗华（伽罗华（Galois）variste Galois(18111832)对伽罗华来说，他所提出并为之坚持的理论是一场对权威、对时代的挑战，他的“群”完全超越了当时数学界能理解的观念。他的数学考官曾说“这个孩子在表达他的想法时有些困难，但是他十分聪明，并体现出了非凡的学术精神”过分地追求简洁是导致这一缺憾的原因。当你试图引寻读者远离习以为常的思路进入较为困惑的领域时，清
24、晰性是绝对必需的。59Thanks下周交作业下周交作业在讨论超前的问题时务必空前地清晰。笛卡尔尼耳斯亨利克阿贝尔（18021829）研究一般五次方程问题踌躇满志的阿贝尔自费印刷了证明五次方程不可解的论文（鉴于经费原因，他把内容压缩在了6页上）高斯见后说：“太疯狂了，居然这么几页纸就解决了数学界的世界难题？！”人们在高斯死后的遗物中发现阿贝尔寄给他的小册子还没有裁开。椭圆函数科学院秘书傅立叶读了论文的引言，然后委托勒让得和柯西负责审查。柯西把稿件带回家中，究竟放在什么地方，竟记不起来了。直到两年以后阿贝尔已经去世，失踪的论文原稿才重新找到，而论文的正式发表，则迁延了12年之久。阿贝尔留下的后继工
25、作，“够数学家们忙上五百年”。阿贝尔死后两天，克雷勒的一封信寄到，告知柏林大学已决定聘请他担任数学教授。60正方形顶点二着色只考虑旋转的等价类个数:6|G|:置换个数 只考虑旋转:4c1(f):不动点个数Rotate 0 degree:(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)(15)(16)rotate 90 degree:(1)(2 3 4 5)(6 7)(8 9 10 11)(12 13 14 15)(16)rotate 180 degree:(1)(2 4)(3 5)(6)(7)(8 10)(9 11)(12 14)(13 15)(16)rotate 270 degree:(1)(2 5 4 3)(6 7)(8 11 10 9)(12 15 14 13)(16)6112345678910111213141516l=c1(a1)+c1(a2)+c1(ag)/|G|