定义1　由1，2，…，n组成一个有序数组称为一个n级排列（也叫作这n个元素的一个全排列，简称排列）.

例如：1234是一个4级排列，3412也是一个4级排列，而52341是一个5级排列.由1，2，3组成的所有3级排列为：123，132，213，231，312，321，共有3！=6个.

n级排列一共有n！个.而在n级排列中，1234…n 这个排列具有自然顺序，称为一个自然排列或标准排列.

定义2　在一个n级排列p1p2…pn中，如果有较大的数 pt排在较小的数ps的前面（ps＜pt），则称pt与ps构成一个逆序，一个n级排列中逆序的总数，称为这个排列的逆序数，记成τ(p1p2…pn).

例如，在4级排列3412中，31，32，41，42各构成一个逆序，所以，排列3412的逆序数τ（3412）=4.同样可计算排列52341的逆序数为τ（52341）=7.

下面讨论计算逆序数的方法，为了讨论方便，不妨设一个n级排列p1p2…pn中，考虑元素pi(i=1,2，…，n)，如果比pi大的且排在pi前面的元素有ti个，就说pi这个元素的逆序数是ti（个）.全体元素的逆序个数之总和：τ(p1p2…pn)=t1+t2+…+tn，即为这个排列的逆序数.

例1　求排列52431的逆序数.

解：在排列52431中：

5排在首位，前面没有其他的数，逆序数为0；

2的前面有一个数（5）比2大，故逆序数为1；

4的前面有一个数（5）比4大，故逆序数为1；

3的前面有两个数（5，4）比3大，故逆序数为2；(www.daowen.com)

1的前面有四个数（5，2，4，3）比1大，故逆序数为4；

于是这个排列的逆序数为 τ（52431）=0+1+1+2+4=8.

容易看出，自然排列的逆序数为0.

定义3　若排列p1p2…pn的逆序数 τ（p1p2…pn）是奇数，则称此排列为奇排列；逆序数是偶数的排列，称为偶排列.

例如：排列3412是偶排列；排列52341是奇排列；自然排列123…n是偶排列.

定义4　把一个排列中的某两个元素位置对调，而其他元素不动，就得到了另一个排列，这种变换称为一个对换.

例如：排列52341 中的3与4对换，就得到新排列52431.

定理1　任何一个排列经过一次对换，排列改变奇偶性.即奇排列经过一次对换变成偶排列，偶排列经过一次对换变成奇排列.

例如：排列 52341 为奇排列（逆序数为7），将其中的3与4对换，得到的新排列52431为偶排列（逆序数为8）.

定理2　全部n级排列中，偶排列与奇排列各占一半，都是个.

证明：如果全部n 级排列中奇排列有p个，偶排列有q个，所有的排列都经过一次同样的对换（即对换相同的两个数），则奇排列变成了偶排列（即 q ≥p），偶排列变成了奇排列（即p ≥q），所以.