组合数学(5)置换群与Pólya定理-海文库
全站搜索：
您现在的位置：&>&&>&数学
组合数学(5)置换群与Pólya定理
ACM暑期集训
组合数学（5） 置换群与Pólya定理1
群的基本概念设非空集合A，运算?，如果对于?a,b?A,都有a?b?A，则称?为A上的二元运算。二元运算的性质（1）封闭性（2）可结合性：a?(b?c)?(a?b)?c（3）可交换性：a?b?b?a（4）单位元：a?e?e?a?a（5）逆元：a?b?b?a?e，则a?1?b代数系统?A，???是非空集合A上的二元运算。设给定代数系统?G，??，满足下述条件：（1）运算?是封闭的（2）运算?是可结合的（3）存在单位元e（4）对于?a?G,存在逆元a?1?G则称集合G在运算?下是一个群，记作群G??G，??。如果G是有限集合，称G为有限群。否则，称G为无限群。2
置换群n次置换：集合X??1，2，3，?,n?到自身的双射????123?n??例如：?ks???12341k2k3????kn???3241???
n次置换共有n!个不同的置换。设X上的置换s和t，置换的乘法s?t仍是X上的一个置换，且定义为s?t(i)?t(s(i))。一般地，s?t?t?s。即置换的乘法无交换律。例如s???1234??4??3241???t???123??4123???
则s?t???1234234???12??3241?????34???1?4123???????2134???称I?123?n?X????123?n??为恒等置换。?s???123?n??的逆置换为s?1???kk??12k3?kn??k1k2k3?kn???123?n???设G??t1,t2,?,tm?是由集合X的置换组成的集合，G在置换的乘法运算下构成一个群，称为置换群。
集合X上的全体置换在置换乘法下构成一个n次对称群，记作SnS??123??123??123??123??123??123??3??????123???,???231???,???312???,???132???,???321???,???213?????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
置换的奇偶性集合X的置换s的置换图中，每一个连通分支称为一个轮换。所有的轮换构成了X的一个划分。例如，f?????????表示为f??14569???2378???101213???11???1415?轮换?a1a2?ak?只与元素的相邻状况有关。如?123???231???312?长度为k的轮换，称为k元轮换。
k元轮换与一个1元轮换相乘时，1元轮换可以省略。如?132???4???132?如果两个轮换?a1a2a3?ak?与?b1b2b3?bl?没有相同的文字，则称两个轮换是不相交的。不相交的两个轮换的乘积是可交换的。 如?1324???56???56???1324?任何一个置换都能表示成若干个互不相交的轮换的乘积，且表示法是唯一的。
例如，f???????????1342???56???7???8???1342???56?恰由一个二元轮换构成（其他轮换的长度都为1）的置换t??ij?称为一个对换（或换位）。f???????????1???26???3???4???5???7???8???26?一个置换与一个对换的乘积，这个置换仅有两个元素换了位置。 例如，f???12345???45123?????14253?t??23?则有，f?t??14253???23????12345???12345??45123???????13245??????12345???45132????[143]?[25]定理：任何一个轮换都可表示成若干个对换（换位）之积。若一个置换可分解成奇数个对换之积，则称为奇置换；若分解成偶数个对换之积，则称为偶置换。
例如，f???1234567???1576243?????25???37???46?是奇置换。t???12345??
?12345?????1???2???3???4???5?是偶置换。对称群Sn共有n!个置换，其中奇、偶置换各占一半。S中的所有偶置换构成一个1n2(n!)阶的子群，称为交代群，记作An。S??123??123??????123??，?3????213??，??123????321??，??123????132??，??123????231??，??123????312???? ??????1???2??3?，?12?，?13?，?23?，?123?，?132??故有，A3???1???2???3?，?123?，?132??[123]???123???123??123??231???????213???????321?????12???13?POJ 3128 Leonardo's Notebook
已知置换P，求一个置换M，使P=M2刘汝佳的分析：考虑某个置换的平方。对于其中长度为奇数的轮换，平方以后这个轮换仍然为一个轮换只是元素顺序换了。一个长度为偶数的轮换，平方以后就变为两个大小相等的轮换了。因此，对于给定的置换，当中所有长度为奇数的轮换，可以直接当做是它原先平方产生的。而长度为偶数的轮换，必须一一配对，当做原先拆出来的。满足这个条件，就是平方。 3
Pólya波利亚定理X??1，2，?，n?是对象的集合，C??c1,c2,?,cm?是颜色的集合。X中的对象按所有可能的方式染以C中的颜色，G是X上任一置换群。如果g?G，设?i(g)表示g中长度为i的轮换的个数，如?1(g)表示g中长 度为1的轮换的个数，称为g的不变元的个数。多项式P(G;x1,x2,?,xn)?11(g)Gx??22(g)?xn(g)n称为G的轮换指数。g?x?1?G?n(g)??1(g)??2(g)??
??n(g)???i(g)称为g的轮换个数。i?1Polya定理
2G是X上的置换群，用m种颜色染n个对象，则不同的染色方案数为P(G;m,m,?,m)?1??2(g)????n(g)Gm?1(g)g??G应用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个)}。所以l?1[mc(a1)?mc(a2)???mc(a24)]G
?(26?6?23?3?24?6?23?8?22)/24?10例2：将等边三角形的三个顶点用红、蓝、绿三种颜色进行着色,问有多少种不同的着色方案? 如果(1) 经旋转能重合的方案认为是相同的？(2) 经旋转和翻转能重合的方案认为是相同的？解 (1) 等边三角形的三个顶点分别标记为1,2,3. {1,2,3}上的置换群为
G={e,(123),(132)}其循环指标为P1G(x1,x2,x3)?3(x31?2x3) 所求染色方案数为P3,3)?1G(3,3(33?2?3)?11(2) 只是将(1)中的置换群变成G={e,(123),(132),(1)(23),(2)(13),(3)(12)}其循环指标为P1G(x1,x2,x3)?6(x31?2x3?3x1x2)
所求染色方案数为：P,3)?1G(3,36(33?2?3?3?32)?10POJ 2409 Let it Bead
用M种颜色的宝石嵌套长度为N的项链，求出本质不同的方案数。分旋转和翻转两种情况讨论，翻转的对称轴又分为两种：顶点与中心的连线为轴，顶点连线的中点与中心的连线为轴。共有2n种置换。
上一篇： 下一篇：
All rights reserved Powered by
copyright &copyright 。文档资料库内容来自网络，如有侵犯请联系客服。扫二维码下载作业帮
2亿+学生的选择
下载作业帮安装包
扫二维码下载作业帮
2亿+学生的选择
群论中 （1 2 3）（2 3 4）（1 4）（2 3）=?以下是在网上找到的解题过程,看不懂设 1 =（1 2 3）,2=（2 3 4）,3=（1 4）,4=（2 3）,则我们要计算置换的乘积 1*2*3*4 我们先计算 （1）,因为 4=（2 3）不含1,所以 4不变1,即 4 （1）=1,3 4 （1）= 3（ 4（1） ）= 3（1）=4.2 3 4 （1）= 2 （ 3 4（1） ）= 2（4）=2.1 2 3 4（1）= 1 （ 2 3 4（1） ）= 1 （2）=3.即 （1）=3.接下去我们计算 （3）.有 4 （3）=2,3 4（3）=2,2 3 4（3）=3,1 2 3 4（3）=1.即 （3）=1 依照上面过程,可计算出 （2）=4,（4）=2.于是 =（1 3）（2 4）.写成置换的形式是
扫二维码下载作业帮
2亿+学生的选择
我给一个算法吧：首先我有一个结论：即：(abc)=(bca)=(cab);这个在轮换里是没有错的,还有(ab)=(ba),且(ab)(ba)=e,(e即不做轮换）,(abc)=(ab)(bc);那就由以上三个公式我们来算下吧：(123)(234)(14)(23)=(12)(23)(23)(34)(14)(23)=(12)(34)(41)(23)=(12)(341)(23)=(12)(413)(23)=(12)(41)(13)(32)=(21)(14)(132)=(214)(132)=(421)(213)=(42)(21)(21)(13)=(24)(13)=(13)(24).上面的方法,就我的想法是尽量把两个相邻的轮换作合并,然后全合并为三阶轮换后,作相应的变化分解为2阶轮换,尽量找出满足(ab)(ba)=e的分解,那么以上的轮换式的计算就容易了,但我个人在4阶以上的运算,还没有找出适合的算法,一般都是把它化为三阶或2阶的轮换,通过以上的方法进行化简,有兴趣的话可以一起研究下一般轮换的计算方法.
为您推荐：
其他类似问题
扫描下载二维码> 问题详情
设G为所有n阶非奇异（满秩)矩阵的集合，矩阵乘法运算。作为定义在G上的二元运算，证明：是一个不可交换群．
悬赏：0&答案豆
提问人：匿名网友
发布时间：
设G为所有n阶非奇异(满秩)矩阵的集合，矩阵乘法运算。作为定义在G上的二元运算，证明：是一个不可交换群．
您可能感兴趣的试题
1设集合S={α，β，γ，δ}，在S上定义一个二元运算*，运算规则如表5-14所示，证明：〈S，*〉是一个循环群．&&表5-14*αβγδααβγδββαδγγγδβαδδγαβ2设S={a，b，c，d}，G={fe，f1，f2，f3}，其中&&&&&&&&&&证明：是S的一个置换群，并求由诱导的S上的二元关系．3考察从蓝、黄、白三种颜色的珠子中选取5粒串成的手镯，如果将一只手镯经顺时针旋转而得到的手镯看做是与原手镯没有区别的手镯，并称这两只手镯是旋转等价的，那么，在考虑旋转等价的条件下，不同手镯的数目是多少?4设G=R×R，R为实数集，G上的一个二元运算+定义为&&〈x1，y1〉+〈x2，y2〉=〈x1+x2，y1+y2〉．&&又设H={(x，y)|y=2x}，证明：(G，+)为阿贝尔群，(H，+)为子群，并求(x0，y0)H，(x0，y0)∈G．
我有更好的答案
相关考试课程
请先输入下方的验证码查看最佳答案
图形验证：
验证码提交中……
找答案会员
享三项特权
找答案会员
享三项特权
找答案会员
享三项特权
选择支付方式：
支付宝付款
郑重提醒：支付后，系统自动为您完成注册
请使用微信扫码支付(元)
支付后，系统自动为您完成注册
遇到问题请联系在线客服QQ：
请您不要关闭此页面,支付完成后点击支付完成按钮
遇到问题请联系在线客服QQ：
恭喜您！升级VIP会员成功
常用邮箱：
用于找回密码
确认密码：温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！&&|&&
做过工,开过荒,教过书,扛过枪,当过干部仍在党,现任公司董事长。业余以探索天地人和谐之道为乐！
LOFTER精选
网易考拉推荐
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
阅读(8208)|
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
历史上的今天
loftPermalink:'',
id:'fks_080074',
blogTitle:'（原创）置换符号ε入门（图）',
blogAbstract:'指标运算的工具之二',
blogTag:'',
blogUrl:'blog/static/',
isPublished:1,
istop:false,
modifyTime:8,
publishTime:6,
permalink:'blog/static/',
commentCount:24,
mainCommentCount:24,
recommendCount:5,
bsrk:-100,
publisherId:0,
recomBlogHome:false,
currentRecomBlog:false,
attachmentsFileIds:[],
groupInfo:{},
friendstatus:'none',
followstatus:'unFollow',
pubSucc:'',
visitorProvince:'',
visitorCity:'',
visitorNewUser:false,
postAddInfo:{},
mset:'000',
remindgoodnightblog:false,
isBlackVisitor:false,
isShowYodaoAd:false,
hostIntro:'做过工,开过荒,教过书,扛过枪,当过干部仍在党,现任公司董事长。业余以探索天地人和谐之道为乐！',
hmcon:'1',
selfRecomBlogCount:'0',
lofter_single:''
{list a as x}
{if x.moveFrom=='wap'}
{elseif x.moveFrom=='iphone'}
{elseif x.moveFrom=='android'}
{elseif x.moveFrom=='mobile'}
${a.selfIntro|escape}{if great260}${suplement}{/if}
{list a as x}
推荐过这篇日志的人：
{list a as x}
{if !!b&&b.length>0}
他们还推荐了：
{list b as y}
转载记录：
{list d as x}
{list a as x}
{list a as x}
{list a as x}
{list a as x}
{if x_index>4}{break}{/if}
${fn2(x.publishTime,'yyyy-MM-dd HH:mm:ss')}
{list a as x}
{if !!(blogDetail.preBlogPermalink)}
{if !!(blogDetail.nextBlogPermalink)}
{list a as x}
{if defined('newslist')&&newslist.length>0}
{list newslist as x}
{if x_index>7}{break}{/if}
{list a as x}
{var first_option =}
{list x.voteDetailList as voteToOption}
{if voteToOption==1}
{if first_option==false},{/if}&&“${b[voteToOption_index]}”&&
{if (x.role!="-1") },“我是${c[x.role]}”&&{/if}
&&&&&&&&${fn1(x.voteTime)}
{if x.userName==''}{/if}
网易公司版权所有&&
{list x.l as y}
{if defined('wl')}
{list wl as x}{/list}【图文】置换群_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
&&置换群,置换,置换乘法没有交换律,置换群的概念,四次对称群,循环置换的性质
大小：266.50KB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢