组合数学课件--第四章第二节 贝恩塞特(Burnside)引理

《组合数学课件--第四章第二节 贝恩塞特(Burnside)引理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第4章Burnside引理与Polya定理4.1群的概念14.2置换群14.3循环、奇循环与偶循环14.4Burnside引理24.5Polya定理34.6举例34.7母函数形式的Polya定理*4.8图的计数*4.9Polya定理的若干推广*11、共轭类4.4.1几个概念2、k不动置换类3、等价类.4.4.2重要定理.4.4.31阶循环的个数及记法贝恩塞特(Burnside)引理贝恩塞特(Burnside)引理24.4.1几个概念--1、共轭类Sn中任意一个置换p都能分解成若干个互不相交的循环的乘积。p=(a1a2.

2、..ak1)(b1b2...bk2)...(h1h2...hkm)共m项，其中k1+k2+...km=n,例如：(1)(23)(4567)(123)(456)(7)(134)(2)(567)3Sn中任意一个置换p都能分解成若干个互不相交的循环的乘积。设其中k阶循环出现的次数为ck,k=1,2,...,n.k阶循环出现ck次,用(k)ck表示Sn中置换可分解成如下格式(1)c1(2)c2...(n)cn1、共轭类在Sn中具有相同格式的置换全体,叫做与该格式相应的共轭类。4例：求S3中所有共轭类。5定理4.4.1Sn中属于

3、(1)c1(2)c2...(n)cn共轭类的元素个数为:1、共轭类例如：3个元素中共轭类213(123)(456)(7)=(7)(123)(456)(134)(2)(567)=(2)(134)(567)证明：首先把每个共轭类的写法标准化按格式(1)c1(2)c2...(n)cn来记。6属于(1)c1(2)c2...(n)cn共轭类的元素个数为:证明：1,2,3,...,n的全排列共n!个,每个排列都可以唯一地划分成格式为(1)c1(2)c2...(n)cn的置换。反过来,该共轭类的每个置换都可以通过这样的划分而得到；1

4、、共轭类7例如：对于6个元素的一个排列345126可以唯一地划分成任何一个共轭类。6个元素的所有共轭类如下：(1)6(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、共轭类8(1)c1(2)c2...(n)cn格式与n!个排列相比较，重复来自。(a)由循环(a1a2a3...ak)=(a2

5、a3...aka1)=...=(aka1a2...ak-1)引起,一个k阶循环重复k倍,ck个k阶循环共重复了kck倍共重复了：1、共轭类9(b)由互不相交的ck个k阶循环乘积的可交换性引起的重复：ck个k阶循环重复了ck!倍属于(1)c1(2)c2...(n)cn共轭类的元素个数为:共重复了：1、共轭类***102、k不动置换类设G是1,2,...,n的置换群,G是Sn的一个子群,若k是1到n中的某个整数,G中使k保持不变的置换全体,记以Zk,叫做G中使k保持不动的置换类,或简称k不动置换类。如G={e,(12),(

6、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不动置换类为:Z2={e,(34)}11定理4.4.2群G中关于k的不动置换类Zk是G的一个子群。证明:(1)封闭性:若p1,p2分别是k不动的两个置换,(2)结合律:(3)单位元素:(4)逆元素:p3=p1p2也是k不动的置换.2k不动置换类****12例如:G={e,(12),(34),(12)

7、(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)传递性。3.等价类.意义134.4.2.重要定理.定理4.4.3EkZk=G,k=1,2,...,n.Z1={e,(34)}E1={1,2}例如:G={e,(12),(34),(12)(34)}144.4.2.重要定理.

8、定理4.4.3EkZk=G,k=1,2,...,n.证明:设

9、Ek

10、=m,既然a1(=k),a2,...,am属于同一等价类,故存在属于G的置换pi使得即置换pi使数k变为等价类中的ai.P={p1,p2,...,pm}是属于群G的置换的集合。设Ek={a1(=k),a2,...,am},a1(=k),a2,...,a