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

1、第四組合數(shù)學第1頁，共23頁，2022年，5月20日，3點31分，星期二4.1 群的概念(1)群定義 給定集合G和G上的二元運算 ，滿足下列條件稱為群。(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. 例 證明對于a1,a2,an的乘積，結(jié)合律成立. aaa=a (共n個a相乘).-1n第2頁，共23頁，2022年，5月20日，3點31分，星期二4.1 群的概念(2

2、) 簡單例子例 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頁，共23頁，2022年，5月20日，3點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頁，共23頁，2022年，5月20日，3點31分，星期二4.1 群的概念前兩例群元素的個數(shù)是有限的，所以是有限群；后一例群元素的個數(shù)是無限的，所以是無限群。有限群G的元素個數(shù)叫做群的階,記做|G|。若群G的任意二元素a,b恒滿足ab=ba。稱G為交換群，或Abel群。設(shè)G是群,H是G的子集,若H在G原有的運算之下也是一個群,則稱為G的一個子群。第5頁，共23頁，2022年，5月20日，

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

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

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

7、3頁，2022年，5月20日，3點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)是一個群，該群成為置換群。 第11頁，共23頁，2022年，5月20日，3點31分，星期二4.2 置換群(2)例 等邊三角形的運動群。 繞中心轉(zhuǎn)動120，不動， 繞對稱軸翻轉(zhuǎn)。 P1=( ),P2=( ),P3=( ),P4=( ), P5=( ),P6=( )。 1,n上的所有置換(共n!個)構(gòu)成一個群，稱為對稱群，記做Sn.注意：一般說1,n上的一個置換群，不一定是指Sn.但一定是Sn的某一個子群。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頁，共23頁，2022年，5月20日，3點31分，星期二第13頁，共23頁，2022年，5月20日，3點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頁，共23頁，2022年，5月20日，3點31分，星期二4.3循環(huán)、奇循環(huán)與偶循環(huán)若兩個循環(huán)無共同文字，稱為不相交的

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

11、共23頁，2022年，5月20日，3點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)叫做對換。8第19頁，共23頁，2022年，5月20日，3點31分，星期二4.3循環(huán)、奇循環(huán)與偶循環(huán)定理 任一循環(huán)都可以表示為對換的積。(1 2 n)=(1 2)(1 3)(1 n)=(2 3)(2 4)(2 n)(2 1)表示不唯一。 故