《组合数学讲义POLYA定理》由会员分享，可在线阅读，更多相关《组合数学讲义POLYA定理（120页珍藏版）》请在金锄头文库上搜索。
1、第四章 Burnside 引理 与Polya定理郝聚涛群的概念置换群循环、奇偶循环Burnside引理Plya定理举例母函数型式的Plya定理图的计数5.1 群的概念定义5.1：给定集合G和G上的二元运算(G, )，满足下列条件称为群封闭性：若a,bG，则存在cG,使得ab=c结合律成立：任意a,b,cG，有(ab)c=a(bc)（semigroup）有 单 位 元 ： 存 在 eG， 使 得 对 于 任 意 aG 满 足ae=ea=a （monoid）有逆元：任意aG，存在bG, ab=ba=e。记b=a-1（group）G=0,1,2,n-1在mod n 的加法下是群G=1,2,n-1在m
2、od n的乘法下是群 iff n是素数Dept of Computer Science and Engineering， Shanghai Jiaotong University二维欧氏空间所有刚体旋转=Ta构成群 x1 cos sin x T= T + (1) : 封闭性 : T T = T + (2) :结合律 : (TT )T = T (T T ) = T + + (3) : 单位元素 : e = T0(4) : 逆元素 : T的逆元素T- = T : y1 sin cos y = T = cos sin cos sin cos( + ) sin( + ) sin cos sin cos
3、 sin( + ) cos( + )概念有限群：元素个数有限的群无限群有限群G的元素个数叫做群的阶,记做|G|交换群（Abel群） 任意元素a,b ab=ba例: G=-1,1在乘法运算下是一个群封闭性:(1)(-1)=-1;(1)(1)=1;(-1)(1)=1,(-1)(-1)=1;结合性：显然单位元素：e=1逆元素 由于(1)(1)=1 (-1)(-1)=1故（-1）-1 =1，（-1）-1=-1群的性质定理：群的单位元是唯一的证：假设有两个单位元e1,e2e1e2=e2e1e2=e1e1 = e2定理定理 : ab = ac b = c, ba = ca b = c11定理 : G中的每
4、一个元素的逆元素是唯一的1 1 11 1 1定义 :设G是群, H是G的子群,若H在G的原来定义的运算下也成群,则称H为G的子群( ) ( )1a ab a a b b= =( ) ( )1a ac a b c c= =定理 .: (abc.lmn) -1 1 1 1n m l c b a= (abc.lmn) .1 1 1n m l c b a e= 置换群置换群是最重要的有限群，所有的有限群都可以用之表示。置换：1,n到自身的1-1变换，例如n阶置换，其中a1a2an是1,n中元素的一个排列n阶置换共有n!个例5.2置换乘法Dept of Computer Science and Engi
5、neering， Shanghai Jiaotong University置换群1,n上的所有n阶置换在上面的乘法定义下是一个群。验证是否满足群的性质Dept of Computer Science and Engineering， Shanghai Jiaotong University例：圆圈上装有A，B，C三颗珠子，正好构成等边三角形，（1）绕过圆心垂直于圆平面的轴，沿反时针方向旋转0，120，240；（2）沿过圆心及A点的轴线翻转180度。经过1，2变换A，B，C三颗珠子两两重合，但顶点交换位置。以1代A，2代B，3代C1 2 3 1 2 3 1 2 31 2 3 2 3 1 3 1
6、2 1 2 3 1 2 3 1 2 31 3 2 3 2 1 2 1 3这六个置换是一个群=1p= 2p= 3p=4p= 5p= 6p正n边形的对称群例5.3 等边三角形的运动群。绕中心转动120度(两个)、不动（一个）、绕对称轴翻转（三个），运动群的个数有6个。正方形的运动群。绕中心转动90度(三个)、不动（一个）、绕对称轴翻转（四个）对于任意的n=3，可得到正n边形的对称群（运动群）：n个旋转：n, n2, , nn-1，其中n视为圆的360/n度的旋转， n2视为圆的2(360/n)度的旋转n个翻转： 1, 2, , nDept of Computer Science and Engin
7、eering， Shanghai Jiaotong University正n边形的n个翻转若n是偶数，则有n/2个关于对角点的翻转， n/2个关于对边中线的翻转；若n是奇数，则有n个顶点与其对边中点的连线的的翻转；Dept of Computer Science and Engineering， Shanghai Jiaotong Universityn阶对称群1,n上的所有置换(共n!个)构成一个群，称为n阶对称群，记做Sn.n个文字的对称群注意：一般说1,n上的一个置换群，不一定是指Sn，但一定是Sn的某一个子群。Dept of Computer Science and Engineeri
8、ng， Shanghai Jiaotong University循环、奇循环与偶循环例5.4 1 2 3 4 5 4 3 1 5 2 a a2a2 . am1 am a3 . am a1 1 3 1 52 3 4 5 1 2 5 4 2 3 4 5 2 3 1 4 (a1a2am)=(a2a3ama1)=(ama1am-1)有m种表示方法。Dept of Computer Science and Engineering， Shanghai Jiaotong University置换的循环表示： (a1, a2 ,., am ) = 1 = (1 4 5 2 3) = (1 3 2)o (4 5
9、) = (1 5 4)o (2)o (3)1 2 3 2 3 11 2 31 2 31 2 3 1 2 3 2 3 1 2 3 1 2 3 1 1 2 3=p(1 2 )= 3 =p=(1)(2)(3)=1 2 31 2 3 1 2 3 2 1 3 3 2 1 3 2 1(1 2)(1 3) =(1 2 3)=定理5.2: 任一循环都可以表示为对换的积。例5.5：(1 2 n)=(1 2)(1 3) (1 n)= (2 3) (2 4) (2 n) (2 1) 表示不唯一。注：分解成对换的形式不唯一，但对换个数的奇偶性唯一。任一置换表示成对换的个数的奇偶性是唯一的置换分成两大类：奇置换与偶置换
10、。循环长度减1的奇偶性即置换奇偶性定理：Sn中所有偶置换构成一阶为(n!)/2的子群称为交错群，记做AnDept of Computer Science and Engineering， Shanghai Jiaotong University证明 :1 2 .n 1 2.n An非空(1)封闭性 : p1, p2是偶置换,则p3 = p1p2也是偶置换(2)结合律 : 置换群的结合律成立(3)单位元素 : 置换群的单位元素本身就是偶置换(4)逆元素 : (i, k )的逆元素为(i, k ), p = (i1, j1)(i2 , j2 ).(ik , jk )的逆元素p 1 = (ik , jk ).(i2 , j2 )(i1, j1)pp 1 = (i1, j1)(i2 , j2 ).(ik , jk )(ik , jk ).(i2 , j2 )(i1, j1 )= (1)(2).(n)Bn = S n An表示奇置换任取其中
