《组合数学课件--第四章第二节贝恩塞特(burnside)引理》由会员分享，可在线阅读，更多相关《组合数学课件--第四章第二节贝恩塞特(burnside)引理（38页珍藏版）》请在金锄头文库上搜索。
1、1,第4章 Burnside引理与Polya定理,4.1 群的概念 14.2 置换群 14.3 循环、奇循环与偶循环 14.4 Burnside引理 24.5 Polya 定理 34.6 举例 34.7 母函数形式的Polya定理 *4.8 图的计数 *4.9 Polya定理的若干推广 *,2,1、共轭类,4.4.1 几个概念,2、k不动置换类,3、等价类.,4.4.2 重要定理.,4.4.3 1阶循环的个数及记法,贝恩塞特(Burnside)引理,贝恩塞特(Burnside)引理,3,4.4 .1 几个概念,-1、共轭类,Sn中任意一个置换p都能分解成若干个互不相交的循环的乘积。,p=(a1
2、a2.ak1)(b1b2.bk2).(h1h2.hkm)共m项，其中k1+k2+.km=n,例如：,(1)(23)(4567),(123)(456)(7),(134)(2)(567),4,Sn中任意一个置换p都能分解成若干个互不相交的循环的乘积。,设其中k阶循环出现的次数为ck,k=1,2,.,n.,k阶循环出现ck次,用(k)ck表示,Sn中置换可分解成如下格式(1)c1 (2)c2. (n)cn,1、共轭类,在Sn中具有相同格式的置换全体,叫做与该格式相应的共轭类。,5,例：求S3中所有共轭类。,6,定理4.4.1 Sn中属于(1)c1(2)c2.(n)cn共轭类的元素个数为:,1、共轭类
3、,例如：3个元素中共轭类,2 1 3,(123)(456)(7)=(7)(123)(456),(134)(2)(567)=(2)(134)(567),证明：首先把每个共轭类的写法标准化,按格式(1)c1(2)c2.(n)cn来记。,7,属于(1)c1(2)c2.(n)cn共轭类的元素个数为:,证明：,1,2,3,.,n的全排列共n!个,每个排列都可以唯一地划分成格式为(1)c1(2)c2.(n)cn的置换。,反过来,该共轭类的每个置换都可以通过这样的划 分而得到；,1、共轭类,8,例如：对于6个元素的一个排列345126可以唯一地划分成任何一个共轭类。,6个元素的所有共轭类如下：,(1)6,(
4、1)4(2)1,(1)3(3)1,(1)2(2)2,(1)1(2)1(3)1,(2)3,(3)2,(3)(4)(5)(1)(2)(6),(3)(4)(5)(1)(26),(3)(4)(5)(126),(3)(4)(51)(26),(3)(45)(126),(34)(51)(26),(345)(126),1、共轭类,9,(1)c1(2)c2.(n)cn格式,与n!个排列相比较，重复来自。,(a)由循环(a1a2a3.ak)=(a2a3. aka1)=.= (aka1a2.ak-1)引起,一个k阶循环重复k倍,ck个k阶循环共重复了kck倍,共重复了：,1、共轭类,10,(b)由互不相交的ck个k
5、阶循环乘积的可交换性引起的重复：,ck个k阶循环重复了ck!倍,属于(1)c1(2)c2.(n)cn共轭类的元素个数为:,共重复了：,1、共轭类,*,11,2、k不动置换类,设G是1,2,.,n的置换群,G是Sn的一个子群,若k是1到n中的某个整数,G中使k保持不变的置换全体,记以Zk,叫做G中使k保持不动的置换类,或简称k不动置换类。,如G=e,(12),(34),(12)(34),这里e是单位元,(12)实际上是(12)(3)(4)的缩写,G中使1不动置换类为:,G中使3不动置换类为:,Z3=e,(12),G中使4不动置换类为:,Z4=e,(12),Z1=e,(34),G中使2不动置换类为
6、:,Z2=e,(34),12,定理4.4.2 群G中关于k的不动置换类Zk是G的一个子群。,证明:,(1)封闭性:若p1,p2分别是k不动的两个置换,(2)结合律:,(3)单位元素:,(4)逆元素:,p3=p1p2也是k不动的置换.,2 k不动置换类,*,13,例如:G=e,(12),(34),(12)(34),在群G作用下1能变为2,2能变为1,3能变为4,4能变为3.,1与2属于同一类,3和4属于另一类,在群G的作用下,1与2不可能变为3或4,同样3或4也不能变为1或2,等价类：在群G的作用下能够相互转化的元素我们称为同一类,这样的类我们称作是一个等价类：,(a)自反性,(b)对称性，(c
7、)传递性。,3.等价类.,意义,14,4.4.2.重要定理.,定理4.4.3 EkZk=G,k=1,2,.,n.,Z1=e,(34),E1=1,2,例如:G=e,(12),(34),(12)(34),15,4.4.2.重要定理.,定理4.4.3 EkZk=G,k=1,2,.,n.,证明:设|Ek|=m,既然a1(=k),a2,.,am属于同一等价类,故存在属于G的置换pi使得,即置换pi使数k变为等价类中的ai.,P=p1,p2,.,pm是属于群G的置换的集合。,设Ek=a1(=k),a2,.,am,a1(=k),a2,.,am是m个不超过n的正整数,而且各不相等；,16,置换pi使数k变为等
8、价类中的ai,i=1,2,m,P=p1,p2,.,pm是属于群G的置换的集合。,只要证明：G=Zkp1Zkp2.Zkpm,因为Zkp1、Zkp2、.、Zkpm互不相交,G=Zkp1+Zkp2+.+Zkpm=mZk=EkZk,4.4.2.重要定理.,17,首先：Zkp1Zkp2.ZkpmG,4.4.2.重要定理.,其次：需证G Zkp1Zkp2.Zkpm,对于G的任一置换p, 有,即在p的作用下变为某一元素ai,依据元素k的等价类,故存在piG,使得,所以有:,18,依据Zk的定义,则有,p是G的任意元素,故有,GZkp1Zkp2.Zkpm,4.4.2.重要定理.,19,所以有G=Zkp1Zkp
9、2.Zkpm,G=Zkp1+Zkp2+.+Zkpm=mZk=EkZk,推论：若m,n属于同一个等价类，则Zm=Zn,4.4.2.重要定理.,*,20,设G=a1,a2,.,ag,其中a1=e,G=e,(12),(34),(12)(34); a1=e=(1)(2)(3)(4),c1(a1)=4;,a2=(12),a3=(34)=(1)(2)(34), c1(a3)=2;,a4=(12)(34), c1(a4)=0;,若把ak分解成不相交的循环的乘积,k=1,2,.,g,记c1(ak)为置换ak中1阶循环的个数,即在ak作用下保持不变的元素的个数,c1(a2)=2;,=(12)(3)(4),4.4
10、.3 1阶循环的个数及记法,21,Burnside引理.设G=a1,a2,.,ag,是N=1,2,.,n上的置换群,G在N上可引出不同的等价类,其不同的等价类的个数为：,首先以G=e,(12),(34),(12)(34)为例来分析,1,2,3,4关于G的等价类是：,1,2,3,4,贝恩塞特(Burnside)引理,意义,22,4.4 贝恩塞特(Burnside)引理,23,因此第i行求和等于c1(ai);第k列求和Zk,表中元素总和=,4.4 贝恩塞特(Burnside)引理,24,若N=1,2,.,n分解成l个等价类:,N=E1E2.E1,而且当i和k属于同一等价类时,则Zi=Zk,4.4
11、贝恩塞特(Burnside)引理,25,所以,4.4 贝恩塞特(Burnside)引理,26,例4.4.1：一个正方形分成四个格子,如图所示,每格有两种颜色可供选择，故有16种方案，,C1,C2,C3,C4,C5,C6,C7,C8,C9,C10,C11,C12,C13,C14,C15,C16,4.4 贝恩塞特(Burnside)引理,27,(a)旋转0度为不动置换,(b)旋转90度时,c3对应c4,c4对应c5,. c16对应c13,(c)旋转180度时,c3和c5互换,c4和c6互换,.,p1=(c1)(c2)(c3)(c4)(c5)(c6)(c7)(c8)(c9)(c10)(c11)(c1
12、2)(c13)(c14)(c15)(c16),p2=(c1)(c2)(c3c4c5c6)(c7c8c9c10)(c11c12)(c13c14c15c16),p3=(c1)(c2)(c3c5)(c4c6)(c7c9)(c8c10)(c11)(c12)(c13c15)(c14c16),4.4 贝恩塞特(Burnside)引理,28,(b)旋转270度时,c3被c4取代,c4被c5取代,. c16被c13取代,p4=(c1)(c2)(c6c5c4c3)(c10c9c8c7)(c11c12)(c16c15c14c13),p1=(c1)(c2)(c3)(c4)(c5)(c6)(c7)(c8)(c9)(c
13、10)(c11)(c12)(c13)(c14)(c15)(c16),p2=(c1)(c2)(c3c4c5c6)(c7c8c9c10)(c11c12)(c13c14c15c16),p3=(c1)(c2)(c3c5)(c4c6)(c7c9)(c8c10)(c11)(c12)(c13c15)(c14c16),=(16+2+4+2)/4=6,4.4 贝恩塞特(Burnside)引理,29,例4.4.2 一个圆环,按顺时针方向在0度,90度,180度,270度位置上装一红或蓝色的珠子,问有多少种不同的等价类,即有多少种不同的方案?刚体运动使之吻合的算一种方案.,4.4 贝恩塞特(Burnside)引理,
14、30,例4.4.2 一个圆环,按顺时针方向在0度,90度,180度,270度位置上装一红或蓝色的珠子,问有多少种不同的等价类,即有多少种不同的方案?刚体运动使之吻合的算一种方案.,4.4 贝恩塞特(Burnside)引理,对应的置换群除了和前例一样的p1,p2,p3,p4之外,还包括4类翻转,31,(e)沿XX轴翻转180度,对应有置换:,(f)沿yy轴翻转180度,对应有置换:,p5=(c1)(c2)(c3c6)(c4c5)(c7c10)(c8c9)(c11c12)(c13)(c15)(c14c16),p6=(c1)(c2)(c3c4)(c5c6)(c7c8)(c9c10)(c11c12)(
15、c13c15)(c14)(c16),4.4 贝恩塞特(Burnside)引理,32,(g)沿对角线13翻转180度,对应有置换:,(h)沿对角线24翻转180度,对应有置换:p8=(c1)(c2)(c3c5)(c4)(c6)(c7c9)(c8)(c10)(c11)(c12)(c13c16)(c14c15),p7=(c1)(c2)(c3)(c4c6)(c5)(c7)(c8c10)(c9)(c11)(c12)(c13c14)(c15c16),4.4 贝恩塞特(Burnside)引理,33,p4=(c1)(c2)(c6c5c4c3)(c10c9c8c7)(c11c12) (c16c15c14c13),p1=(c1)(c2)(c3)(c4)(c5)(c6)(c7)(c8)(c9) (c10) (c11)(c12)(c13)(c14)(c15)(c16),
