正文描述:《组合数学第四章new》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第四章Pólya定理群的概念置换群循环、奇循环与偶循环Burnside引理Pólya定理例母函数型的Pólya定理图的计数4.1群的概念(1)群定义给定集合G和G上的二元运算·,满足下列条件称为群。(a)封闭性:若a,b∈G,则存在c∈G,使得a·b=c.(b)结合律成立:任意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.由于结合律成立,(a·b)·c=a·(b·c)可记做a·b·c.例证明对
2、于a1,a2,…,an的乘积,结合律成立.a·a·…·a=a(共n个a相乘).-1n4.1群的概念(2)简单例子例G={1,-1}在普通乘法下是群。例G={0,1,2,…,n-1}在modn的加法下是群.例二维欧氏空间所有刚体旋转T={Ta}构成群。其中Ta=cosasina-sinacosaTbTa=cosbsinbcosasina-sinbcosb-sinacosa4.1群的概念=cosacosb-sinasinbsinacosb+cosasinb-sinacosb-cosasinbcosacosb-sinasinb
3、=cos(a+b)sin(a+b)=Ta+b-sin(a+b)cos(a+b)从而有(a)封闭性;(b)结合律成立:(TαTβ)Tγ=Tα(TβTγ)=TαTβTγ;(c)有单位元:T0=;(d)有逆元:Ta=T-a=cosa-sinasinacosa10014.1群的概念前两例群元素的个数是有限的,所以是有限群;后一例群元素的个数是无限的,所以是无限群。有限群G的元素个数叫做群的阶,记做
4、G
5、。若群G的任意二元素a,b恒满足ab=ba。责称G为交换群,或Abel群。设G是群,H是G的子集,若H在G原有的运算之下也是一个
6、群,则称为G的一个子群。4.1群的概念基本性质单位元唯一e1e2=e2=e1消去律成立ab=ac→b=c,ba=ca→b=c每个元的逆元唯一aa=aa=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,则存在最小正整数r,使得a=e.且a=a.证设
7、G
8、=g,则a,a,…,a,a∈G,由鸽巢原理其中必有相同项。设a=a,1≤m<l≤g+1,e=a,1≤l-m≤g,令l-m=r.则有a=aa=e.即a=a
9、.既然有正整数r使得a=e,其中必有最小者,不妨仍设为r.r称为a的阶。易见H={a,a,…a,a=e}在原有运算下也是一个群。r-1r-12gg+1mll-mrr-1r-1-1r2r-1r4.2置换群置换群是最重要的有限群,所有的有限群都可以用之表示。置换:[1,n]到自身的1-1变换。n阶置换。[1,n]目标集。(),a1a2…an是[1,n]中元的一个排列。n阶置换共有n!个,同一置换用这样的表示可有n!个表示法。例如p1=()=(),n阶置换又可看作[1,n]上的一元运算,一元函数。12…na1a2…an1234
10、3124314223414.2置换群置换乘法P1=(),P2=()P1P2=()()=()注意:既然先做P1的置换,再做P2的置换就规定了若作为运算符或函数符应是后置的。这与一般习惯的前置不一样。一般而言,对[1,n]上的n阶置换,i[1,n]要写成(i)P1P2,而不是P1P2(i).(i)P有时写成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.12343124123431241
11、23443213124243112342431P1P1P2P1P1P2P2P21234432143214213123442314.2置换群(1)置换群[1,n]上的所有n阶置换在上面的乘法定义下是一个群。(a)封闭性()()=()(b)可结合性(()())()=()=()(()())(c)有单位元e=()(d)()=()12…na1a2…ana1a2…anb1b2…bn12…nb1b2…bn12…na1a2…ana1a2…anb1b2…bn12…na1a2…ana1a2…anb1b2…bn12…nc1c2…cnb1b2…
12、bnc1c2…cnb1b2…bnc1c2…cn12…n12…n12…na1a2…ana1a2…an12…n-14.2置换群(2)例等边三角形的运动群。绕中心转动120,不动,绕对称轴翻转。P1=(),P2=(),P3=(),P4=(),P5=(),P6=()。[1,n]上的所有置换(共n!个)构成一个群,称为对称群,
显示全部收起