第2节 置换的奇偶性.ppt

1、2 置换的奇偶性,重点 1、置换的乘积和逆置换的计算方法,2、置换逆序数的计算方法,3、置换逆序数的性质（前三个结论）,一、置换的乘法和逆置换,有限集：,元素个数有限的集合。,置换：,有限集上的一一变换（双射）。,设有限集 p是S上的一个置换，,记,集合上所有置换构成的集合记为,元置换群。,今后称 为n,容易发现,例如，,其中它的6个元素（即置换分别为）,前3个由第1个轮换得到，,后3个由前3个对换得到。,假设p和q是S上的两个置换，,则由上节例1知p与q,的复合qp仍然是S上的置换（双射）。,由于,于是可记,另外，,显示了置换乘法得计算过程,对任意的置换p,例1,设有两个置换,解,求,二、置

2、换的逆序数计算方法,如果置换p只把i 与j 交换而保持其他数字不变，,即,则称这样的置换为对换，,记为(i, j)。,显然，,即,置换p的像 是数字 的一个排列。,置换和排列中对换记号前后不一致，我们用(i,j)表对换，(ij)表逆序对,的一个逆序对（相对于自然排列123n而言的）。,记为N(p)。,排列 包含的逆序对的总个数称为该排,列（或置换p)的逆序数，,定义2.1,称为置换p的符号，,记为sgn(p)。,如果N(p)是偶数，,则称p是偶置换；,否则称为奇置换。,例2,设有两个置换,确定两个置换的符号。,解,置换p=35412的逆序对,(31), (32), (54), (51), (5

3、2), (41), (42),置换q=24153的逆序对,(21), (41), (43), (53),由上面两个例子能总结出求一个置换（或排列）逆序数的方法吗？,注释1,的定义容易发现,对任意的置换,后面比 小的数的个数.,后面比 小的数的个数,前面比 大的数的个数,前面比 大的数的个数,由逆序数和逆序对,后面比 小的数的个数,或,前面比 大的数的个数,的逆序数.,例3求n级置换,解,用第一种方法,置换和排列是相互唯一确定的。,因此，一个置换,的逆序和你叙述也可称为排列的逆序和逆序数。,类似地可以定义偶排列和奇排列的概念。,则,三、置换的逆序数性质,右乘对换q，相当于把p的相应位置元素对换,

4、设有两个置换,置换p可表示一些对换的乘积。先把排列p(1)p(2)p(n)通过对换化成自然排列，然后再转化置换的对换乘积,引理2.1,置换p与一个对换乘积后符号改变。,一个置换右乘一个对换就相当于对排列,证明,进行一次对换。,由于置换p与排列 的逆序数相同，,于是证明一次对换改变排列的奇偶性即可。,情形1 相邻对换,显然，除a和b外其它逆序对在两个排列中相同。,设排列为,当 时，,经对换后排列的逆序增加1个 ,当 时，,经对换后排列的逆序减少1个 ,因此，作一次相邻对换，排列改变奇偶性。,对换使排列奇偶性发生改变。,情形2 一般情形,设排列为,检查对换a与b。,一次相邻对换改变排列奇偶性，,于

5、是2m+1次相邻,命题2.2,（1）任意一个置换可表示成一些对换的积。,（1）,证明,（2）一个置换表示成一些对换的乘积时，,对换个数,的奇偶性与置换的奇偶性相同。,考虑排列,设,对换 中的p(1)和p(i)得到新的排列,设,其中 的左边第一个数为1。,对换 中的p(2)和p(l)得到新的排列,其中 的左边第一个和第二个数分别为1和2。,重复上述过程，,最后可得到数列,对应上面排列对换的置换对换分别为,则,（2）由（1）知,这表明p与s有相同的奇偶性。,置换与一个对换乘积后符号改变,推论2.3,对任意的置换p和q，,证明,有,由命题2.2（1），假设,其中由命题2.2（2）知,于是,推论2.4,证明,元对称群 中奇偶置换个数相等。,令 元对称群 中欧置换的子集为,奇置换的子集为,对任意的,由引理,2.1知,定义映射,容易证明f 和g都是单射(?)，,从而,于是由,推论2.5,证明,由推论2.2得,每个置换p和它的逆置换有相同的奇偶性。,得,作业：P87 E