组合数学(5)置换群与Pólya定理教学总结_第1页
组合数学(5)置换群与Pólya定理教学总结_第2页
组合数学(5)置换群与Pólya定理教学总结_第3页
组合数学(5)置换群与Pólya定理教学总结_第4页
组合数学(5)置换群与Pólya定理教学总结_第5页
已阅读5页,还剩4页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、组合数学(5)置换群与P ol ya定理精品资料ACM暑期集训 组合数学(5)置换群与Polya定理1 群的基本概念设非空集合A,运算,如果对于a, b A,都有a b A,则称 为 A上的二元运算。二元运 算的性质(1) 封闭性(2) 可结合性:a (b c) (a b) c(3可交换性:abba(4) 单位元:a e e a a(5) 逆元:a b b a e,贝U a 1 b代数系统A,是非空集合A上的二元运算。设给定代数系统G ,,满足下述条件:(1) 运算是封闭的(2) 运算是可结合的(3) 存在单位元e(4) 对于 a G ,存在逆元a 1 G则称集合G在运算 下是一个群,记作群G

2、 G,。如果G是有限集合,称G为有限群。否则,称G为无限群。2 置换群n次置换:集合X1,2,3, ,n到自身的双射123n例如:s 1 2 3 4k1k2k3kn3 2 4 1n次置换共有n!个不同的置换设X上的置换s和t,置换的乘法st仍是X上的一个置换,且定义为s t(i) t(s(i)。一般地,s t t s°即置换的乘法无交换律。123 41234例如st324 14123“ 1 234123 4123 4则s t3 241412 3213 4k1k3nkn为恒等置换的逆置换为s1k1k2 k3knn设Gt1 , t2 , ,tm是由集合X的置换组成的集合,G在置换的乘法运

3、算下构成一个群,称为置换群。集合X上的全体置换在置换乘法下构成一个n次对称群,记作Sn12 312 312312 312 312 3S3123,231,312,132,321,213POJ 2369 Permutations 求置换 P 的秩 k (order ) : Pk=I仅供学习与交流,如有侵权请联系网站删除谢谢2精品资料POJ 1026 Cipher求置换P的k次幕Pk。题目大意:首先输入长度为 n的数字串构成置换P。然后求字符序列Src进行k次置换后的字符序列。POJ 1721 CARDS已知置换P的k次幕Pk,求P (是k次方根吗) 任何一个置换都能表示成若干个互不相交的轮换的乘积

4、,且表示法 是唯一的。“1 2 3 4 5 6 7 8例如,f1342 56 7 81342 563 1 4 2 6 5 7 8恰由一个二元轮换构成(其他轮换的长度都为1)的置换t i j 称为一个对换(或换位)。仅供学习与交流,如有侵权请联系网站删除谢谢4精品资料仅供学习与交流,如有侵权请联系网站删除谢谢#精品资料2 置换的奇偶性集合X的置换s的置换图中,每一个连 通分支称为一个轮换。所有的轮换构成了 X的一个划分。比12 3456789101112131415例如,f43 7569821121113101514表示为f14 5 6923781012131114 15轮换a1a2ak只与元素

5、的相邻状况有关。如123231312长度为k的轮换,称为k元轮换。k元轮换与一个1元轮换相乘时,1元轮换可以省略。如1324132如果两个轮换a1a2a3 ak与b1b2b3 bl没有相同的文字,则称 两个 轮换是不相交的。不相 交的两个轮换的乘积是 可交换的。如 1324565613241234 567 8f126 3 4 5 7 8261634 527 8一个置换与一个对换的 乘积,这个置换仅有两 个元素换了位置例如,f12 3 4 54 5 12 314253t 23则有,f t 14253 2312 3 4 54 5 12 312 3 4 54 5 13 2143 25定理:任何一个轮

6、换都 可表示成若干个对换(换位)之积若一个置换可分解成奇 数个对换之积,则称为 奇置换; 若分解成偶数个对换之 积,则称为偶置换。例如,f25 37 46是奇置换仅供学习与交流,如有侵权请联系网站删除谢谢5精品资料仅供学习与交流,如有侵权请联系网站删除谢谢#精品资料是偶置换1 2 3 4 5t12 3 4 51 2 3 4 5仅供学习与交流,如有侵权请联系网站删除谢谢#精品资料仅供学习与交流,如有侵权请联系网站删除谢谢6精品资料Sn中的所有偶置扌奂构成一个孑n)阶的子群,称为交代群,记作An1231 231 2312312 3123S31232 133 2113 2231312123,12,

7、13:,23,123, 132故有,A3123,123, 13212312 312 3123121323121 33 2 1对称群Sn共有n !个置换,其中奇、偶置 换各占一半。X 1,2, ,n是对象的集合,C c1,c2, , cm是颜色的集合。X中的对象按所有可能的 方式染以C中的颜色,G是X上任一置换群。如果g G,设j(g)表示g中长度为i的轮换的个数,女口1 (g)表示g中长度为1的轮换的个数,称为g的不变元的个数多项式 P(G;x1,x2,(g)1(g)2(g),Xn)Ggx 1(g)x 2(g)12xnn(g)称为G的轮换指数。nn(g)i(g)称为g的轮换个数i 1POJ 3

8、128 Leonardo's Notebook已知置换 P,求一个置换 M,使P=M2刘汝佳的分析:考虑某个置换的平方。对于其中长度为奇数的轮换, 平方以后这个轮换仍然为一个轮换只是元素顺序换了。一个长度为偶 数的轮换,平方以后就变为两个大小相等的轮换了。因此,对于给定 的置换,当中所有长度为奇数的轮换,可以直接当做是它原先平方产 生的。而长度为偶数的轮换,必须一一配对,当做原先拆出来的。满 足这个条件,就是平方。Polya定理1G是X上的置换群,用m种颜色染n个对象,则不同的染色方案数为lG3 P o lya波利亚定理1m (gp)其中 Gg1, g2, ,gpPolya定理2G是X

9、上的置换群,用m种颜色染n个对象,则不同的染色方案数为P(G;m, m,m)1Ggm 1(g)2(g)(g)仅供学习与交流,如有侵权请联系网站删除谢谢7精品资料10Polya定理3G是X上的置换群,用m种颜色染n个对象,其中恰有ai个对象染成g色 (i 1,2, m)的不同的染色方案数 为1Bg|hG(1,2, , n ) Pa1a2 (1,2, , n )G 1,2, n 012n n其中hG( 1, 2, n)是G中形如1 12 2 n n的置换个数Paa2 ( 1, 2, n)表示具有下述性质的染 色的个数:在这种染色下,对象集 合X1,2,n的形如1 12 2 n n的每一划分的每一类

10、染成同色,而 染成ci色(i 1,2,m)的对象恰有ai个。应用Polya定理的解题思路:(1 )认定对象集合X(2) 找出置换群G(3) 分析每个置换的轮换指数(4) 代入Polya 定理例1 :正六面体6个面用红、蓝着色,有多少种方案?旋转重合算同一种方 案。解:使正六面体重合的刚体运动有5类:绕对面中心连线旋转正负90度(共3*2种);旋转180度(共3种);绕对棱中点连线旋转180度(共6 种);绕对角线旋转正负120度(共4*2种);不动变换。以1,2,3,4,5,6分别记正六面体的上,下,左,右,前,后六个面,则G=(1)(2)(3)(5)(6),(1)(2)(3546)(类似的有

11、 6 个),(1)(2)(34)(56)(类似的有 3 个),(12)(35)(46)(类似的有 6 个),(253)(164)( 类似的有8个)。所以1l咅mc®mc(a2)mc(a24)Gl仅供学习与交流,如有侵权请联系网站删除谢谢5(266 23 3 246 238 22)/24例2 :将等边三角形的三个顶点用红、蓝、绿三种颜色进行着色 ,问有多少种不同的着色方案?如果(1)经旋转能重合的方案认为是相同的?经旋转和翻转能重合的方案认为是相同的?解(1)等边三角形的三个顶点分别标记为1,2,3. 1,2,3上的置换群为G=e,(123),(132)其循环指标为Pg(X1,X2,X3) - (X132X3)所求染色方案数为Pg(3,3,3) -(3332 3)11只是将(1)中的置换群变成G=e,(123),(132),(1)(23),(2)(13),(3)(12)其循环指标为 PG(x1,x2,x3) -(xf 2x3 3x1

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论