资源描述：
《离散 (37).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、4.3置换4.3.1置换的概念4.3.2置换的积与逆4.3.3轮换4.3.4奇置换与偶置换4.3.1置换的概念定义4.3.1设A＝{1,2,…,n}，若f是A到A的双射，则称f是A上的n元置换，简称置换，记作f＝4.3.1置换的概念例4.3.1设集合A＝{1,2,3,4,5}，双射f：A→A且f(1)＝4,f(2)＝5,f(3)＝2,f(4)＝1,f(5)＝3。以置换形式表示f为f＝4.3.1置换的概念例4.3.2设集合A＝{1,2,3}，A上的全部置换f1＝f2＝f3＝f4＝f5＝f6＝4.3.1置换的概念注记作{1,2,…,n}上的置换f,就是构造{1,2,…,n}的一个全排
2、列，即f(1)f(2)…f(n)是{1,2,…,n}的一个全排列。f＝4.3.2置换的积与逆定义4.3.2设A为有限集，f与g均为集合A上的置换，置换f与g的积即为f与g的复合函数gf，记作gf。4.3.2置换的积与逆例如，f＝g＝则fg＝＝gf＝＝4.3.2置换的积与逆定义4.3.3设A＝{1,2,…,n}，A上的置换f＝则f的逆即为f的逆函数f-1，仍记作f-1。即f-1＝4.3.2置换的积与逆例如，f＝则f-1＝＝4.3.2置换的积与逆注记(1)设A＝{1,2,…,n}A上的恒等置换e＝对A上的任意置换f，显然fe＝f＝ef。4.3.2置换的积与逆(2)设n为整数，f为有限
3、集A上的置换，定义f的n次幂fn为：fn＝并约定f0＝e(e为A上的恒等置换)4.3.2置换的积与逆递归定义置换f的n次幂fn为①f0＝e(e为A上的恒等置换)②fn＝fn-1f(n为正整数)③fn＝fn+1f-1(n为负整数)容易验证fnfm＝fn+mn,m为整数(fn)m＝fnmn,m为整数4.3.2置换的积与逆定义4.3.4设f为有限集A上的置换，使fk等于恒等置换的最小正整数k称为f的阶。4.3.2置换的积与逆例如设f＝由于f5＝f6＝所以f的阶为64.3.3轮换g＝非轮换f＝轮换4.3.3轮换定义4.3.5设f是集合A上的置换,若f把A中元素i1映射为i2,元素i2映射
4、为i3,…,元素ik-1映射为ik,元素ik映射为i1,但其余的元素(如果还有的话)都映射为自身,则称f是集合A上的k轮换或k循环,简称为轮换或循环,记作f＝(i1,i2,…,ik)。4.3.3轮换g＝f＝＝(1,3,4,2,5,8)4.3.3轮换f＝＝(1,3,4,2,5,8)f-1＝＝(8,5,2,4,3,1)4.3.3轮换注记(1)设f＝(i1,i2,…,ik)是有限集A上的轮换，则轮换f的逆f-1＝(ik,ik-1,…,i1)(2)恒等置换e＝简称1轮换或1循环，记(1)或(2)或…或(n)，即(1)＝(2)＝…＝(n)4.3.3轮换(3)2轮换还简称为对换(4)集合A上
5、无公共元素的轮换称不相交轮换(5)轮换是置换的简洁表达，因此轮换的积与逆就是置换的积与逆4.3.3轮换例4.3.5设集合A＝{1,2,3,4,5}，f与g是A上的两个轮换，且f＝(5,3,2,4,1)，g＝(4,2,5)。则gf＝(4,2,5)(5,3,2,4,1)＝＝f-1＝＝＝(1,4,2,3,5)4.3.3轮换定理4.3.1k轮换(i1,i2,…,ik)的阶为k证明当1≤m＜k时,(i1,i2,…,ik)m＝(i1,im+1,…)≠(1)。而(i1,i2,…,ik)k＝(1)。4.3.3轮换例如设f＝＝(1,3,4,2,5,8)由于f5＝f6＝4.3.3轮换定理4.3.2设
6、f与g是集合A上不相交轮换,则fg＝gf。证明设A上不相交轮换f＝(i1,i2,…,is)与g＝(j1,j2,…,jt)任取a∈A4.3.3轮换推论4.3.1设f1,f2,…,fr是集合A上的互不相交轮换，n为正整数，则(f1f2…fr)n＝f1nf2n…frn证明n＝1时，结论成立。设n＝k时，结论成立。即(f1f2…fr)k＝f1kf2k…frk当n＝k＋1时，(f1f2…fr)n＝(f1f2…fr)k+1＝(f1f2…fr)(f1f2…fr)k＝(f1f2…fr)(f1kf2k…frk)＝f1f2…frf1kf2k…frk＝f2…frf1f1kf2k…frk＝f2…frf1
7、k+1f2k…frk＝…＝f1k+1f2k+1…frk+1＝f1nf2n…frn4.3.3轮换例4.3.6设A＝{1,2,3,4,5,6,7,8}，轮换f＝(2,3,7,6,4)，轮换g＝(1,5,8)则(fg)59＝f59g59＝f4g2＝(2,4,6,7,3)(1,8,5)＝＝4.3.3轮换g＝非轮换？＝(1,3,4,2,5)(6,7)＝(1,3,4,2,5)(6,7)(8)＝4.3.3轮换定理4.3.3每个非轮换置换都可表示为不相交轮换的积，并且除了轮换的排列次序外，表示法
