資源描述:
《第四組合數(shù)學(xué)》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、第四章Pólya定理群的概念置換群循環(huán)、奇循環(huán)與偶循環(huán)Burnside引理Pólya定理例母函數(shù)型的Pólya定理圖的計(jì)數(shù)4.1群的概念(1)群定義給定集合G和G上的二元運(yùn)算·,滿足下列條件稱為群。(a)封閉性:若a,b∈G,則存在c∈G,使得a·b=c.(b)結(jié)合律成立:任意a,b,c∈G,有(a·b)·c=a·(b·c).(c)有單位元:存在e∈G,任意a∈G.a·e=e·a=a.(d)有逆元:任意a∈G,存在b∈G,a·b=b·a=e.b=a.由于結(jié)合律成立,(a·b)·c=a·(b·c)可記做a·b·c.例證明對(duì)于a1,a2,…,an的乘積,結(jié)合律成立.a·a·
2、…·a=a(共n個(gè)a相乘).-1n4.1群的概念(2)簡(jiǎn)單例子例G={1,-1}在普通乘法下是群。例G={0,1,2,…,n-1}在modn的加法下是群.例二維歐氏空間所有剛體旋轉(zhuǎn)T={Ta}構(gòu)成群。其中Ta=cosasina-sinacosaTbTa=cosbsinbcosasina-sinbcosb-sinacosa4.1群的概念=cosacosb-sinasinbsinacosb+cosasinb-sinacosb-cosasinbcosacosb-sinasinb=cos(a+b)sin(a+b)=Ta+b-sin(a+b)cos(a+b)從而有(a)封閉性;(
3、b)結(jié)合律成立:(TαTβ)Tγ=Tα(TβTγ)=TαTβTγ;(c)有單位元:T0=;(d)有逆元:Ta=T-a=cosa-sinasinacosa10014.1群的概念前兩例群元素的個(gè)數(shù)是有限的,所以是有限群;后一例群元素的個(gè)數(shù)是無(wú)限的,所以是無(wú)限群。有限群G的元素個(gè)數(shù)叫做群的階,記做
4、G
5、。若群G的任意二元素a,b恒滿足ab=ba。稱G為交換群,或Abel群。設(shè)G是群,H是G的子集,若H在G原有的運(yùn)算之下也是一個(gè)群,則稱為G的一個(gè)子群。4.1群的概念基本性質(zhì)單位元唯一e1e2=e2=e1消去律成立ab=ac→b=c,ba=ca→b=c每個(gè)元的逆元唯一aa=aa=
6、e,ab=ba=e,aa=ab,a=b(d)(ab….c)=c…ba.c…baab…c=e-1-1-1-1-1-1-1-1-1-1-14.1群的概念(e)G有限,a∈G,則存在最小正整數(shù)r,使得a=e.且a=a.r-1r-14.2置換群置換群是最重要的有限群,所有的有限群都可以用之表示。置換:[1,n]到自身的1-1變換。n階置換。[1,n]目標(biāo)集。(),a1a2…an是[1,n]中元的一個(gè)排列。n階置換共有n!個(gè),同一置換用這樣的表示可有n!個(gè)表示法。例如p1=()=(),n階置換又可看作[1,n]上的一元運(yùn)算,一元函數(shù)。12…na1a2…an123431243142
7、23414.2置換群置換乘法P1=(),P2=()P1P2=()()=()注意:既然先做P1的置換,再做P2的置換就規(guī)定了若作為運(yùn)算符或函數(shù)符應(yīng)是后置的。這與一般習(xí)慣的前置不一樣。一般而言,對(duì)[1,n]上的n階置換,i[1,n]要寫成(i)P1P2,而不是P1P2(i).(i)P有時(shí)寫成i在上面例中,1→3→2,2→1→4,3→2→3,4→4→1.也可寫(1)P1P2=2,(2)P1P2=4,(3)P1P2=3,(4)P1P2=1.P2P1=()()=( )≠P1P2.1234312412343124123443213124243112342431P1P1P2P1P1
8、P2P2P21234432143214213123442314.2置換群置換群具有的性質(zhì)(a)封閉性()()=()(b)可結(jié)合性(()())()=()=()(()())(c)有單位元e=()(d)()=()12…na1a2…ana1a2…anb1b2…bn12…nb1b2…bn12…na1a2…ana1a2…anb1b2…bn12…na1a2…ana1a2…anb1b2…bn12…nc1c2…cnb1b2…bnc1c2…cnb1b2…bnc1c2…cn12…n12…n12…na1a2…ana1a2…an12…n-1定義:置換群[1,n]上的所有n階置換集合及在其上定義的
9、置換乘法構(gòu)成的代數(shù)系統(tǒng)是一個(gè)群,該群成為置換群。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è)子群。1231231232311233121231321233211232131234.3循環(huán)、奇循環(huán)與偶循環(huán)(a1a2…am)=()稱為置換的循環(huán)表示。于是()=(14523),()=(132)(45)