组合数学群论.ppt

黑板上的排列组合黑板上的排列组合用六种不同颜色涂一用六种不同颜色涂一正方体，一面一色，正方体，一面一色，且每面颜色不同，会且每面颜色不同，会有多少种涂法？有多少种涂法？用六种不同颜色涂一正方体，用六种不同颜色涂一正方体，一面一色，一面一色，不同不同面可以同色面可以同色，，会有多少种涂法？会有多少种涂法？6*5*P(4,4)/4 / 6 = 302第四章 Burnside引理和Pólya定理•组合计数中遇到的困难–找出问题通解的表达式困难•引入母函数–区分讨论的问题类型困难,区分同类性,避免重复和遗漏•容斥原理避免重复计数•如何区分同类•举例–红蓝两种颜色给正方形的四个顶点着色,存在多少种不同的方案? 2 24 4–若允许正方形转动,有多少种方案?•分类：按红色点分类•0个红点 1种•1个红点 1种•2个红点 2种•3个红点 1种•4个红点 1种共共6 6种种3群群(group) 5伽罗华（伽罗华（Galois）•Évariste Galois(1811~1832) •引入群论群论新名词并奠定了群论基础•非常彻底地把全部代数方程可解性问题，转化或归结为置换群及其子群结构分析的问题,得出五次以上一般代数方程根式不可解，以及用圆规、直尺(无刻度的尺)三等分任意角和作倍立方体不可能等结论。

•刘维尔在1846才领悟到其手稿中迸发出的天才思想，他花了几个月的时间试图解释它的意义 •他被公认为数学史上两个最具浪漫主义色彩的人物之一他被公认为数学史上两个最具浪漫主义色彩的人物之一 •他的死使数学的发展被推迟了几十年 •这个人是上帝派来的，在人世间匆匆转了一圈，仅仅21年，却一不小心，开启了数学的一个新时代 ……..–伽罗华在圣佩拉吉监狱中写成的研究报告中写道：“把数学运算归类，学会按照难易程度，而不是按照它们的外部特征加以分类，这就是我所理解的未来数学家的任务，这就是我所要走的道路64.1 群的概念(1)群群(group)(group)定义定义 给定集合G和G上的二元运算 · ，满足下列条件称为群a)封闭性(Closure)：若a,b∈G,则存在c∈G,使得a·b=c.(b)结合律(Associativity)：任意a,b,c∈G,有(a·b)·c=a·(b·c).由于结合律成立，(a·b)·c=a·(b·c)可记做a·b·c.(c)有单位元(Identity)：存在e∈G,任意a∈G.a·e=e·a=a.(d)有逆元(Inverse)：任意a∈G,存在b∈G, a·b=b·a=e. 记为b=a-1. 74.1 群的概念(2) 简单例子例例 G={1,-1}在普通乘法下是群。

证：1)封闭性：1×1=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)逆元素：对任意元素a有(a+(n-a)) mod n = 0 ,a的逆元a-1=n-a84.1 群的概念例例 二维欧氏空间所有刚体旋转T={Ta}构成群其中Ta = cosa sina -sina cosa 证：1)封闭性： 2)结合律：成立(TαTβ)Tγ = Tα(TβTγ) = TαTβTγ 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) cos(a+b)10 0 194.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-1.ab…c = e114.1 群的概念(e) G有限，a∈G，则存在最小正整数r，使得ar = e.且a-1 = ar-1 .证证 设|G|=g,则a,a2 ,…,ag,ag+1∈G,由鸽巢原理其中必有相同项设am =al, 1≤m＜l≤g+1, e=al-m ,1≤l-m≤g，令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(1234) →(4123)12434132134.2 置换群• 置换群是最重要的有限群，所有的有限群都可以用之表示 1 2 … na1 a2 … an•置换：[1,n]到自身的1-1映射称为n阶置换[1,n]目标集上的置换表示为( ), a1a2…an是[1,n]中元的一个排列1 2 3 43 1 2 43 1 4 22 3 4 1•n阶置换共有n!个，同一置换用这样的表示可有n!个表示法例如 p1=( )=( )，n阶置换又可看作[1,n]上的一元运算，一元函数144.2 置换群•置换乘法 P1=( ),P2=( )P1P2=( )( )=( ) P2P1=( )( )=(　　 ).• P2P1≠P1P2.•置换不满足交换律•但是满足结合律1 2 3 43 1 2 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 3154.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 … bn1 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 … n164.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 323174.2 置换群•[1,n]上的所有置换(共n!个)构成一个群，称为n阶对称群(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 3184.3循环、奇循环与偶循环•(a1a2…am)称为m阶循环；(a1a2…am)=(a2a3…ama1)=…=(ama1…am-1)有m种表示方法。

•若两个循环无共同文字，称为不相交的，不相交的循环相乘可交换•如(132)(45)= (45)(132).•若p=(a1a2…an),则pn =(1)(2)…(n)=e.–如p=(123) p2=(321) p3=(1)(2)(3)123454315212345312541234552314•于是( )=(14523) ( )=(132)(45), ( )=(154)(2)(3).a1a2…am-1ama2 a3…am a1•(a1a2…am) = ( ) 称为置换的循环表示Rotate 90o(1234) →(4123)（（1->4->3->2->1)12434132194.3循环、奇循环与偶循环•定理定理 任一置换可表成若干不相交循环的乘积•证证 对给定的任一置换p=( )，从1开始搜索•1→ai1→ai2→…→aik→1得一循环(1 ai1 ai2…aik),•若(1 ai1 … aik)包含了[1,n]的所有文字，则命题成立•否则在余下的文字中选一个，继续搜索,又得一循环直到所有文字都属于某一循环为止。

因不相交循环可交换，故除了各个循环的顺序外，任一置换都有唯一的循环表示1 2 … na1 a2…anppppp204.3循环、奇循环与偶循环•共轭类一般可以把Sn中任意一个置换p分解为若干不相交的循环乘积P=(a1 a2…ak1)(b1 b2…bk2)….(h1 h2…hkl) 其中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)1•Sn中有相同格式的置换全体构成一个共轭类 ∑kCk= n nk=1214.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种表示种表示, (a1a2…ak)=(a2a3…aka1)=…=(aka1…ak-1) Ck个长度为个长度为k的循环重复了的循环重复了kCk次；次；(2)互不相交的互不相交的Ck个循环进行全排列有个循环进行全排列有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)}. •例例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 Cn234.3循环、奇循环与偶循环例例 一副扑克牌，一分为二，交错互相插入(洗牌)，这样操作一次相当于一个置换p。

i =p(i+1)/2,i=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,放28………1272283292652p = (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阶循环阶循环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 3…n-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 3…n-1 n2 3 4…..1 n 2 3…n-1 1=( )( )1 2 3 … n-1 n 2 3…n-1 1 n2 3 4…..1 n 2 3…n-1 n 1=( )( )1 2 3 … n-1 n2 3 4…..n 1=( )=( 1 2 3….n )254.3循环、奇循环与偶循环•任一置换表示成对换的个数的奇偶性是唯一•证明：设f的表达式为设l,k(l

f=∏(xi-xj)i

凸多边形中，如果各边相等且各角也相等，这样的多边形叫做正多边形所谓正多面体，是指多面体的各个面都是全等的正多边形，并且各个多面角都是全等的多面角 任何凸多面体的顶点数任何凸多面体的顶点数v v与面数与面数f f的和都较棱数的和都较棱数e e多多2 2，即，即v v+ +f f- -e e =2=2这就是欧拉定理欧拉定理 304.3循环、奇循环与偶循环 由欧拉定理推出：凸正多面体只有五种凸正多面体只有五种，即：正四面体、正八面体、正二十面体、正六面体（正方体）、正十二面体， 其中正四面体、正八面体和正二十面体的各面都是正三角形，正六面体的各面是正方形，正十二面体的各面是正五边形 v+f-e =4+4-6=2314.3循环、奇循环与偶循环 一个正多面体和以它的各面中心为顶的正多面体，叫做互为对互为对偶的正多面体偶的正多面体正六面体和正八面体是互为对偶的正多面体；正十二面体和正二十面体是互为对偶的正多面体；正四面体的对偶多面体是正四面体 一多面体在空间运动，其运动前后占有同一个空间位置，一切这样的运动的集合，对于以两个这样的运动相继施行作为乘法构成群，称为多面体群多面体群。

由几何学可知，正多面体只有5种,即正四面体、正六面体、正八面体、正十二面体、正二十面体于是有正四面体群、正六（八）面体群、正十二（二十）面体群等三种群 .324.3循环、奇循环与偶循环正四面体群不动旋转: （A)(B)(C)(D)以顶点与对面的中心连线为轴：•A 为顶点(AO1):±120o (A)(BCD) and (A)(BDC)•B为顶点:±120o (B) (ACD) and (B)(ADC) •C为顶点:±120o (C) (ABD) and (C)(ADB) •D为顶点:±120o (D) (ABC) and (D)(ACB)共有8个三项循环以正四面体A-BCD的3对对边之中点联线为旋转轴：作角度为π的3个旋转，分别对应于置换(AB)(CD)，(AC)(BD)，(AD)(BC),这样的12个运动构成群,称为正四面体群正四面体群 e, (BCD),(BDC),(ACD),(ADC)，(ABD)，(ADB)，(ABC)，(ACB) ,(AB)(CD)，(AC)(BD)，(AD)(BC),它与4个文字A、B、C、D上的四次交错群A4同构，因此，四次交错群A4又称为正四面体群 334.3循环、奇循环与偶循环 正八面体群正八面体群或正六面体群正六面体群由24个运动构成群，它与四次对称群S4同构,所以正八面体群与正六面体群是一致的，都是4次对称群S4。

有时把四次对称群称为正八面体群或正六面体群 •正方形顶点二着色只考虑旋转的等价类个数: 6•|G|:置换个数 –只考虑旋转: 4•置换群–Rotate 0 degree: p0=(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)(15)(16)–rotate 90 degree: p1=(1)(2 3 4 5)(6 7)(8 9 10 11)(12 13 14 15)(16)–rotate 180 degree: p2=(1)(2 4)(3 5)(6)(7)(8 10)(9 11)(12 14)(13 15)(16)–rotate 270 degree: p3=((1)(2 5 4 3)(6 7)(8 11 10 9)(12 15 14 13)(16)3412345678910111213141516着色问题的等价类置换pi使图像k变为l，则称k和l属于同一个等价类等价类,置换pi使图像k不变不变354.4 Burnside引理•k不动置换类(Stabilizer) •设G是[1,n]上的一个置换群。

G是Sn的一个子群. k∈[1,n]， G中使k元素保持不变的置换全体，称为k不动置换类，记做Zk.•如G={e,(1 2),(3 4), (1 2)(3 4)}•Z1={e,(3 4)}•Z2={e,(3 4)}•Z3=Z4={e,(1 2)}•如A4={ e,(123),(124),(132),(134),(142), (143), (234), (243), (12)(34), (13)(24), (14)(23)}.–Z1= { e, (234), (243) }–Z2= { e, (134),(143)}–Z3= { e, (124), (142) }–Z4= { e, (123), (132) }364.4 Burnside引理•定理 置换群G的k不动置换类Zk是G的一个子群封闭性：k→k→k,k　　　k. 　结合性：自然有单位元：G的单位元属于Zk.有逆元：P∈Zk,k→k,则k→k,P-1∈Zk.　∴Zk是G的子群.P1 P2P1P2PP-1374.4 Burnside引理•等价类(Orbit)G={(1)(2)(3)(4),(12),(34),(12)(34)}.在G下，1变2，3变4，但1不变3。

Z1=Z2={e,(34)}, Z3=Z4={e,(12)}.•{1,2….n}中的数k，若存在置换pi使k变为l，则称k和l属于同一个等价类,数k所属的等价类记为Ek•一般[1,n]上G将[1,n]分成若干等价类，满足等价类的3个条件.(a)自反性;(b)对称性;(c)传递性•对于A4, ={ e,(123),(124),(132),(134),(142), (143), (234), (243), (12)(34), (13)(24), (14)(23)}.E1=E2={1,2} E3=E4={3 4}E1=E2=E3=E4={1,2,3,4}•正方形顶点二着色只考虑旋转的等价类个数: 6•|G|:置换个数 –只考虑旋转: 4•置换群–Rotate 0 degree: p0=(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)(15)(16)–rotate 90 degree: p1=(1)(2 3 4 5)(6 7)(8 9 10 11)(12 13 14 15)(16)–rotate 180 degree: p2=(1)(2 4)(3 5)(6)(7)(8 10)(9 11)(12 14)(13 15)(16)–rotate 270 degree: p3=((1)(2 5 4 3)(6 7)(8 11 10 9)(12 15 14 13)(16)3812345678910111213141516着色问题的等价类置换pi使图像k变为l，则称k和l属于同一个等价类等价类,置换pi使图像k不变不变Z1={p0, p1, p2, p3}Z2= Z3= Z4= Z5={p0}Z6= Z7= {p0 , p2}|Ek|*|Zk|=|G|?394.4 Burnside引理•定理定理( (Orbit-stabilizer theorem) ) 设G是[1,n]上的一个置换群，Ek是[1,n]在G的作用下包含k的等价类，Zk是k不动置换类。

有|Ek||Zk|=|G|. •证证 设|Ek|=l,Ek={a1(=k),a2,…,al} k=a1→ai, i=1,2,…,l. P={p1,p2,…,pl} 令Gi=Zkpi,i=1,2,…,l.则k在Zkpi的作用下变为ai GiG(G关于Zk的陪集分解)i≠j,Gi∩Gj=Φ. G1+G2+…+Gl   G.　 另一方面，任意p∈G. k→aj→k　 PPj-1∈Zk, P∈ZkPj=Gj.　　　 ∴G G   G1+G1+…+G+Gl l.从而，G=G1+G2+…+Gl.　|G|=|G1|+|G2|+…+|Gl|=|Zkp1|+| Zkp2|+…+| Zkpl| = |Zk|·l= |Zk|·|Ek|PipPj-1404.4 Burnside引理•定义回顾–群用G表示,G中的每个置换表示为ai G={a1,a2….ag}={e,(1 2),(3 4),(1 2)(3 4)}–G中某个置换ai的k阶循环出现的次数为 ck(ai)a1=e=(1)(2)(3)(4) c1(a1) = 4 (1)4a4=(12)(34) c1(a4) = 0 c2(a4) = 2 (2)2–G中使某元素k不动置换类，记做ZkG中的Z1={e,(3 4)}–G中数k所属的等价类记为EkE1=E2={1,2} E3=E4={3,4}•几个常用群对称群Sn交错(交代)群An转动群•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)}. A4={ e,(123),(124),(132),(134),(142), (143), (234), (243), (12)(34), (13)(24), (14)(23)}.•正方形顶点二着色只考虑旋转的等价类个数: 6•|G|:置换个数 –只考虑旋转: 4•置换群–Rotate 0 degree: p0=(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)(15)(16)–rotate 90 degree: p1=(1)(2 3 4 5)(6 7)(8 9 10 11)(12 13 14 15)(16)–rotate 180 degree: p2=(1)(2 4)(3 5)(6)(7)(8 10)(9 11)(12 14)(13 15)(16)–rotate 270 degree: p3=((1)(2 5 4 3)(6 7)(8 11 10 9)(12 15 14 13)(16)4112345678910111213141516着色问题的等价类着色问题的等价类置换置换pi使图像使图像k变为变为l，则称，则称k和和l属于同一个等价类属于同一个等价类,置换置换pi使图像使图像k不变不变Z1={p0, p1, p2, p3}Z2= Z3= Z4= Z5={p0}Z6= Z7= {p0 , p2}|Ek|*|Zk|=|G|定理定理(Orbit-stabilizer theorem) 设设G是是[1,n]上的一个置换群，上的一个置换群，Ek是是[1,n]在在G的作用下的作用下包含包含k的等价类，的等价类，Zk是是k不动置换类。

有不动置换类有|Ek||Zk|=|G|.不动置换和等价类之间的关系不动置换和等价类之间的关系42简单例子•例如，G={e,(12),(34),(12)(34)}.•c1(a1)=4,c1(a2)=2,•c1(a3)=2,c1(a4)=0.•E1=E2={1,2} E3=E4={3,4} •l=[4+2+2+0]/4=2. 1 2 3 4 c1(aj)(1)(2)(3)(4) 1 1 1 1 4 (1)(12)(3)(4) 0 0 1 1 2 (1) (2)(1)(2)(34) 1 1 0 0 2 (1) (2)(12)(34) 0 0 0 0 0 (2) |Zk| → 2 2 2 2 8 Sjk kaj42 12 12•Sjk= 对第对第j行求和得行求和得c1(aj),对第对第k列求和得列求和得|Zk|1, k =k,0, k ≠k.ajaj表中元素的总和表中元素的总和|Ek|*|Zk|=|G|434.4 Burnside引理•一般而言，与上表相仿，有下面表格，其中 Sjk=1, k =k,0, k ≠k.ajaj Sjk kaj 1 2 … n c1(aj) a1 S11 S12 … S1n c1(a1) a2 S21 S22 … S2n c1(a2) … … … … ag Sg1 Sg2 … Sgn c1(ag) |Zk| |Z1||Z2| … |Zn| 44•若j, i同属一个等价类，则Ei=Ej,|Ei|=|Ej| 因因|Ei||Zi|=|G|,故故|Zi|=|Zj|. [1,n]分成分成l个等价类。

个等价类[1,n]=Ea1+Ea2+…+Eal.|Ek||Zk|=|G|.每个等价类中每个等价类中一共一共l个等价类中个等价类中454.4 Burnside引理•Burnside引理(Burnside lemma(1897)–Cauchy(1845)-Frobenius(1887) lemma –Orbit-counting theorem–The result is not due to Burnside himself, who merely quotes it in his book 'On the Theory of Groups of Finite Order', attributing it instead to Frobenius(1887). 设G={a1,a2,…ag}是目标集[1,n]上的置换群每个置换都写成不相交循环的乘积c1(ak)是在置换ak的作用下不动点的个数，也就是长度为1的循环的个数 G将[1,n]划分成l个等价类等价类个数为：464.4 Burnside引理•例例 一正方形分成4格，2着色，有多少种方案？•图象：看上去不同的图形•方案：经过转动相同的图象算同一方案。

图象数总是大于方案数1 2 3 4 5 6 7 89 10 11 12 13 14 15 1647图象与方案•图象:固定不动,物理位置上具有不同染色的即为不同的图象•方案:经过外力变换,可以完全重合的不同图象为同一个方案–内部结构不变–置换:外力产生的变换,如转动,翻转–图象中的等价类48•不动：a1=(1)(2)…(16)•逆时针转90度 ：a2=(1)(2)(3 4 5 6)(7 8 9 10) (11 12)(13 14 15 16)•顺时针转90度 ：a3=(1)(2)(6 5 4 3)(10 9 8 7)(11 12)(16 15 14 13)•转180度：a4=(1)(2)(3 5)(4 6)(7 9)(8 10)(11)(12) (13 15)(14 16)•(16+2+2+4)/4=6(种方案)1 2 3 4 5 6 7 89 10 11 12 13 14 15 16l=[c1(a1)+c1(a2)+…+c1(ag)]/|G|494.4 Burnside引理•针对图像集的转动群来求解•求解2着色的不同方案，可以用Burnside引理•但是当多种颜色着色，理论上可以用Burnside来求解，但是极其复杂Rotate 90o(1234) →(4123)12434132The cyclic group Z26 underlies Caesar's cipher.群魔方群：魔方群：魔方的所有可能魔方的所有可能重新排列形成一个群。

重新排列形成一个群http://www.cse.psu.edu/~yanxi/CourseFall2007.htm 群的发展•群就是对称，研究群，就是研究各种对称性 正规子群正规子群不仅自己是一个群，如果“除”原来的群，得到的也是一个群对原来的群作“除法”得到的群叫商群 单群单群不能被继续分解的群 素数？？素数？？ 能找到所有的单群吗？能找到所有的单群吗？ 1823年发现所谓的交错群An对于所有n>=5都是单群，从而不是可解群 1884年16族有限李群:离散域上的矩阵组成的群 Sophus Lie 挪威数学家菲利克斯菲利克斯·克莱因克莱因德国数学家德国数学家 1872年几何与群的联系 18个有限单群家族+26个单独存在的有限单群 分类结构分析：1872年的Sylow定理使数学家开始明白有限群更深层的结构1892年的Hölder：真正明确提出对有限单群的分类所有的有限单群？ 100年过去了…… 百年的征程•当1983年Gorenstein宣称有限单群分类定理被证明之时，群论学界可是欢呼雀跃•整个证明散落在各期刊的500多篇论文之中，合计过万页，每篇论文都对某种特殊情况进行了处理。

•问题是，他弄错了•他以为一类名为“拟薄群”（quasi-thin group）的类别已经被处理好了，但事实上没有•直到2004年，由Aschbacher和Smith撰写的一篇一千多页的论文才将这个情况完全处理妥当，从而填补了这个漏洞此时，有限单群分类定理，这个有限群理论的圣杯，才正式被圆满证明•18个有限单群家族，再加上26个散在单群，这就是所有的有限单群魔群魔群•最大的散在单群——魔群（Monster Group） •魔群是在1973年被Fischer和Griess分别独立发现的•最大的散在单群，“魔群”这个名字就源于它庞大的体积•魔群的准确元素个数是808017424794512875886459904961710757005754368000000000，也就是大概8*1053个•太阳系的原子个数也就是大约1057个，仅仅高了两个数量级如果我们用线性空间和矩阵变换来表示魔群的话，我们至少需要一个196883维的线性空间， •Griess提出了一个名为Griess代数的代数结构，而魔群恰好就是这个代数结构的自同构群换句话说，魔群恰好刻画了Griess代数的所有对称性•Griess代数的维度是196884，比196883多1。

冥冥中的联系冥冥中的联系•Griess代数的维度是196884，比196883多1•模形式理论中，有一个特殊的函数占据着相当重要的地位，它叫j不变量 •傅立叶级数，其中每个系数都是整数 巧合？联系？ •1979年，Conway和Norton提出了 “魔群月光猜想” （monsterous moonshine ）•存在一个基于魔群的无限维代数结构，通过魔群的不可约线性表示，它恰好给出了j不变量的所有傅立叶系数，而魔群每一个元素在这个代数结构上的作用，都自然地给出了与某个群相关的模形式 •1992年由Brocherds完成证明•证明同时包含了数学和物理，其中用到了弦论中的No-ghost定理来构造证明中必不可少的一个代数结构；•1998年Brocherds由于这个证明获得了菲尔兹奖•通过这个定理架起的桥梁，数学家们也发现了魔群、模函数和弦理论之间更多的千丝万缕的联系•甚至有人过于疯狂地设想，魔群也许就代表着我们这个宇宙终极的对称性 58伽罗华（伽罗华（Galois）•Évariste Galois(1811~1832)•对伽罗华来说，他所提出并为之坚持的理论是一场对权威、对时代的挑战，他的“群”完全超越了当时数学界能理解的观念。

•他的数学考官曾说“这个孩子在表达他的想法时有些困难，但是他十分聪明，并体现出了非凡的学术精神”•过分地追求简洁是导致这一缺憾的原因•当你试图引寻读者远离习以为常的思路进入较为困惑的领域时，清晰性是绝对必需的59ThanksThanks下周交作业下周交作业在讨论超前的问题时务必空前地清晰——笛卡尔•尼耳斯·亨利克·阿贝尔（1802－1829）•研究一般五次方程问题–踌躇满志的阿贝尔自费印刷了证明五次方程不可解的论文（鉴于经费原因，他把内容压缩在了6页上）–高斯见后说：“太疯狂了，居然这么几页纸就解决了数学界的世界难题？！” 人们在高斯死后的遗物中发现阿贝尔寄给他的小册子还没有裁开•椭圆函数–科学院秘书傅立叶读了论文的引言，然后委托勒让得和柯西负责审查柯西把稿件带回家中，究竟放在什么地方，竟记不起来了直到两年以后阿贝尔已经去世，失踪的论文原稿才重新找到，而论文的正式发表，则迁延了12年之久–阿贝尔留下的后继工作，“够数学家们忙上五百年”–阿贝尔死后两天，克雷勒的一封信寄到，告知柏林大学已决定聘请他担任数学教授60•正方形顶点二着色只考虑旋转的等价类个数: 6•|G|:置换个数 –只考虑旋转: 4•c1(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)6112345678910111213141516•l=[c1(a1)+c1(a2)+…+c1(ag)]/|G|。