2 置换的奇偶性置换的奇偶性重点重点重点重点 1 1 1 1、置换的乘积和逆置换的计算方法、置换的乘积和逆置换的计算方法、置换的乘积和逆置换的计算方法、置换的乘积和逆置换的计算方法2 2 2 2、置换逆序数的计算方法、置换逆序数的计算方法、置换逆序数的计算方法、置换逆序数的计算方法3 3 3 3、置换逆序数的性质（前三个结论）、置换逆序数的性质（前三个结论）、置换逆序数的性质（前三个结论）、置换逆序数的性质（前三个结论）一、置换的乘法和逆置换一、置换的乘法和逆置换一、置换的乘法和逆置换一、置换的乘法和逆置换有限集有限集有限集有限集：元素个数有限的集合。元素个数有限的集合。元素个数有限的集合。元素个数有限的集合。置换置换置换置换：有限集上的一一变换（双射）。有限集上的一一变换（双射）。有限集上的一一变换（双射）。有限集上的一一变换（双射）。设有限集设有限集设有限集设有限集 p p是是是是S S上的一个置换，上的一个置换，上的一个置换，上的一个置换，记记记记集合上所有置换构成的集合记为集合上所有置换构成的集合记为集合上所有置换构成的集合记为集合上所有置换构成的集合记为元置换群。元置换群。元置换群。元置换群。今后称今后称今后称今后称 为为为为n n容易发现容易发现容易发现容易发现例如，例如，例如，例如，其中它的其中它的其中它的其中它的6 6个元素（即置换分别为）个元素（即置换分别为）个元素（即置换分别为）个元素（即置换分别为）前前前前3 3个由第个由第个由第个由第1 1个轮换得到，个轮换得到，个轮换得到，个轮换得到， 后后后后3 3个由前个由前个由前个由前3 3个对换得到。个对换得到。个对换得到。个对换得到。假设假设假设假设p p和和和和q q是是是是S S上的两个置换，上的两个置换，上的两个置换，上的两个置换， 则由上节例则由上节例则由上节例则由上节例1 1知知知知p p与与与与q q的复合的复合的复合的复合qpqp仍然是仍然是仍然是仍然是S S上的置换（双射）。上的置换（双射）。上的置换（双射）。上的置换（双射）。由于由于由于由于于是可记于是可记于是可记于是可记另外，另外，另外，另外，显示了置换乘法显示了置换乘法显示了置换乘法显示了置换乘法得计算过程得计算过程得计算过程得计算过程对任意的置换对任意的置换对任意的置换对任意的置换p p, ,例例例例1 1 设有两个置换设有两个置换设有两个置换设有两个置换解解解解求求求求二、置换的逆序数计算方法二、置换的逆序数计算方法二、置换的逆序数计算方法二、置换的逆序数计算方法如果置换如果置换如果置换如果置换p p只把只把只把只把i i 与与与与j j 交换而保持其他数字不变，交换而保持其他数字不变，交换而保持其他数字不变，交换而保持其他数字不变，即即即即则称这样的置换为对换，则称这样的置换为对换，则称这样的置换为对换，则称这样的置换为对换， 记为记为记为记为( ( ( (i, ji, j) ) ) )。显然，显然，显然，显然，即即即即置换置换置换置换p p的像的像的像的像 是数字是数字是数字是数字 的一个排列。的一个排列。的一个排列。的一个排列。如果如果如果如果 时时时时则称则称则称则称 是排列是排列是排列是排列置换和排列中对换记号前置换和排列中对换记号前置换和排列中对换记号前置换和排列中对换记号前后不一致，我们用后不一致，我们用后不一致，我们用后不一致，我们用( (i,ji,j) )表表表表对换，对换，对换，对换，( (ij ij) )表逆序对表逆序对表逆序对表逆序对的一个逆序对（相对于自然排列的一个逆序对（相对于自然排列的一个逆序对（相对于自然排列的一个逆序对（相对于自然排列123123123123n n而言的）。而言的）。而言的）。而言的）。记为记为记为记为N N( (p p) )。排列排列排列排列 包含的逆序对的总个数称为该排包含的逆序对的总个数称为该排包含的逆序对的总个数称为该排包含的逆序对的总个数称为该排列（或置换列（或置换列（或置换列（或置换p p) ) ) )的逆序数，的逆序数，的逆序数，的逆序数，定义定义定义定义2.12.12.12.1称为置换称为置换称为置换称为置换p p的符号，的符号，的符号，的符号，记为记为记为记为sgn(sgn(p p) )。如果如果如果如果N N( (p p) )是偶数，是偶数，是偶数，是偶数， 则称则称则称则称p p是偶置换；是偶置换；是偶置换；是偶置换； 否则称为奇置换。否则称为奇置换。否则称为奇置换。否则称为奇置换。例例例例2 2 设有两个置换设有两个置换设有两个置换设有两个置换确定两个置换的符号。确定两个置换的符号。确定两个置换的符号。确定两个置换的符号。解解解解 置换置换置换置换p p=35412=35412的逆序对的逆序对的逆序对的逆序对(31), (32), (54), (51), (52), (41), (42)(31), (32), (54), (51), (52), (41), (42)置换置换置换置换q q=24153=24153的的的的逆序对逆序对逆序对逆序对(21), (41), (43), (53)(21), (41), (43), (53)由上面两个例子能总结出求一个置换（或由上面两个例子能总结出求一个置换（或由上面两个例子能总结出求一个置换（或由上面两个例子能总结出求一个置换（或排列）逆序数的方法吗？排列）逆序数的方法吗？排列）逆序数的方法吗？排列）逆序数的方法吗？注释注释注释注释1 1 1 1的定义容易发现的定义容易发现的定义容易发现的定义容易发现对任意的置换对任意的置换对任意的置换对任意的置换后面比后面比 小的数的个数小的数的个数.后面比后面比 小的数的个数小的数的个数前面比前面比 大的数的个数大的数的个数前面比前面比 大的数的个数大的数的个数由逆序数和逆序对由逆序数和逆序对由逆序数和逆序对由逆序数和逆序对 后面比后面比 小的数的个数小的数的个数或或前面比前面比 大的数的个数大的数的个数的逆序数的逆序数的逆序数的逆序数. . . . 例例3 3求求求求n n级置换级置换级置换级置换解解用第一种方法置置置置换换和排列是相互唯一确定的。和排列是相互唯一确定的。和排列是相互唯一确定的。和排列是相互唯一确定的。 因此，一个置因此，一个置因此，一个置因此，一个置换换的逆序和你叙述也可称的逆序和你叙述也可称的逆序和你叙述也可称的逆序和你叙述也可称为为排列的逆序和逆序数。排列的逆序和逆序数。排列的逆序和逆序数。排列的逆序和逆序数。类类似地可以定似地可以定似地可以定似地可以定义义偶排列和奇排列的概念。偶排列和奇排列的概念。偶排列和奇排列的概念。偶排列和奇排列的概念。则则则则三、置换的逆序数性质三、置换的逆序数性质三、置换的逆序数性质三、置换的逆序数性质右乘对换右乘对换q，相当于把，相当于把p的的相应位置元素对换相应位置元素对换设有两个置换设有两个置换设有两个置换设有两个置换置换置换p可表示一些对换的乘积。先把排列可表示一些对换的乘积。先把排列p(1)p(2)p(n)通过通过对换化成自然排列，然后再转化置换的对换乘积对换化成自然排列，然后再转化置换的对换乘积引理引理引理引理2.12.1 置换置换置换置换p p与一个对换乘积后符号改变。与一个对换乘积后符号改变。与一个对换乘积后符号改变。与一个对换乘积后符号改变。一个置换右乘一个对换就相当于对排列一个置换右乘一个对换就相当于对排列一个置换右乘一个对换就相当于对排列一个置换右乘一个对换就相当于对排列证明证明证明证明进行一次对换。进行一次对换。进行一次对换。进行一次对换。由于置换由于置换由于置换由于置换p p与排列与排列与排列与排列 的逆序数相同，的逆序数相同，的逆序数相同，的逆序数相同，于是证明一次对换改变排列的奇偶性即可。于是证明一次对换改变排列的奇偶性即可。于是证明一次对换改变排列的奇偶性即可。于是证明一次对换改变排列的奇偶性即可。情形情形1 相邻对换相邻对换对换对换a与与b显然，除显然，除a和和b外其它逆序对在两个排列中相同。外其它逆序对在两个排列中相同。设排列为设排列为当当 时，时， 经对换后排列的逆序增加经对换后排列的逆序增加1个个 ,当当 时，时， 经对换后排列的逆序减少经对换后排列的逆序减少1个个 ,因此，作一次相邻对换，排列改变奇偶性。因此，作一次相邻对换，排列改变奇偶性。次相邻对换次相邻对换次相邻对换次相邻对换对换使排列奇偶性发生改变。对换使排列奇偶性发生改变。情形情形2 一般情形一般情形设排列为设排列为检查对换检查对换a与与b。一次相邻对换改变排列奇偶性，一次相邻对换改变排列奇偶性， 于是于是2m+1次相邻次相邻次相邻对换次相邻对换命题命题命题命题2.22.2（1 1）任意一个置换可表示成一些对换的积。）任意一个置换可表示成一些对换的积。）任意一个置换可表示成一些对换的积。）任意一个置换可表示成一些对换的积。（1 1）证明证明证明证明（2 2）一个置换表示成一些对换的乘积时，）一个置换表示成一些对换的乘积时，）一个置换表示成一些对换的乘积时，）一个置换表示成一些对换的乘积时，对换个数对换个数对换个数对换个数的奇偶性与置换的奇偶性相同。的奇偶性与置换的奇偶性相同。的奇偶性与置换的奇偶性相同。的奇偶性与置换的奇偶性相同。考虑排列考虑排列考虑排列考虑排列设设设设对换对换对换对换 中的中的中的中的p p(1)(1)和和和和p p( (i i) )得到新的排列得到新的排列得到新的排列得到新的排列设设设设其中其中其中其中 的左边第一个数为的左边第一个数为的左边第一个数为的左边第一个数为1 1。对换对换对换对换 中的中的中的中的p p(2)(2)和和和和p p( (l l) )得到新的排列得到新的排列得到新的排列得到新的排列其中其中其中其中 的左边第一个和第二个数分别为的左边第一个和第二个数分别为的左边第一个和第二个数分别为的左边第一个和第二个数分别为1 1和和和和2 2。重复上述过程，重复上述过程，重复上述过程，重复上述过程， 最后可得到数列最后可得到数列最后可得到数列最后可得到数列对应上面排列对换的置换对换分别为对应上面排列对换的置换对换分别为对应上面排列对换的置换对换分别为对应上面排列对换的置换对换分别为则则则则（2 2）由（）由（）由（）由（1 1）知）知）知）知这表明这表明这表明这表明p p与与与与s s有相同的奇偶性。有相同的奇偶性。有相同的奇偶性。有相同的奇偶性。置换与一个对换乘积置换与一个对换乘积置换与一个对换乘积置换与一个对换乘积后符号改变后符号改变后符号改变后符号改变推论推论推论推论2.32.3 对任意的置换对任意的置换对任意的置换对任意的置换p p和和和和q q，证明证明证明证明有有有有由命题由命题由命题由命题2.22.2（1 1），假设），假设），假设），假设其中由命题其中由命题其中由命题其中由命题2.22.2（2 2）知）知）知）知于是于是于是于是推论推论推论推论2.42.4证明证明证明证明 元对称群元对称群元对称群元对称群 中奇偶置换个数相等。中奇偶置换个数相等。中奇偶置换个数相等。中奇偶置换个数相等。令令令令 元对称群元对称群元对称群元对称群 中偶置换的子集为中偶置换的子集为中偶置换的子集为中偶置换的子集为奇置换的子集为奇置换的子集为奇置换的子集为奇置换的子集为对任意的对任意的对任意的对任意的由引理由引理由引理由引理2.12.1知知知知定义映射定义映射定义映射定义映射容易证明容易证明容易证明容易证明f f 和和和和g g都是单射都是单射都是单射都是单射(?)(?)，从而从而从而从而于是由于是由于是由于是由 推论推论推论推论2.52.5证明证明证明证明 由推论由推论由推论由推论2.22.2得得得得 每个置换每个置换每个置换每个置换p p和它的逆置换有相同的奇偶性。和它的逆置换有相同的奇偶性。和它的逆置换有相同的奇偶性。和它的逆置换有相同的奇偶性。得得得得作业：作业：P87 Ex 1, 2 (4), 4, 5 (2)例例例例5 5 已知已知已知已知p p的逆序数为的逆序数为的逆序数为的逆序数为a a ，求逆置换的逆序数。，求逆置换的逆序数。，求逆置换的逆序数。，求逆置换的逆序数。解解解解设设设设 且且且且则则则则即即即即 是是是是p p的逆序的逆序的逆序的逆序 是是是是 的逆序。的逆序。的逆序。的逆序。因此，因此，因此，因此，p p和它的逆置换逆序数相等。和它的逆置换逆序数相等。和它的逆置换逆序数相等。和它的逆置换逆序数相等。