逆序数

贡献者： addis

　　¹我们把集合 $ \left\{1,\dots,N \right\} $ 的某种排列记为 $\pi$，该排列的元素按照顺序分别记为 $\pi_1, \dots, \pi_N$。对于任意 $i < j$，如果满足 $\pi_i > \pi_j$ 我们就把 $i, j$ 或者 $\pi_i, \pi_j$ 称为排列 $\pi$ 的一个逆序对（inversion）。一个排列中所有逆序对的个数就叫逆序数（inversion number）。

　　 逆序数主要的应用有定义行列式和列维—奇维塔（Levi-Civita）符号。在这两个应用中，我们只对逆序数的奇偶性感兴趣。我们把逆序数为奇数的排列叫做奇排列，逆序数为偶数的排列叫做偶排列。把按从小到大的顺序排列叫做标准排列。标准排列逆序数为零，是一个偶排列。

　　 一般情况下，要计算逆序数，我们可以依次令 $i = 1, \dots, N$，对每个 $i$，将其右边所有小于 $\pi_i$ 的元素数求和即可。

证明

　　 在排列 $p_n$ 中，考虑第 $i, j$（$i < j$）两个元素的置换，不妨把他们的值分别记为 $m, n$。不妨假设 $m < n$（$n < m$ 的讨论同理）。为了方便讨论，我们把任意两个不同元素都用弧线连起来，这些弧线有的代表逆序对，有的不是。我们可以把这些连线分为 4 类来讨论：

1. 对于不连接到 $m$ 或 $n$ 的线，置换不改变它们之中的逆序数。
2. 对于从 $m$ 或 $n$ 连接到 $m$ 左边或 $n$ 右边的线，置换同样不改变他们之中的逆序数。
3. 若 $m,n$ 不相邻，对于从 $m$ 或 $n$ 连接到 $m, n$ 之间某个元素 $q$ 的两条线，只有当 $m < q < n$ 时逆序数会改变：从两个非逆序对变为逆序对。但无论有多少满足条件的 $q$，逆序数只会增加偶数个。
4. $m,n$ 在置换前不是逆序对，置换后变为逆序对，使逆序数增加 1，改变逆序数的奇偶性。

　　 综上所述，逆序对在置换后必定改变奇数个，所以逆序数奇偶性发生变化。证毕。

　　 证明显然。

1. ^ 参考 Wikipedia 相关页面。