§1.2排列.ppt

* * 一、排 列 二、反序 反序数 三、奇排列 偶排列 四、对换 一、排列 定义 称为一个 元排列． 由1，2，…，n 组成的一个有序数组 123，132，213，231，312，321．　 如，所有的3元排列是 　——共6=3！个. (　的阶乘) 注： 1)所有不同　元排列的总数是 2)123···n称为自然排列 二、反序　反序数 我们规定各元素之间有一个标准次序, n 个不同的自然数，规定由小到大为自然顺序. 定义 一个排列中反序的总数称为这个排列的反序数(逆序数)． 在一个排列中，如果一对数的前后位置 与标准次序相反，即前面的数大于后面的数， 则称这对数为一个反序(逆序)； ① 排列 123　　 称为自然排列，其逆序数为０． 注： ② 排列 的逆序数常记为 ③　　　　　　　后面比 小的数的个数 后面比 小的数的个数. 后面比 小的数的个数 或　　　　　　　前面比 大的数的个数 前面比 大的数的个数 前面比 大的数的个数． 方法一 方法二 例1．排列 31542 中，逆序有 31， 32， 54， 52， 42 的逆序数. 例2．求 元排列 解： 方法一 逆序数为奇数的排列称为奇排列； 逆序数为偶数的排列称为偶排列． 三 、奇排列、偶排列 定义 标准排列 123　　 为偶排列． 注： 练习：求下列排列的逆序数并讨论其奇偶性． （1） （2） 答案: （2） 当 时为偶排列； 当 时为奇排列. 当 为偶数时为偶排列， 当 为奇数时为奇排列. 方法一 方法二 四 、对换 1.定义 把一个排列中某两个数的位置互换，而 其余的数不动，得到另一个排列，这一变换 称为一个对换． 将相邻两个元素对调，叫做相邻对换． 过一系列对换由 得到 设 ， 是任意两个排列,那么总可通 2.定理1 证明: 对n进行数学归纳 ⑴1元排列只有一个，命题显然成立 ⑵假定n－1时结论成立，现证n时结论仍然成立 设i1i2···in是n元排列，若in=n,据归纳假定，n－1元 排列经一系列对换可变成12···(n－1),这一系列对换 已把i1i2···in变成为12···n；若i n≠n,对作对换 (in,n),将其变成i1/i2/···in-1/n， 据归纳假定可知结论成立. 12···n也可用一系列对换变成j1j2···jn，因此， j1j2···jn也可用一系列对换变成12···n ，由可逆性， 经过一系列对换得到 一系列对换互换，并且所作对换的次数与这个 任意一个排列与标准排列 都可经过 排列的奇偶性相同． 推论 由定理1知对换的次数就是排列奇偶性的 变化次数, 因此知结论成立. 证明 而标准排列是偶排列（逆序数为0）,