第2节 置换的奇偶性.ppt

2置换的奇偶性 重点1 置换的乘积和逆置换的计算方法 2 置换逆序数的计算方法 3 置换逆序数的性质 前三个结论 一 置换的乘法和逆置换 有限集 元素个数有限的集合 置换 有限集上的一一变换 双射 设有限集p是S上的一个置换 记 集合上所有置换构成的集合记为 元置换群 今后称为n 容易发现 例如 其中它的6个元素 即置换分别为 前3个由第1个轮换得到 后3个由前3个对换得到 假设p和q是S上的两个置换 则由上节例1知p与q 的复合qp仍然是S上的置换 双射 由于 于是可记 另外 显示了置换乘法得计算过程 对任意的置换p 例1 设有两个置换 解 求 二 置换的逆序数计算方法 如果置换p只把i与j交换而保持其他数字不变 即 则称这样的置换为对换 记为 i j 显然 即 置换p的像是数字的一个排列 置换和排列中对换记号前后不一致 我们用 i j 表对换 ij 表逆序对 的一个逆序对 相对于自然排列123 n而言的 记为N p 排列包含的逆序对的总个数称为该排 列 或置换p 的逆序数 定义2 1 称为置换p的符号 记为sgn p 如果N p 是偶数 则称p是偶置换 否则称为奇置换 例2 设有两个置换 确定两个置换的符号 解 置换p 35412的逆序对 31 32 54 51 52 41 42 置换q 24153的逆序对 21 41 43 53 由上面两个例子能总结出求一个置换 或排列 逆序数的方法吗 注释1 的定义容易发现 对任意的置换 后面比小的数的个数 后面比小的数的个数 前面比大的数的个数 前面比大的数的个数 由逆序数和逆序对 后面比小的数的个数 或 前面比大的数的个数 的逆序数 例3 求n级置换 解 用第一种方法 置换和排列是相互唯一确定的 因此 一个置换 的逆序和你叙述也可称为排列的逆序和逆序数 类似地可以定义偶排列和奇排列的概念 则 三 置换的逆序数性质 右乘对换q 相当于把p的相应位置元素对换 设有两个置换 置换p可表示一些对换的乘积 先把排列p 1 p 2 p n 通过对换化成自然排列 然后再转化置换的对换乘积 引理2 1 置换p与一个对换乘积后符号改变 一个置换右乘一个对换就相当于对排列 证明 进行一次对换 由于置换p与排列的逆序数相同 于是证明一次对换改变排列的奇偶性即可 情形1相邻对换 显然 除a和b外其它逆序对在两个排列中相同 设排列为 当时 经对换后排列的逆序增加1个 当时 经对换后排列的逆序减少1个 因此 作一次相邻对换 排列改变奇偶性 对换使排列奇偶性发生改变 情形2一般情形 设排列为 检查对换a与b 一次相邻对换改变排列奇偶性 于是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和它的逆置换有相同的奇偶性 得