基本介绍

利用逆序来描述排列的方法是M.Hall,Jr发现的。逆序的概念是一个旧概念，它在矩阵的行列式理论中起着重要作用。令是集合的一个排列。如果而，称为一个逆序。于是，逆序对应一对数，它们在排列中失去自然次序。例如，排列31524中有4 个逆序，即的唯一没有逆序的排列是。对于排列，我们令表示第二个分量为的逆序个数。换句话说，等于排列中先于且又大于的那些整数的个数。它度量的失序有多少。数列称为排列的逆序数列。上例给出的数列的逆序数列是。

排列的逆序数列必须满足条件

这是显然的，因为对每一个，在集合中都有个整数大于k。利用乘法原理，可知满足的整数的个数等于。这些数列中每一个都唯一地对应的一个排列2。

定理构造方法

定理1设是整数数列且，则存在的唯一排列，其逆序数列是。

证明：我们介绍一种方法，可用来唯一地构造其逆序数列为的一个数列。

：写 出。

：考察:。已知，如果,，则必在n的前面。如果，则必在n的后面。

考察。已知。如果，则必在由步得到的两个数之前，如果，，则必在由步得到的两个数之间。如果,，则必在由步得到的两个数之后。

(一般步)考察。已知，在由n到的各步中，k个数已按要求的次序放好。如果，则必在由步得到的所有数之前。如果，则必在头两个数之间。...如果，则必在所有数之后。

...

1：...

作完诸步之后，就唯一确定了的排列，其逆序数列是。

习惯上，根据的排列的逆序个数是偶数还是奇数，称它为偶排列或奇排列。排列的符号则根据它是否为偶或奇定义为+1或-1。在矩阵的行列式理论中，排列符号的概念是重要的，这里阶矩阵的行列式定义为。这里求和是指对的所有排列求和，为的符号。

若排列具有逆序个数为的逆序数列则可以相继经过k次交换相邻两数得到。我们首先把1逐次与个在它左边的数进行交换。然后把2逐次与个在它左边的大于2的数交换，等等。用这种方法经次交换后，我们得到。

例题解析

试确定的排列，使其逆序数列为，对于给定的逆序数列，按照定理证明中的步骤，得到下面的结果：