组合数学(5)置换群与Pólya定理_第1页
组合数学(5)置换群与Pólya定理_第2页
组合数学(5)置换群与Pólya定理_第3页
全文预览已结束

下载本文档

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

文档简介

ACM暑期集训 组合数学（5） 置换群与Plya定理1 群的基本概念2 置换群POJ 2369 Permutations 求置换P的秩k（order）：Pk=IPOJ 1026 Cipher 求置换P的k次幂Pk。题目大意：首先输入长度为n的数字串构成置换P。然后求字符序列Src进行k次置换后的字符序列。POJ 1721 CARDS 已知置换P的k次幂Pk，求P（是k次方根吗）2 置换的奇偶性POJ 3128 Leonardos Notebook 已知置换P，求一个置换M，使P=M2刘汝佳的分析：考虑某个置换的平方。对于其中长度为奇数的轮换，平方以后这个轮换仍然为一个轮换只是元素顺序换了。一个长度为偶数的轮换，平方以后就变为两个大小相等的轮换了。因此，对于给定的置换，当中所有长度为奇数的轮换，可以直接当做是它原先平方产生的。而长度为偶数的轮换，必须一一配对，当做原先拆出来的。满足这个条件，就是平方。3 Plya波利亚定理应用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)(4)(5)(6),(1)(2)(3546)(类似的有6个), (1)(2)(34)(56)(类似的有3个),(12)(35)(46)(类似的有6个), (253)(164) (类似的有8个)。所以例2：将等边三角形的三个顶点用红、蓝、绿三种颜色进行着色,问有多少种不同的着色方案? 如果 (1) 经旋转能重合的方案认为是相同的？ (2) 经旋转和翻转能重合的方案认为是相同的？解 (1) 等边三角形的三个顶点分别标记为1,2,3. 1,2,3上的置换群为 G=e,(123),(132)其循环指标为所求染色方案数为 (2) 只是将(1)中的置换群变成 G=e,(123),(132),(1)(23),(2)(13),(3)(12)其循环指标为 所求染色方案数为：POJ 2409 Let it Bead 用M种颜色的宝石嵌套长度为N的项链，求出本质不同的方案数。分旋转和翻转
人人文库> 全部分类> 行业资料 > 管理策划

温馨提示

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

最新文档

评论

0/150

提交评论