全排列与逆序数

马同学

下面就来介绍阶行列式的定义，它的定义相当复杂，可以想象是数学家们（比如凯莱、范德蒙、克拉默等）废了无数草稿纸，反复验算各阶线性方程组，从中总结出来的。

为了介绍行列式的定义，先引入两个概念。

1 全排列

把个不同的元素排成一列，叫做这个元素的全排列。

比如有、、这三个数字，总共有以下六种不重复的排列方式：

这六种排列方式统称为全排列。

2 逆序数

2.1 定义

在一个排列（也就是数列）中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为该排列的逆序数。逆序数为奇数的排列称为奇排列，逆序数为偶数的排列称为偶排列。

比如有这么一个排列：

为了计算它的逆序数，先单独算出每个数字的。比如该排列的第三个数字5之前，没有一个数字大于它，也就是没有一个逆序的，那么记作（因为它是第三个数字）：

再比如，第四个4之前，有一个逆序的，记作：

数列内每个数字都可以求出对应的：

然后将所有数字的加起来就得到了整个数列的逆序数：

因为算出来逆序数为6，所以这是偶排列。

2.2 交换

一个排列中任意的两个元素对换，排列改变奇偶性。

不妨假设元素为从1开始的自然数（从小到大为标准次序）。

先证相邻对换的情形。

设排列：

很显然，这些元素的逆序数不会改变：

而的逆序数有两种情况：

总之，对换前后，奇偶性改变。

再证一般对换的情形。

设排列为：

首先：

再：

总共次相邻对换，所以奇偶性改变。

比如排列：

和之前比，5和2对换了，各个数字的为：

所以变成了奇排列：

关注马同学

微信公众号：matongxue314

马同学机器学习

马同学图解数学

关注马同学

微信公众号：matongxue314