线性代数第一章行列式第二节全排列及其逆序数.ppt

第二节 全排列及其逆序数 全排列 逆序数 引例 主要内容 一、引例 引例 用1，2，3三个数字可以组成多少个没 有重复数字的三位数？ 在数学中，把考察的对象，例如引例中的数字 1，2，3叫做元素. 上述问题就是：把三个不同的 元素排成一列，共有几种不同的排法？ 二、全排列 对于 n 个不同的元素，也可以提出类似的问 题： 把 n 个不同的元素排成一列，共有几种不同 的排法？ 为此先给出全排列的定义. 定义 把 n 个不同的元素排成一列，叫做这 n 个元素的全排列（也简称排列）. n 个不同元素的所有排列的种数，通常用 Pn 表 示. 由 的结果可知 P3 = 3 · 2 · 1 = 6. 为了得出计算 Pn 的公式，可以仿照 进行讨论： 从 n 个元素中任取一个放在第一个位置上， 有 n 种取法； 从剩下的 n – 1 个元素中任取一个放在第二 个位置上，有 n – 1 种取法； 这样继续下去，直到最后只剩下一个元素放 在第 n 个位置上，只有 1 种取法. 于是 Pn = n ? (n – 1) ? ··· ? 3 ? 2 ? 1 = n! . 三、排列的逆序数 定义 对于 n 个不同的元素，先规定各元素 之间有一个标准次序（例如 n 个不同的自然数，可 规定由小到大为标准次序）， 于是在这 n 个元素的 任一排列中，当某两个元素的先后次序与标准次 序不同时，就说有 1 个逆序. 一个排列中所有逆 序的总数叫做这个排列的逆序数. 1. 定义 逆序数为奇数的排列叫做奇排列,逆序数为偶 在一个 n 阶排列中,任何一个数对不是构成 逆序就是构成顺序. 如果我们把顺序的个数称为顺 序数, 则一个 n 阶排列的顺序数与逆序数的和为 n(n -1)/2. 数的排列叫做偶排列. 下面来讨论计算排列的逆序数的方法. 2. 计算方法 不失一般性，不妨设 n 个元素为 1 至 n 这 n 个 自然数， 并规定由小到大为标准次序. 设 为这 n 个自然数的一个排列， 考虑元素 pi （i = 1, 2, … , n）， 如果比 pi 大的且排在 pi 前面的元素有 ti 个，就说 pi 这个元素的逆序数是 ti . 全体元素的 逆序数之和