《組合數(shù)學(xué)群論》PPT課件.ppt

《《組合數(shù)學(xué)群論》PPT課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《《組合數(shù)學(xué)群論》PPT課件.ppt（61頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、黑板上的排列組合,用六種不同顏色涂一正方體，一面一色，且每面顏色不同，會有多少種涂法？,用六種不同顏色涂一正方體，一面一色，不同面可以同色，會有多少種涂法？,6*5*P(4,4)/4 / 6 = 30,2,第四章 Burnside引理和Plya定理,組合計(jì)數(shù)中遇到的困難 找出問題通解的表達(dá)式困難 引入母函數(shù) 區(qū)分討論的問題類型困難,區(qū)分同類性,避免重復(fù)和遺漏 容斥原理避免重復(fù)計(jì)數(shù) 如何區(qū)分同類 舉例 紅藍(lán)兩種顏色給正方形的四個頂點(diǎn)著色,存在多少種不同的方案? 24 若允許正方形轉(zhuǎn)動,有多少種方案? 分類：按紅色點(diǎn)分類 0個紅點(diǎn) 1種 1個紅點(diǎn) 1種 2個紅點(diǎn) 2種 3個紅點(diǎn) 1種 4個紅點(diǎn) 1

2、種,共6種,3,群(group),5,伽羅華（Galois）,variste Galois(18111832) 引入群論新名詞并奠定了群論基礎(chǔ) 非常徹底地把全部代數(shù)方程可解性問題，轉(zhuǎn)化或歸結(jié)為置換群及其子群結(jié)構(gòu)分析的問題,得出五次以上一般代數(shù)方程根式不可解，以及用圓規(guī)、直尺(無刻度的尺)三等分任意角和作倍立方體不可能等結(jié)論。 劉維爾在1846才領(lǐng)悟到其手稿中迸發(fā)出的天才思想，他花了幾個月的時間試圖解釋它的意義 他被公認(rèn)為數(shù)學(xué)史上兩個最具浪漫主義色彩的人物之一 他的死使數(shù)學(xué)的發(fā)展被推遲了幾十年 這個人是上帝派來的，在人世間匆匆轉(zhuǎn)了一圈，僅僅21年，卻一不小心，開啟了數(shù)學(xué)的一個新時代 . 伽羅華在

3、圣佩拉吉監(jiān)獄中寫成的研究報告中寫道：“把數(shù)學(xué)運(yùn)算歸類，學(xué)會按照難易程度，而不是按照它們的外部特征加以分類，這就是我所理解的未來數(shù)學(xué)家的任務(wù)，這就是我所要走的道路?！?6,4.1 群的概念,(1)群(group) 定義 給定集合G和G上的二元運(yùn)算 ，滿足下列條件稱為群。 (a)封閉性(Closure)： 若a,bG,則存在cG,使得ab=c. (b)結(jié)合律(Associativity)： 任意a,b,cG,有(ab)c=a(bc). 由于結(jié)合律成立，(ab)c=a(bc)可記做abc. (c)有單位元(Identity)： 存在eG,任意aG.ae=ea=a. (d)有逆元(Inverse)：

4、任意aG,存在bG, ab=ba=e. 記為b=a-1.,7,4.1 群的概念,(2) 簡單例子 例 G=1,-1在普通乘法下是群。 證：1)封閉性：11=1 (-1)(-1)=1 (-1)1=-1 1(-1)=-1 2)結(jié)合律：成立 3)單位元：1 4)逆元素：1的逆元是1，-1的逆元是-1 例 G=0,1,2,n-1在mod n的加法下是群. 證：1)封閉性：除以n的余數(shù)只能是0,1,2,n-1，故封閉性成立 2)結(jié)合律：成立 3)單位元：0 4)逆元素：對任意元素a有(a+(n-a) mod n = 0 ,a的逆元a-1=n-a,8,4.1 群的概念,證：1)封閉性： 2)結(jié)合律：成立(

5、TT)T = T(TT) = TTT 3)單位元：T0 = 4)逆元素：Ta的逆元即T-a,9,4.1 群的概念,前兩例群元素的個數(shù)是有限的，所以是有限群；后一例群元素的個數(shù)是無限的，所以是無限群。 有限群G的元素個數(shù)叫做群的階,記做|G|。 設(shè)G是群,H是G的子集,若H在G原有的運(yùn)算之下也是一個群,則稱為G的一個子群。 若群G的任意二元素a,b恒滿足ab=ba。則稱G為交換群，或Abel群。,10,4.1 群的概念,單位元唯一 e1e2=e2=e1 消去律成立 ab=ac b=c, ba=ca b=c 每個元的逆元唯一 aa-1=a-1a = e, ab-1 = ba-1 = e , aa-

6、1 = ab-1 , a-1=b (d)(ab.c)-1 = c-1 b-1a-1 . c-1 b-1a-1.abc = e,11,4.1 群的概念,(e) G有限，aG，則存在最小正整數(shù)r，使得ar = e.且a-1 = ar-1 . 證 設(shè)|G|=g,則a,a2 ,ag,ag+1G, 由鴿巢原理其中必有相同項(xiàng)。設(shè)am =al, 1mlg+1, e=al-m ,1l-mg， 令l-m=r.則有ar =ar-1a=e.即a-1=ar-1. 既然有正整數(shù)r使得ar = e,其中必有最小者，不妨仍設(shè)為r. r稱為a的階。易見 H=a,a2 ,ar-1 ,ar =e在原有運(yùn)算下也是一個群。,12,著

7、色問題的等價類,紅藍(lán)兩種顏色給正方形的四個頂點(diǎn)著色,存在多少種不同的方案? 24 若允許正方形轉(zhuǎn)動,有多少種方案? 轉(zhuǎn)動的表示？,Rotate 90o (1234) (4123),1,2,4,3,4,1,3,2,13,4.2 置換群,置換群是最重要的有限群，所有的有限群都可以用之表示。,14,4.2 置換群,置換乘法 P1=( ),P2=( ) P1P2=( )( )=( ) P2P1=( )( )=( ). P2P1P1P2. 置換不滿足交換律 但是滿足結(jié)合律,1 2 3 4 3 1 2 4,1 2 3 4 3 1 2 4,1 2 3 4 4 3 2 1,3 1 2 4 2 4 3 1,1

8、2 3 4 2 4 3 1,1 2 3 4 4 3 2 1,4 3 2 1 4 2 1 3,1 2 3 4 4 2 1 3,15,4.2 置換群,(1)置換群(permutation group) 1,n上的由多個置換組成的集合在上面的乘法定義下構(gòu)成一個群,則稱為置換群。 (a)封閉性 ( )( )=( ) (b)可結(jié)合性 ( )( ) ( ) =( )=( )( ) ( ) (c) 有單位元 e=( ) (d) ( )-1 =( ),1 2 n a1 a2 an,a1 a2 an b1 b2 bn,1 2 n b1 b2 bn,1 2 n a1 a2 an,a1 a2 an b1 b2 bn

9、,1 2 n a1 a2 an,a1 a2 an b1 b2 bn,1 2 n c1 c2 cn,b1 b2 bn c1 c2 cn,b1 b2 bn c1 c2 cn,1 2 n 1 2 n,1 2 n a1 a2 an,a1 a2 an 1 2 n,16,4.2 置換群,例 等邊三角形的轉(zhuǎn)動群。 不動 繞中心轉(zhuǎn)動120o 繞對稱軸翻轉(zhuǎn)。,2,3,17,4.2 置換群,1,n上的所有置換(共n!個)構(gòu)成一個群，稱為n階對稱群(Symmetric group)，記做Sn. 集合1，2，3的三個元素置換群組成S3 注意：一般說1,n上的一個置換群，不一定是指Sn.但一定是Sn的某一個子群。,18

10、,4.3循環(huán)、奇循環(huán)與偶循環(huán),(a1a2am)稱為m階循環(huán)；(a1a2am)=(a2a3ama1)=(ama1am-1)有m種表示方法。 若兩個循環(huán)無共同文字，稱為不相交的，不相交的循環(huán)相乘可交換。 如(132)(45)= (45)(132). 若p=(a1a2an),則pn =(1)(2)(n)=e. 如p=(123) p2=(321) p3=(1)(2)(3),Rotate 90o (1234) (4123) （1-4-3-2-1),1,2,4,3,4,1,3,2,19,4.3循環(huán)、奇循環(huán)與偶循環(huán),定理 任一置換可表成若干不相交循環(huán)的乘積。 證 對給定的任一置換p=( )，從1開始搜索 1

11、ai1ai2aik1得一循環(huán)(1 ai1 ai2aik), 若(1 ai1 aik)包含了1,n的所有文字，則命題成立。 否則在余下的文字中選一個，繼續(xù)搜索,又得一循環(huán)。直到所有文字都屬于某一循環(huán)為止。 因不相交循環(huán)可交換，故除了各個循環(huán)的順序外，任一置換都有唯一的循環(huán)表示。,1 2 n a1 a2an,20,4.3循環(huán)、奇循環(huán)與偶循環(huán),共軛類 一般可以把Sn中任意一個置換p分解為若干不相交的循環(huán)乘積。 P=(a1 a2ak1)(b1 b2bk2).(h1 h2hkl) 其中k1+k2+kl = n，設(shè)k階循環(huán)出現(xiàn)的次數(shù)為 ck,用(k)ck表示，則Sn中置換的格式為 (1)c1(2)c2(n

12、)cn 例：(1)(2 3)(4 5 6 7)的格式是(1)1(2)1(4)1 Sn中有相同格式的置換全體構(gòu)成一個共軛類。,21,4.3循環(huán)、奇循環(huán)與偶循環(huán),定理1 Sn中屬(1)c1(2)c2 (n)cn共軛類的元素的個數(shù)為,證 (1)C1(2)C2(n)Cn 即,()()()() ()(),_ / ,1個,_ / ,2個,_ / ,n個,_ _/ /,C1個,_ _/ /,C2個,_ _/ /,Cn個,(1)一個長度為k的循環(huán)有k種表示, (a1a2ak)=(a2a3aka1)=(aka1ak-1) Ck個長度為k的循環(huán)重復(fù)了kCk次； (2)互不相交的Ck個循環(huán)進(jìn)行全排列有Ck!種表示.

13、 1,2,n的全排列共有n!個，給定一個排列，裝入格式得一置換，除以前面的重復(fù)度得 n!/(C1!C2!Cn!1C12C2 nCn )個不同的置換.,22,4.3循環(huán)、奇循環(huán)與偶循環(huán),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),(

14、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),23,4.3循環(huán)、奇循環(huán)與偶循環(huán),例 一副撲克牌，一分為二，交錯互相插入(洗牌)，這樣操作一次相當(dāng)于一個置換p。,51 . . . 5 3 1,52 . . . 6 4 2,先放1,再放27,放2,放28,1,27,2,28,3,29,26,52,p = (1) (2 27 14

15、 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) 如此操作多少輪，所有的牌又恢復(fù)原順序？ p8 = e,1階循環(huán)2個 2階循環(huán)1個 8階循環(huán)6個,24,4.3循環(huán)、奇循環(huán)與偶循環(huán),2階循環(huán)叫做對換 定理 任一循環(huán)都可以表示為對換的積。 (1 2 n)=(1 2)(1 3)(1 n) 證明：設(shè)（1 2 n-1) = (1 2) (1 3) (1

16、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 ),25,4.3循環(huán)、奇循環(huán)與偶循環(huán),任一置換表示成對換的個數(shù)的奇偶性是唯一 證明：設(shè)f的表達(dá)式為 設(shè)l,k(lk)為正整數(shù)常數(shù)，則有 其中A為不含有xk和xl項(xiàng)的部分 若將l和k換位，(l k)f = -f 每次對換都改變f的符號，則對應(yīng)的分解的奇偶性是唯一的。,26,4.3循環(huán)、奇循環(huán)與偶循環(huán),置換分成兩大類：奇置換與偶置換。 若一個置換能分解為奇數(shù)個換位之積，則為

17、奇置換，若可以分解為偶數(shù)個換位之積，則為偶置換。 S = (1)(25)(37)(46) 3個換位，奇置換 S = (1) (2) (3) (4) (5) 0個換位，偶置換,27,4.3循環(huán)、奇循環(huán)與偶循環(huán),例 0表示空格 有些布局通過左圖偶數(shù)次換位得到，有些是奇數(shù)次換位得到，但奇數(shù)次換位得到的不能通過偶數(shù)次換位來得到。 p=(0)(1 15)(2 14)(3 13)(4 12)(5 11)(6 10)(7 9)(8) 奇置換。 如果限制任一變動都是與0做相鄰的對換，是否能夠由左圖生成右圖？ 0從右下角出發(fā)回到右下角，水平方向上，垂直方向上都做了偶數(shù)次對換。一個奇置換不會等于一個偶置換。,？,

18、X,28,4.3循環(huán)、奇循環(huán)與偶循環(huán),1,n上的所有置換(共n!個)構(gòu)成一個群，稱為n階對稱群(Symmetric group)，記做Sn. 定理 Sn中所有偶置換構(gòu)成一階為(n!)/2的子群稱為交錯群，記做An. ()封閉性:偶置換相乘還是偶置換 ()結(jié)合律：置換群的結(jié)合律 ()單位元：置換群的單位元素本身就是偶置換 ()逆元 (i k)-1= (i k) 設(shè) p = (i1 j1)(i2 j2)(ii ji),則p-1 = (ii ji)(i1 j1) 故An為群 令Bn=Sn-An, |Bn|+|An|=n!, 則(i j) Bn An，所以 |Bn|An|， (i j) An Bn，所

19、以|An|Bn| |An|=|Bn|=(n!)/2,29,4.3循環(huán)、奇循環(huán)與偶循環(huán),如果兩凸多邊形的角對應(yīng)地相等, 對應(yīng)邊也相等,這兩個多邊形就叫做全等多邊形。 凸多邊形中，如果各邊相等且各角也相等，這樣的多邊形叫做正多邊形。 所謂正多面體，是指多面體的各個面都是全等的正多邊形，并且各個多面角都是全等的多面角。,任何凸多面體的頂點(diǎn)數(shù)v與面數(shù)f的和都較棱數(shù)e多2，即v+f-e =2。這就是歐拉定理。,30,4.3循環(huán)、奇循環(huán)與偶循環(huán),由歐拉定理推出：凸正多面體只有五種，即：正四面體、正八面體、正二十面體、正六面體（正方體）、正十二面體， 其中正四面體、正八面體和正二十面體的各面都是正三角形，正

20、六面體的各面是正方形，正十二面體的各面是正五邊形。,v+f-e = 4+4-6=2,31,4.3循環(huán)、奇循環(huán)與偶循環(huán),一個正多面體和以它的各面中心為頂?shù)恼嗝骟w，叫做互為對偶的正多面體。 正六面體和正八面體是互為對偶的正多面體；正十二面體和正二十面體是互為對偶的正多面體；正四面體的對偶多面體是正四面體。,一多面體在空間運(yùn)動，其運(yùn)動前后占有同一個空間位置，一切這樣的運(yùn)動的集合，對于以兩個這樣的運(yùn)動相繼施行作為乘法構(gòu)成群，稱為多面體群。 由幾何學(xué)可知，正多面體只有5種,即正四面體、正六面體、正八面體、正十二面體、正二十面體。于是有正四面體群、正六（八）面體群、正十二（二十）面體群等三種群 .,32

21、,4.3循環(huán)、奇循環(huán)與偶循環(huán),正四面體群 不動旋轉(zhuǎn): （A)(B)(C)(D) 以頂點(diǎn)與對面的中心連線為軸： A 為頂點(diǎn)(AO1):120o (A)(BCD) and (A)(BDC) B為頂點(diǎn):120o (B) (ACD) and (B)(ADC) C為頂點(diǎn):120o (C) (ABD) and (C)(ADB) D為頂點(diǎn):120o (D) (ABC) and (D)(ACB) 共有8個三項(xiàng)循環(huán)。 以正四面體A-BCD的3對對邊之中點(diǎn)聯(lián)線為旋轉(zhuǎn)軸：作角度為的3個旋轉(zhuǎn)，分別對應(yīng)于置換(AB)(CD)，(AC)(BD)，(AD)(BC), 這樣的12個運(yùn)動構(gòu)成群,稱為正四面體群。 e, (BCD

22、),(BDC),(ACD),(ADC)，(ABD)，(ADB)，(ABC)，(ACB) ,(AB)(CD)，(AC)(BD)，(AD)(BC),它與4個文字A、B、C、D上的四次交錯群A4同構(gòu)，因此，四次交錯群A4又稱為正四面體群。,33,4.3循環(huán)、奇循環(huán)與偶循環(huán),正八面體群或正六面體群由24個運(yùn)動構(gòu)成群，它與四次對稱群S4同構(gòu),所以正八面體群與正六面體群是一致的，都是4次對稱群S4。有時把四次對稱群稱為正八面體群或正六面體群。,正方形頂點(diǎn)二著色只考慮旋轉(zhuǎn)的等價類個數(shù): 6 |G|:置換個數(shù) 只考慮旋轉(zhuǎn): 4 置換群 Rotate 0 degree: p0=(1)(2)(3)(4)(5)(6

23、)(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),34,著色問題的等價類,置換pi使圖像k變?yōu)閘，則稱k和l屬于同一個等價類,置換pi使圖像k不變,35,4.

24、4 Burnside引理,k不動置換類(Stabilizer) 設(shè)G是1,n上的一個置換群。G是Sn的一個子群. k1,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),

25、 (142) Z4= e, (123), (132) ,36,4.4 Burnside引理,定理 置換群G的k不動置換類Zk是G的一個子群。封閉性：kkk,kk.結(jié)合性：自然。有單位元：G的單位元屬于Zk.有逆元：PZk,kk,則kk,P-1Zk.Zk是G的子群.,P1 P2,P1P2,P,P,-1,37,4.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中的數(shù)k，若存在置換pi使k變?yōu)閘，則稱k和l屬于同一個等價類,數(shù)k所屬

26、的等價類記為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,正方形頂點(diǎn)二著色只考慮旋轉(zhuǎn)的等價類個數(shù): 6 |G|:置換個數(shù) 只考慮旋轉(zhuǎn): 4 置換群 Rotate 0 degree: p0=(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13

27、)(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),38,著色問題的等價類,置換pi使圖像k變?yōu)閘，則稱k和l屬于同一個等價類,置換pi使圖像k不變,Z1=p0, p1, p2, p3,Z2= Z3= Z4=

28、Z5=p0,Z6= Z7= p0 , p2,|Ek|*|Zk|=|G|?,39,4.4 Burnside引理,定理(Orbit-stabilizer theorem) 設(shè)G是1,n上的一個置換群，Ek是1,n在G的作用下包含k的等價類，Zk是k不動置換類。有|Ek|Zk|=|G|. 證 設(shè)|Ek|=l,Ek=a1(=k),a2,al k=a1ai, i=1,2,l. P=p1,p2,pl 令Gi=Zkpi,i=1,2,l.則k在Zkpi的作用下變?yōu)閍i GiG(G關(guān)于Zk的陪集分解)ij,GiGj=. G1+G2+Gl G. 另一方面，任意pG. kajk PPj-1Zk, PZkPj=Gj.

29、 G G1+Gl. 從而，G=G1+G2+Gl. |G|=|G1|+|G2|+|Gl|=|Zkp1|+| Zkp2|+| Zkpl| = |Zk|l= |Zk|Ek|,Pi,p,Pj-1,40,4.4 Burnside引理,定義回顧 群用G表示,G中的每個置換表示為ai G=a1,a2.ag=e,(1 2),(3 4),(1 2)(3 4) G中某個置換ai的k階循環(huán)出現(xiàn)的次數(shù)為 ck(ai) a1=e=(1)(2)(3)(4) c1(a1) = 4 (1)4 a4=(12)(34) c1(a4) = 0 c2(a4) = 2 (2)2 G中使某元素k不動置換類，記做Zk G中的Z1=e,(3

30、 4) G中數(shù)k所屬的等價類記為Ek E1=E2=1,2 E3=E4=3,4 幾個常用群 對稱群Sn 交錯(交代)群An 轉(zhuǎn)動群,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)

31、(34), (13)(24), (14)(23).,正方形頂點(diǎn)二著色只考慮旋轉(zhuǎn)的等價類個數(shù): 6 |G|:置換個數(shù) 只考慮旋轉(zhuǎn): 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 deg

32、ree: p3=(1)(2 5 4 3)(6 7)(8 11 10 9)(12 15 14 13)(16),41,著色問題的等價類,置換pi使圖像k變?yōu)閘，則稱k和l屬于同一個等價類,置換pi使圖像k不變,Z1=p0, p1, p2, p3,Z2= Z3= Z4= Z5=p0,Z6= Z7= p0 , p2,|Ek|*|Zk|=|G|,定理(Orbit-stabilizer theorem) 設(shè)G是1,n上的一個置換群，Ek是1,n在G的作用下 包含k的等價類，Zk是k不動置換類。有|Ek|Zk|=|G|.,不動置換和等價類之間的關(guān)系,42,簡單例子,例如，G=e,(12),(34),(12)

33、(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.,Sjk= 對第j行求和得c1(aj),對第k列求和得|Zk|,表中元素的總和,|Ek|*|Zk|=|G|,43,4.4 Burnside引理,一般而言，與上表相仿，有下面表格，其中 Sjk=,44,若j, i同屬一個等價類，則Ei=Ej,|Ei|=|Ej|,因|Ei|Zi|=|G|,故|Zi|=|Zj|.,1,n分成l個等價類。1,n=Ea1+Ea2+Eal.,|Ek|Zk|=|G|.,每個等價類中,一共l個等價類中,45,4.4 Bur

34、nside引理,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). 設(shè)G=a1,a2,ag是目標(biāo)集1,n上的置換群。每個置換都寫成不相交循環(huán)的乘積。c1

35、(ak)是在置換ak的作用下不動點(diǎn)的個數(shù)，也就是長度為1的循環(huán)的個數(shù)。 G將1,n劃分成l個等價類。等價類個數(shù)為：,46,4.4 Burnside引理,例 一正方形分成4格，2著色，有多少種方案？ 圖象：看上去不同的圖形。 方案：經(jīng)過轉(zhuǎn)動相同的圖象算同一方案。圖象數(shù)總是大于方案數(shù)。,47,圖象與方案,圖象:固定不動,物理位置上具有不同染色的即為不同的圖象 方案:經(jīng)過外力變換,可以完全重合的不同圖象為同一個方案 內(nèi)部結(jié)構(gòu)不變 置換:外力產(chǎn)生的變換,如轉(zhuǎn)動,翻轉(zhuǎn) 圖象中的等價類,48,不動：a1=(1)(2)(16) 逆時針轉(zhuǎn)90度 ：a2=(1)(2)(3 4 5 6)(7 8 9 10) (1

36、1 12)(13 14 15 16) 順時針轉(zhuǎn)90度 ：a3=(1)(2)(6 5 4 3)(10 9 8 7)(11 12)(16 15 14 13) 轉(zhuǎn)180度：a4=(1)(2)(3 5)(4 6)(7 9)(8 10)(11)(12) (13 15)(14 16) (16+2+2+4)/4=6(種方案),l=c1(a1)+c1(a2)+c1(ag)/|G|,49,4.4 Burnside引理,針對圖像集的轉(zhuǎn)動群來求解 求解2著色的不同方案，可以用Burnside引理 但是當(dāng)多種顏色著色，理論上可以用Burnside來求解，但是極其復(fù)雜,Rotate 90o (1234) (4123),

37、1,2,4,3,4,1,3,2,The cyclic group Z26 underlies Caesars cipher.,群,魔方群：魔方的所有可能 重新排列形成一個群。,http:/www.cse.psu.edu/yanxi/CourseFall2007.htm,群的發(fā)展,群就是對稱，研究群，就是研究各種對稱性,正規(guī)子群 不僅自己是一個群，如果“除”原來的群，得到的也是一個群。 對原來的群作“除法”得到的群叫商群,單群 不能被繼續(xù)分解的群。,素?cái)?shù)？,能找到所有的單群嗎？,1823年發(fā)現(xiàn)所謂的交錯群An對于所有n=5都是單群，從而不是可解群。,1884年16族有限李群:離散域上的矩陣組成的

38、群,Sophus Lie 挪威數(shù)學(xué)家,菲利克斯克萊因 德國數(shù)學(xué)家,1872年幾何與群的聯(lián)系,18個有限單群家族+26個單獨(dú)存在的有限單群,分類結(jié)構(gòu)分析： 1872年的Sylow定理。使數(shù)學(xué)家開始明白有限群更深層的結(jié)構(gòu) 1892年的Hlder：真正明確提出對有限單群的分類,所有的有限單群？,100年過去了,百年的征程,當(dāng)1983年Gorenstein宣稱有限單群分類定理被證明之時，群論學(xué)界可是歡呼雀躍。 整個證明散落在各期刊的500多篇論文之中，合計(jì)過萬頁，每篇論文都對某種特殊情況進(jìn)行了處理。 問題是，他弄錯了。 他以為一類名為“擬薄群”（quasi-thin group）的類別已經(jīng)被處理好了，

39、但事實(shí)上沒有。 直到2004年，由Aschbacher和Smith撰寫的一篇一千多頁的論文才將這個情況完全處理妥當(dāng)，從而填補(bǔ)了這個漏洞。此時，有限單群分類定理，這個有限群理論的圣杯，才正式被圓滿證明。 18個有限單群家族，再加上26個散在單群，這就是所有的有限單群。,魔群,最大的散在單群魔群（Monster Group） 魔群是在1973年被Fischer和Griess分別獨(dú)立發(fā)現(xiàn)的。 最大的散在單群，“魔群”這個名字就源于它龐大的體積。 魔群的準(zhǔn)確元素個數(shù)是808017424794512875886459904961710757005754368000000000，也就是大概8*1053個。

40、 太陽系的原子個數(shù)也就是大約1057個，僅僅高了兩個數(shù)量級。如果我們用線性空間和矩陣變換來表示魔群的話，我們至少需要一個196883維的線性空間， Griess提出了一個名為Griess代數(shù)的代數(shù)結(jié)構(gòu)，而魔群恰好就是這個代數(shù)結(jié)構(gòu)的自同構(gòu)群。換句話說，魔群恰好刻畫了Griess代數(shù)的所有對稱性。 Griess代數(shù)的維度是196884，比196883多1。,冥冥中的聯(lián)系,Griess代數(shù)的維度是196884，比196883多1 模形式理論中，有一個特殊的函數(shù)占據(jù)著相當(dāng)重要的地位，它叫j不變量 傅立葉級數(shù)，其中每個系數(shù)都是整數(shù),巧合？聯(lián)系？,1979年，Conway和Norton提出了 “魔群月光猜

41、想” （monsterous moonshine ）。 存在一個基于魔群的無限維代數(shù)結(jié)構(gòu)，通過魔群的不可約線性表示，它恰好給出了j不變量的所有傅立葉系數(shù)，而魔群每一個元素在這個代數(shù)結(jié)構(gòu)上的作用，都自然地給出了與某個群相關(guān)的模形式。 1992年由Brocherds完成證明 證明同時包含了數(shù)學(xué)和物理，其中用到了弦論中的No-ghost定理來構(gòu)造證明中必不可少的一個代數(shù)結(jié)構(gòu)； 1998年Brocherds由于這個證明獲得了菲爾茲獎。 通過這個定理架起的橋梁，數(shù)學(xué)家們也發(fā)現(xiàn)了魔群、模函數(shù)和弦理論之間更多的千絲萬縷的聯(lián)系。 甚至有人過于瘋狂地設(shè)想，魔群也許就代表著我們這個宇宙終極的對稱性。,58,伽羅華

42、（Galois）,variste Galois(18111832) 對伽羅華來說，他所提出并為之堅(jiān)持的理論是一場對權(quán)威、對時代的挑戰(zhàn)，他的“群”完全超越了當(dāng)時數(shù)學(xué)界能理解的觀念。 他的數(shù)學(xué)考官曾說“這個孩子在表達(dá)他的想法時有些困難，但是他十分聰明，并體現(xiàn)出了非凡的學(xué)術(shù)精神” 過分地追求簡潔是導(dǎo)致這一缺憾的原因。 當(dāng)你試圖引尋讀者遠(yuǎn)離習(xí)以為常的思路進(jìn)入較為困惑的領(lǐng)域時，清晰性是絕對必需的。,59,Thanks 下周交作業(yè),在討論超前的問題時務(wù)必空前地清晰。 笛卡爾,尼耳斯亨利克阿貝爾（18021829） 研究一般五次方程問題 躊躇滿志的阿貝爾自費(fèi)印刷了證明五次方程不可解的論文（鑒于經(jīng)費(fèi)原因，他把

43、內(nèi)容壓縮在了6頁上） 高斯見后說：“太瘋狂了，居然這么幾頁紙就解決了數(shù)學(xué)界的世界難題？！” 人們在高斯死后的遺物中發(fā)現(xiàn)阿貝爾寄給他的小冊子還沒有裁開。 橢圓函數(shù) 科學(xué)院秘書傅立葉讀了論文的引言，然后委托勒讓得和柯西負(fù)責(zé)審查。柯西把稿件帶回家中，究竟放在什么地方，竟記不起來了。直到兩年以后阿貝爾已經(jīng)去世，失蹤的論文原稿才重新找到，而論文的正式發(fā)表，則遷延了12年之久。 阿貝爾留下的后繼工作，“夠數(shù)學(xué)家們忙上五百年”。 阿貝爾死后兩天，克雷勒的一封信寄到，告知柏林大學(xué)已決定聘請他擔(dān)任數(shù)學(xué)教授。,60,正方形頂點(diǎn)二著色只考慮旋轉(zhuǎn)的等價類個數(shù): 6 |G|:置換個數(shù) 只考慮旋轉(zhuǎn): 4 c1(f): 不

44、動點(diǎn)個數(shù) 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),61,l=c1(a1)+c1(a2)+c1(ag)/|G|,