在排列组合中，常讨论n个不同元素排序的种数，我们这里只研究由1，2，…，n这n个不同自然数排序的相关知识.

定义1.3　由数1，2，…，n组成的一个有序数组，称为一个n级排列（简称排列）.

例如，1234及2341都是4级排列.n级排列的一般形式可记为p1p2…pn，其中pi（i=1，2，…，n）为1，2，…，n中的某个自然数，且p1，p2，…，pn互不相同.由排列组合的知识可知，n级排列的总数为n！.在所有的n级排列中，排列12…n是唯一从左向右看元素按从小到大顺序形成的排列，称其为标准排列；其余的n级排列都会有较大的元素在左，而较小的元素在右的现象.

定义1.4　在一个n级排列p1p2…pn中，如果较大的元素ps排在较小的元素pt的左侧，则称ps和pt构成一个逆序.一个n级排列中逆序的总数，称为这个排列的逆序数，记为τ（p1p2…pn）或N（p1p2…pn）.

例如，在排列23154中，共有2和1，3和1，5和4三个逆序，因此排列23154的逆序数为3，即τ（23154）=3.

对于一个n级排列p1p2…pn，可以用以下两种方法计算它的逆序数：

方法一：将pt（t=1，2，…，n）左侧比pt大的元素的个数称为pt的逆序数，并记作τt，则该排列的逆序数为

τ(p1p2…pt…pn)=τ1+τ2+…+τt+…+τn.　(1.9)

方法二：观察排在1左侧元素的个数，设为m1（1的逆序数），然后把1划去，再观察2左侧元素的个数（划去的元素不再计算在内），设为m2（2的逆序数），再把2划去，如此继续下去，最后设在n左侧有mn个元素（实为0），则该排列的逆序数为

τ(p1p2…pt…pn)=m1+m2+…+mt+…+mn.　(1.10)

[例1.4]　求下列各排列的逆序数.

(1)53412　(2)35412　(3)123…(n-1)n

(4)n(n-1)…21　(5)13…(2n-1)24…(2n)

解　（1）由式（1.9），τ（53412）=0+1+1+3+3=8.

（2）由式（1.10），τ（35412）=3+3+0+1+0=7.

（3）由式（1.10），τ（123…（n-1）n）=0+0+…+0=0.

（4）由式（1.10），τ（n（n-1）…21）=（n-1）+（n-2）+…+1+0=.

（5）由式（1.9），

定义1.5　逆序数为奇数的排列称为奇排列，逆序数为偶数的排列称为偶排列.(www.daowen.com)

定义1.6　在一个n级排列p1…ps…pt…pn中，如果仅将它的两个元素ps与pt对调，其余元素保持不变，得到另一个排列p1…pt…ps…pn，这种做出新排列的过程叫做对换，记为对换（ps，pt）.特别地，将相邻两个元素对调，叫做相邻对换.

在例1.4中，可以看到标准排列是一个偶排列，并且注意到偶排列53412经过对换（3，5）后，得到的排列35412是一个奇排列.事实上，我们有以下结论.

定理1.1　任一排列经过一次对换后必改变其奇偶性.

证*　（1）首先讨论相邻对换的特殊情况，设原排列为

…ij…,

则经过对换（i，j）后，变为新排列

…ji….

由于仅改变了i和j的次序，其余元素的位置并没有改变，因此新排列的逆序数比原排列的逆序数增加1（当i＜j时），或减少1（当i＞j时）.无论哪种情况，经过一次相邻对换之后排列的奇偶性发生改变.

（2）下面讨论一般情况，设原排列为

…ip1p2…psj…,　(1.11)

则先经过s次相邻对换，将排列（1.11）变为

…p1p2…psij…,　(1.12)

然后，再经过s+1次相邻对换，将排列（1.12）变为

…jp1p2…psi….　(1.13)

由上面的对换过程可以知道，对排列式（1.11）施以对换（i，j）得到排列式（1.13）的过程，可以分解为施以2s+1次相邻对换实现.而每施行一次相邻对换都改变排列的奇偶性，故排列式（1.11）与排列式（1.13）的奇偶性不同.可见，任一排列经过一次对换后必改变其奇偶性.

下面研究在一个n级排列中，偶排列和奇排列各占多少.

定理1.2　当n＞1时，n级排列中，奇排列和偶排列各占一半，均有个.

证　n级排列的总数共有n！个，设其中偶排列有p个，奇排列有q个，则p+q=n！.如果对这p个偶排列施以同一个对换[例如对换（1，2）]，则由定理1.1知p个偶排列全部变为不同的奇排列，且都包含在那q个奇排列中，因此p≤q.同理，可得q≤p.所以