1.2 全排列和对换
排列与逆序数
全排列
把 个元素按照某种顺序不重不漏地排成一列，称作这 个元素的全排列，也称 元排列。各种各样的顺序放在一起，所有 元排列构成的集合记为 ， 所含的元素个数即为 元排列的个数，记为 。
也就是说
逆序
在某个 元排列中，如果存在一个大数排在一个小数前面，就称这一对数构成一个逆序。
比如，在 6 元排列 中，、 和 各是一个逆序。
一个排列中，逆序的总数称为逆序数，上述排列的逆序数记作 。再比如，有 。
逆序数为奇数的排列，称作奇排列；逆序数为偶数的排列，称为偶排列。我们在意的不是逆序数本身，而是逆序数的奇偶。
例
对换
定理：排列中对换两数的位置，排列的奇偶性改变。
先考虑最简单的，相邻两个数的对换。
所有这些逆序： 该在还是在，本来没有的也不会多出来 —— 因为他们的相对前后位置不会改变。所以我们只需要考虑 的大小。剩下的事就很简单了：
也就是说相邻两个数对换，排列的奇偶性会改变。
下面考虑更一般的情况：
我们将其视为多次相邻对换：
也就是总共挪了 次。显然， 次加一或减一，最后逆序数必然会改变奇偶。
推论：对于任意的 ，其中的奇排列和偶排列的数量必然相等。
因为把其中所有的排列的前两个数对换，奇排列都变成了偶排列，偶排列都变成了奇排列，而且所有的排列依然不重不漏。显然二者的数量相同。