逆序数

逆序数是刻画全排列"乱序程度"的量：在一个排列 $\sigma_1\sigma_2\cdots\sigma_n$ 中，若下标 $i<j$ 而 $\sigma_i>\sigma_j$，则称 $(\sigma_i,\sigma_j)$ 构成一对逆序，逆序总数即为该排列的逆序数。它等于把排列经相邻对换化为顺序排列所需的交换次数，也决定行列式展开项 $(-1)^t$ 的符号。

$$\text{逆序数} = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} [\sigma_i > \sigma_j]$$

符号 $[\cdot]$ 为 Iverson 括号：条件成立取 $1$，否则取 $0$。