排列及其逆序数.ppt

一个排列的逆序总数称为这个排列的逆序数。 对换与排列的奇偶性的关系 铁岭师范高等专科学校 理工学院 数学教研室 * 线性 代数 行列式 矩 阵 向量 空间 特征值 与特征 向量 二 次 型 排列及其逆序数 n阶行列式的定义 行列式的性质 行列式按行（列）展开 克莱姆法则 第一章 行列式 排列 逆序和逆序数 奇排列和偶排列 逆序数的计算方法 对换 第一节 排列及其逆序数 概念的引入 引例 用1、2、3三个数字，可以组成多少个没有重复数字的三位数？ 解 1 2 3 1 2 3 百位 3种放法 十位 1 2 3 1 个位 1 2 3 2种放法 1种放法 种放法. 共有 一、排 列 一般地： 把n个不同元素排成一列有几种不同排法？ 分析： 从n个元素中取定一个放在第一个位置上有n 种放法； 又从剩下的n-1个元素中任取一个放 在第二个位置上有n-1种放法； 如此下去，直到最后一个元素放在第n个位置上 只有1种放法。 把n个不同元素排成一列称为这n个元素 的全排列。(简称排列） 用Pn表示所有排列的种数。 定义1 称在 n! 种排列中从小到大次序的那个排为自然排列 （或标准排列）. 注意： 不失一般性，我们将 n 个元素看成 n 个自然数， 在一个排列中,如果一个大的数排在小的 数之前,就称这两个数构成一个逆序。 例如 排列312有2个逆序，即31；32 二、逆序和逆序数 定义2 逆序数为奇数的排列称为奇排列, 逆序数为偶数的排列称为偶排列。 三、奇排列和偶排列 定义3 例如 ： 排列312的逆序数为2，故它是偶排列。 而 排列132的逆序数为1，故它为奇排列。 方法1 分别计算出排在 前面比它大的数 码之和即分别算出 这 个元素 的逆序数，这些元素的逆序数的总和即为所求 排列的逆序数. 例如 排列32514 中， 3 2 5 1 4 逆序数为3 1 故此排列的逆序数为3+1+0+1+0=5. 四、逆序数的计算方法 分别计算出排列中每个元素前面比它大的数码个数之和，即算出排列中每个元素的逆序数，这每个元素的逆序数之总和即为所求排列的逆序数. 方法2 例如 求排列32514的逆序数. 解 在排列32514中, 3排在首位,逆序数为0; 2的前面比2大的数只有一个3,故逆序数为1; 5的前面没有比5大的数,其逆序数为0; 1的前面比1大的数有3个,故逆序数为3; 4的前面比4大的数有1个,故逆序数为1; 3 2 5 1 4 于是排列32514的逆序数为 例1 计算下列排列的逆序数，并讨论它们的奇偶性. 解 此排列为偶排列. 解 当 时为偶排列； 当 时为奇排列. 在排列中，将任意两个元素对调，其余元素不动，这种作出新排列的手续叫做对换． 将相邻两个元素对调，叫做相邻对换． 例如 五、对 换 定义4 定理1　一个排列中的任意两个元素对换，排列改变 奇偶性． 证明 设排列为 对换 与 除 外，其它元素的逆序数不改变. （1）先证相邻对换情形．