第四組合數(shù)學(xué)精品課件

1、第四組合數(shù)學(xué)第1頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)31分，星期二4.1 群的概念(1)群定義 給定集合G和G上的二元運(yùn)算 ，滿足下列條件稱為群。(a)封閉性：若a,bG,則存在cG,使得ab=c.(b)結(jié)合律成立：任意a,b,cG,有(ab)c=a(bc).(c)有單位元：存在eG,任意aG.ae=ea=a.(d)有逆元：任意aG,存在bG, ab=ba=e. b=a.由于結(jié)合律成立，(ab)c=a(bc)可記做abc. 例 證明對(duì)于a1,a2,an的乘積，結(jié)合律成立. aaa=a (共n個(gè)a相乘).-1n第2頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)31分，星期二4.1 群的概念(2

2、) 簡(jiǎn)單例子例 G=1,-1在普通乘法下是群。例 G=0,1,2,n-1在mod n的加法下是群.例 二維歐氏空間所有剛體旋轉(zhuǎn)T=Ta構(gòu)成群。其中Ta = cosa sina -sina cosa TbTa= cosb sinb cosa sina -sinb cosb -sina cosa第3頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)31分，星期二4.1 群的概念= cosacosb-sinasinb sinacosb+cosasinb -sinacosb-cosasinb cosacosb-sinasinb= cos(a+b) sin(a+b) =Ta+b -sin(a+b) cos(a+

3、b) 從而有(a)封閉性; (b)結(jié)合律成立：(TT)T = T(TT) = TTT ; (c)有單位元： T0 = ; (d)有逆元：Ta =T-a = cosa -sina sina cosa1 00 1第4頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)31分，星期二4.1 群的概念前兩例群元素的個(gè)數(shù)是有限的，所以是有限群；后一例群元素的個(gè)數(shù)是無(wú)限的，所以是無(wú)限群。有限群G的元素個(gè)數(shù)叫做群的階,記做|G|。若群G的任意二元素a,b恒滿足ab=ba。稱G為交換群，或Abel群。設(shè)G是群,H是G的子集,若H在G原有的運(yùn)算之下也是一個(gè)群,則稱為G的一個(gè)子群。第5頁(yè)，共23頁(yè)，2022年，5月20日，

4、3點(diǎn)31分，星期二4.1 群的概念基本性質(zhì)單位元唯一 e1e2=e2=e1消去律成立 ab=ac b=c, ba=ca b=c每個(gè)元的逆元唯一 aa =a a = e, ab = ba = e , aa = ab , a = b(d)(ab.c) =c b a . c b a abc = e-1-1-1-1-1-1-1-1-1-1-1第6頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)31分，星期二4.1 群的概念(e) G有限，aG，則存在最小正整數(shù)r，使得a = e.且a = a .r-1r-1第7頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)31分，星期二第8頁(yè)，共23頁(yè)，2022年，5月20日，

5、3點(diǎn)31分，星期二4.2 置換群 置換群是最重要的有限群，所有的有限群都可以用之表示。置換：1,n到自身的1-1變換。n階置換。1,n目標(biāo)集。( ), a1a2an是1,n中元的一個(gè)排列。n階置換共有n!個(gè)，同一置換用這樣的表示可有n!個(gè)表示法。例如 p1=( )=( )，n階置換又可看作1,n上的一元運(yùn)算，一元函數(shù)。 1 2 na1 a2 an1 2 3 43 1 2 43 1 4 22 3 4 1第9頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)31分，星期二4.2 置換群置換乘法 P1=( ),P2=( )P1P2=( )( )=( ) 注意：既然先做P1的置換，再做P2的置換就規(guī)定了若作為

6、運(yùn)算符或函數(shù)符應(yīng)是后置的。這與一般習(xí)慣的前置不一樣。一般而言，對(duì)1,n上的n階置換，i1,n要寫(xiě)成(i)P1P2，而不是P1P2(i). (i)P有時(shí)寫(xiě)成i 在上面例中，132,214,323,441.也可寫(xiě)(1)P1P2=2,(2)P1P2=4,(3)P1P2=3,(4)P1P2=1. 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 1P1P1P2P1P1P2P2P21 2 3 44 3 2 14 3 2 14 2 1 31 2 3 44 2 3 1第10頁(yè)，共2

7、3頁(yè)，2022年，5月20日，3點(diǎn)31分，星期二4.2 置換群置換群具有的性質(zhì) (a)封閉性 ( )( )=( ) (b)可結(jié)合性 ( )( )( ) =( )=( )( )( ) (c) 有單位元 e=( ) (d) ( ) =( )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-

8、1定義：置換群 1,n上的所有n階置換集合及在其上定義的置換乘法構(gòu)成的代數(shù)系統(tǒng)是一個(gè)群，該群成為置換群。 第11頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)31分，星期二4.2 置換群(2)例 等邊三角形的運(yùn)動(dòng)群。 繞中心轉(zhuǎn)動(dòng)120，不動(dòng)， 繞對(duì)稱軸翻轉(zhuǎn)。 P1=( ),P2=( ),P3=( ),P4=( ), P5=( ),P6=( )。 1,n上的所有置換(共n!個(gè))構(gòu)成一個(gè)群，稱為對(duì)稱群，記做Sn.注意：一般說(shuō)1,n上的一個(gè)置換群，不一定是指Sn.但一定是Sn的某一個(gè)子群。1 2 31 2 31 2 32 3 11 2 33 1 21 2 31 3 21 2 33 2 11 2 32 1

9、 3 12 3第12頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)31分，星期二第13頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)31分，星期二4.3循環(huán)、奇循環(huán)與偶循環(huán)(a1a2am)=( ) 稱為置換的循環(huán)表示。于是( )=(14523), ( )=(132)(45), ( )=(154)(2)(3).(a1a2am)=(a2a3ama1)=(ama1am-1)有m種表示方法。a1a2am-1ama2 a3am a1123454315212345312541234552314第14頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)31分，星期二4.3循環(huán)、奇循環(huán)與偶循環(huán)若兩個(gè)循環(huán)無(wú)共同文字，稱為不相交的

10、，不相交的循環(huán)相乘可交換。如(132)(45)= (45)(132).若p=(a1a2am),則p =(1)(2)(n)=e.定理 任一置換可表成若干不相交循環(huán)的乘積。n第15頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)31分，星期二第16頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)31分，星期二第17頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)31分，星期二4.3循環(huán)、奇循環(huán)與偶循環(huán)例 一副撲克牌，一分為二，交錯(cuò)互相插入(洗牌)，這樣操作一次相當(dāng)于一個(gè)置換p。i =p(i+1)/2,i=1,3,5,51. i/2+26,i=2,4,6,52.p=( ),第i個(gè)位置被i 號(hào)牌占據(jù).pipp第18頁(yè)，

11、共23頁(yè)，2022年，5月20日，3點(diǎn)31分，星期二4.3循環(huán)、奇循環(huán)與偶循環(huán)26 . . . 5 3 3 2 1 152 52 . . . 29 6 28 4 27 2p = (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)p = e2階循環(huán)叫做對(duì)換。8第19頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)31分，星期二4.3循環(huán)、奇循環(huán)與偶循環(huán)定理 任一循環(huán)都可以表示為對(duì)換的積。(1 2 n)=(1 2)(1 3)(1 n)=(2 3)(2 4)(2 n)(2 1)表示不唯一。 故