奇排列

逆序数为奇数的排列

逆序数为奇数的排列称为奇排列。经过一次对换，奇排列变成偶排列，偶排列变成奇排列。在全部n级排列中，奇、偶排列的个数相等，各有（n！/2 ）个。任意一个n级排列与排列 12...n 都可以经过一系列对换互变，并且所作对换的个数与这个排列有相同的奇偶性。

定义

n级排列

定义1 由1，2，...，n组成的一个有序数组称为一个n级排列。

例如，2431是一个四级排列，45321是一个五级排列。

注：n级排列的总数是

显然，也是一个n级排列，这个排列具有自然顺序，就是按递增的顺序排起来的；其它的排列都或多或少地破坏自然顺序。

逆序数

定义2 在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序，一个排列中逆序的总数就称为这个排列的逆序数。

例如2431中，21,43，41,31是逆序，2431的逆序数就是4；而45321的逆序数是9.

注：排列的逆序数记为

奇排列

定义3 逆序数为奇数的排列称为奇排列。（相应地，逆序数为偶数的排列称为偶排列。）

例如，2431是偶排列，45321是奇排列，的逆序数是零，因而是偶排列。

注：1）考虑由任意n个不同的自然数所组成的排列，一般地也称为n级排列。对这样一般的n级排列，同样可以定义上面这些概念。

2）对换：把一个排列中某两个数的位置互换，而其余的数不动，就得到另一个排列。这样一个变换称为一个对换。

性质

定理1 对换改变排列的奇偶性。（经过一次对换，奇排列变成偶排列，偶排列变成奇排列。）

证明：先看一个特殊的情形，即对换的两个数在排列中是相邻的情形。排列（1）

经过 j，k对换变成排列（2）

这里“ ”表示那些不动的数。显然，在排列（1）中如 j，k 与其他的数构成逆序，则在排列（2）中仍然构成逆序；如不构成逆序则在（2）中也不构成逆序；不同的只是 j，k 的次序。如果原来j，k 组成逆序，那么经过对换，逆序数就减少一个；如果原来 j，k不组成逆序，那么经过对换，逆序数就增加一个。不论增加1还是减少1，排列的逆序数的奇偶性总是变了。因此，在这个特殊的情形，定理是对的。

再看一般的情形。设排列为（记为（3））

经过 j，k 对换，排列（3）变成排列（记为（4））

不难看出，这样一个对换可以通过一系列的相邻数的对换来实现。从（3）出发，把k 与 is对换，再与is-1 对换，也就是说，把k 一位一位的向左移动。经过s+1次相邻位置的对换，排列（3）就变成排列（记为（5））

从（5）出发，再把j 一位一位地向右移动，经过s次相邻位置的对换，排列（5）就变成了排列（4）。因此，j，k 对换可以通过2s+1次相邻位置的对换来实现。2s+1是奇数，相邻位置的对换改变排列的奇偶性。显然，奇数次这样的对换的最终结果还是改变奇偶性。

定理2 在全部n级排列中，奇、偶排列的个数相等，各有个。

证明：假设在全部n级排列中共有s个奇排列，t个偶排列。将s个奇排列中的前两个数字对换，得到s个不同的偶排列。因此s≤t. 同样可证t≤s，于是s=t，即奇、偶排列的总数相等，各有个。

注：定理2保证了n阶行列式的展开式的n! 项中正负项各半。

定理3 任意一个n级排列与排列都可以经过一系列对换互变，并且所作对换的个数与这个排列有相同的奇偶性。

证明：我们对排列的级数n作数学归纳法，来证任意一个n级排列都可以经过一系列对换变成 .

1级排列只有一个，结论显然成立。

假设结论对n-1级排列已经成立，证对n级排列的情形结论也成立。

设是一个n级排列，如果，那么根据归纳法假设，n-1级排列可以经过一系列变换变成，于是这一系列对换也就把变成 . 如果，那么对作jn，n对换，它就变成，这就归结成上面的情形，因此结论普遍成立。