逆序与逆序数¶

本页面给出本节最重要的一个量：排列的逆序数 $\tau(i_1 i_2 \cdots i_n)$。它衡量一个排列"颠倒"到什么程度，也是 $n$ 阶行列式中每一项正负号的唯一来源。

页面的重点是两种科学的计数方法（从数字角度、从位置角度）以及它们为什么不重不漏——后者用到的正是导论里的划分。

前置知识

$n$ 阶排列：$j_1 j_2 \cdots j_n$ 的定义，特别地自然排列与反序排列
组合数 $\binom{n}{2} = \dfrac{n(n-1)}{2}$：从 $n$ 个东西里任取两个的种数
划分：把一个集合分成若干两两不交的非空子集，且并起来是全集

引入：符号从哪里来¶

先看二阶行列式

\[ \begin{vmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{vmatrix} = a_{11} a_{22} - a_{12} a_{21} : \]

它的两项符号一正一负；三阶行列式的六项则是三正三负。为什么是这些项取正、那些项取负？

对二阶、三阶，可以用"主对角线减反对角线"来解释。但这个解释到了四阶就失效了（见 1.3），必须换一种只依赖"每项取了哪些位置"的说法。这种说法就是：看这一项的列指标排成的排列有多"颠倒"。于是先要把"颠倒程度"变成一个数。

逆序¶

定义（逆序）

设 $i_1 i_2 \cdots i_n$ 是一个 $n$ 阶排列。若存在一对下标 $p, q$ 满足

\[ 1 \le p < q \le n, \qquad i_p > i_q, \]

则称这一对数 $i_p, i_q$ 构成一个逆序，也说 $(i_p, i_q)$ 是一个逆序。

用一句话说：前面的数比后面的数大，就是一个逆序。

这个定义要注意三点：

与"相邻"无关。 $i_p$ 与 $i_q$ 在排列里可以隔得很远。例如排列 $312$ 中，$3$ 与 $1$ 位置相邻也是逆序，$3$ 与 $2$ 隔着 $1$ 也是逆序。
逆序的对象是"一对数"。 说"$3$ 是逆序"没有意义，要说是"$3$ 与 $2$ 构成一个逆序"。
取值的来源是"下标的大小"。 判断标准是"位置在前的那一个数值是否更大"，与数值本身是什么无关。

命题（候选对的总数）

在 $n$ 阶排列 $i_1 i_2 \cdots i_n$ 中，形如 $(i_p, i_q)$（$p < q$）的数对共有

\[ \binom{n}{2} = \frac{n(n-1)}{2} \]

对。

证明

每一对 $(p, q)$（$1 \le p < q \le n$）对应一对数 $(i_p, i_q)$，不同的下标对给出不同的数对（因为排列中每个数只出现一次）。所以只需数下标对：从 $1, 2, \dots, n$ 中任取两个不同的数，小的作 $p$、大的作 $q$，共 $\binom{n}{2}$ 对。

这个数字后面要用来估计逆序数的最大值。

逆序数¶

定义（逆序数）

排列 $i_1 i_2 \cdots i_n$ 中逆序的总数称为该排列的逆序数，记作

\[ \tau(i_1 i_2 \cdots i_n). \]

这里 $\tau$ 是希腊字母 tau，读作"套"。

按定义，$\tau$ 就是"满足 $p < q$ 且 $i_p > i_q$ 的下标对 $(p,q)$ 的个数"。由上面的命题立刻得到：

\[ 0 \le \tau(i_1 i_2 \cdots i_n) \le \binom{n}{2} = \frac{n(n-1)}{2}. \]

两个端点都能达到：

$\tau(1\,2\,\cdots\,n) = 0$，因为自然排列中每个数都比它后面的数小；
$\tau(n\,(n-1)\,\cdots\,2\,1) = \binom{n}{2}$，因为反序排列中任意两个数都构成逆序。

先感受一下量级

按定义"逐对检查"来计算代价很高：$n$ 阶排列要检查 $\binom{n}{2}$ 对，$n$ 越大增长越快（$n = 20$ 时已是 $190$ 对）。这不失为一种办法，但它是"最原始"的办法，排列稍微长一点就不实用。下面给出两种科学得多的算法。

一个例子：$\tau(2\,4\,6\,5\,7\,1\,3)$¶

先用最笨的办法把答案找到，再用聪明办法核对。

例题 1（按定义逐对检查）

求 $\tau(2\,4\,6\,5\,7\,1\,3)$。

解记排列为 $i_1 i_2 \cdots i_7 = 2\,4\,6\,5\,7\,1\,3$。对每个位置上的数，数出它后面比它小的数的个数：

位置 $p$	$1$	$2$	$3$	$4$	$5$	$6$	$7$
$i_p$	$2$	$4$	$6$	$5$	$7$	$1$	$3$
后面比它小的个数	$1$	$2$	$3$	$2$	$2$	$0$	$0$

合计得

\[ \tau = 1 + 2 + 3 + 2 + 2 + 0 + 0 = 10 . \]

逐个位置数的时候要保证"数全了"：位置 $1$ 上的 $2$ 后面有 $1$ 比它小；位置 $2$ 上的 $4$ 后面有 $1, 3$ 比它小；位置 $3$ 上的 $6$ 后面有 $5, 1, 3$ 比它小；等等。

下面的两种方法就是为了让"数全了"这件事不再靠眼睛。

两种科学的计数方法¶

关键思路：不要直接去数"逆序"这个笼统的东西，而是先把所有逆序按某个标准分成若干类，再逐类去数。 只要分类方式构成一个划分，就能保证不重不漏。

方法一：从数字角度¶

定义（$m_i$）

设 $i_1 i_2 \cdots i_n$ 是 $n$ 阶排列。对每个 $i = 1, 2, \dots, n$，规定

\[ m_i = \text{在数 } i \text{ 前面且比 } i \text{ 大的数的个数}. \]

也就是说，$m_i$ 数的是"以 $i$ 为后一个数"的逆序的个数。

注意 $m_i$ 是按数值 $i$ 来编号的（$m_1$ 到 $m_n$），与 $i$ 在排列中处在第几位无关。例如在上面的排列 $2\,4\,6\,5\,7\,1\,3$ 中：

$i$	$1$	$2$	$3$	$4$	$5$	$6$	$7$
$i$ 前面比 $i$ 大的数	$2,4,6,5,7$	无	$4,6,5,7$	无	$6$	无	无
$m_i$	$5$	$0$	$4$	$0$	$1$	$0$	$0$

命题（方法一）

对任意 $n$ 阶排列 $i_1 i_2 \cdots i_n$，

\[ \tau(i_1 i_2 \cdots i_n) = \sum_{i=1}^{n} m_i . \]

证明

把所有逆序的集合按"后一个数是谁"分类。 用 $R$ 记这个排列中一切逆序组成的集合，即

\[ R = \{\, (i_p, i_q) \mid p < q,\ i_p > i_q \,\}. \]

对每个 $i \in \{1, 2, \dots, n\}$，令

\[ R_i = \{\, (i_p, i_q) \in R \mid i_q = i \,\}, \]

即所有"后一个数是 $i$"的逆序。于是

不重：$i \ne j$ 时 $R_i \cap R_j = \varnothing$，因为一个数对的后一个数不可能同时是 $i$ 又是 $j$；
不漏：每个逆序 $(i_p, i_q)$ 都有后一个数 $i_q$，故它属于 $R_{i_q}$。

因此 $\{R_1, R_2, \dots, R_n\}$ 是 $R$ 的一个划分，从而

\[ \#R = \sum_{i=1}^{n} \#R_i . \]

再看 $\#R_i$：$R_i$ 中的数对形如 $(i_p, i)$，其中 $i_p$ 在 $i$ 前面且大于 $i$；反过来，任何"在 $i$ 前面且比 $i$ 大"的数 $i_p$ 都给出 $R_i$ 中的一个数对。所以 $\#R_i = m_i$。又 $\#R = \tau$，代回即得结论。

为什么这一步值得单独写一个证明

"把逆序按后一个数分类"这句话听起来是废话，但"不重不漏"必须验证，而验证用到的正是划分的定义。以后遇到"某个量等于若干部分之和"的命题，第一步几乎都是去找这样的划分。此处的划分属于导论中"等价关系与划分"的直接应用。

方法二：从位置角度¶

定义（$l_i$）

设 $i_1 i_2 \cdots i_n$ 是 $n$ 阶排列。对第 $i$ 个位置，规定

\[ l_i = \text{在第 } i \text{ 个位置后面且比 } j_i \text{ 小的数的个数}, \]

即 $l_i$ 数的是"以第 $i$ 个位置上的数为前一个数"的逆序的个数。

为避免下标重名，下面把第 $i$ 个位置上的数写成 $j_i$，于是

\[ l_i = \#\{\, q \mid i < q \le n,\ j_q < j_i \,\}. \]

命题（方法二）

对任意 $n$ 阶排列 $j_1 j_2 \cdots j_n$，

\[ \tau(j_1 j_2 \cdots j_n) = \sum_{i=1}^{n} l_i . \]

证明

这次把逆序集合 $R$ 按前一个数所在的位置分类：

\[ R^{(i)} = \{\, (j_p, j_q) \in R \mid p = i \,\}. \]

与前面同样的两条理由：不同的 $i$ 给出的 $R^{(i)}$ 两两不交（一个数对的前一个数只有一个位置），且每个逆序都落在某个 $R^{(i)}$ 中。故 $\{R^{(1)}, \dots, R^{(n)}\}$ 是 $R$ 的划分，

\[ \tau = \#R = \sum_{i=1}^{n} \#R^{(i)} = \sum_{i=1}^{n} l_i . \]

最后一步是因为 $R^{(i)}$ 恰由"第 $i$ 个位置上的数与其后比它小的数"配对而成，个数正是 $l_i$。

两种方法的关系¶

两种方法数的是同一批逆序，只是分类标准不同：方法一按"后一个数"归类，方法二按"前一个数的位置"归类。因此二者给出同一个和。

顺便得到两个恒等式（对任意排列都成立）：

\[ \sum_{i=1}^{n} m_i = \sum_{i=1}^{n} l_i = \tau . \]

左侧是一个排列 2 4 6 5 7 1 3，所有逆序按"后一个数"被分成 7 组，分别用颜色标出；右侧是同一批逆序按"前一个数的位置"被分成 7 组 — 图 1：两种计数方法都是"先把所有逆序划分成若干类，再逐类计数"。左：按后一个数分类，第 $i$ 类恰有 $m_i$ 个，故 $\tau = \sum m_i$；右：按前一个数的位置分类，第 $i$ 类恰有 $l_i$ 个，故 $\tau = \sum l_i$。两侧数的是同一批逆序。

回到例题¶

例题 2（用两种方法重算）

求 $\tau(2\,4\,6\,5\,7\,1\,3)$。

解（从数字角度） 依次看 $i = 1, 2, \dots, 7$：

\[ \tau = m_1 + m_2 + \cdots + m_7 = 5 + 0 + 4 + 0 + 1 + 0 + 0 = 10 . \]

解（从位置角度） 依次看第 $1$ 到第 $7$ 个位置，$l_i$ 即例题 1 表中"后面比它小的个数"：

\[ \tau = l_1 + l_2 + \cdots + l_7 = 1 + 2 + 3 + 2 + 2 + 0 + 0 = 10 . \]

两种方法结果一致，与按定义逐对检查的 $10$ 也一致。

例题 3

求 $\tau(1\,3\,5\,7\,2\,4\,6\,8)$。

解用方法一，依次看数值 $i = 1, \dots, 8$：

$i$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$
$i$ 前面比 $i$ 大的数	无	$3,5,7$	无	$5,7$	无	$7$	无	无
$m_i$	$0$	$3$	$0$	$2$	$0$	$1$	$0$	$0$

求和得

\[ \tau(1\,3\,5\,7\,2\,4\,6\,8) = 0 + 3 + 0 + 2 + 0 + 1 + 0 + 0 = 6 . \]

用方法二核对：各位置的 $l_i$ 依次为 $0, 1, 2, 3, 0, 0, 0, 0$，和为 $6$，一致。这是一个偶排列（见对换与奇偶排列）。

这种"奇偶交错、先奇后偶"的排列在练习里很常见，用方法一比逐对检查快得多。

最大逆序数¶

命题（最大逆序数）

对任意 $n$ 阶排列，

\[ \tau \le \binom{n}{2} = \frac{n(n-1)}{2}, \]

且等号成立当且仅当该排列是反序排列 $n\,(n-1)\,\cdots\,2\,1$。

证明

由前面的命题，$n$ 阶排列中形如 $(i_p, i_q)$（$p < q$）的数对总共只有 $\binom{n}{2}$ 对，而逆序必须是其中的某些对，故 $\tau \le \binom{n}{2}$。

若排列是反序排列，则 $p < q$ 时必有 $i_p > i_q$（越靠前越大），每对数对都是逆序，故 $\tau = \binom{n}{2}$。反之，若存在 $p < q$ 使 $i_p < i_q$，则这一对不是逆序，逆序总数就小于 $\binom{n}{2}$。

$\dfrac{n(n-1)}{2}$ 的奇偶性

最大逆序数的奇偶性只取决于 $n$ 除以 $4$ 的余数：设 $n = 4k + r$，则 $\dfrac{n(n-1)}{2}$ 的奇偶性如下表。

$n \bmod 4$	$0$	$1$	$2$	$3$
$\dfrac{n(n-1)}{2} \bmod 2$	$0$	$0$	$1$	$1$

也就是说，$n \equiv 0, 1 \pmod 4$ 时反序排列是偶排列，$n \equiv 2, 3 \pmod 4$ 时反序排列是奇排列。这个结论在"反序排列的奇偶性"这类题目里可以直接用，推导只需把 $n = 4k + r$ 代入计算。

易错点¶

三个常见的错

把"逆序"当成"相邻反序"。 逆序只看两个数的先后与大小，与它们之间隔了多少个数无关。例如 $3\,1\,2$ 中有 $2$ 个逆序：$(3,1)$ 与 $(3,2)$。
把 $m_i$ 当成"第 $i$ 个位置的数"。 $m_i$ 的下标是数值 $i$；$l_i$ 的下标是位置 $i$。两者下标含义完全不同，混用会导致整张表都错位。
忘了验算。 两种方法的答案必须相同；若不同，说明分类时数重了或数漏了。做题时至少用一种方法算出结果，再用另一种抽查一两个位置。

参见¶

排列：上一页，$n$ 阶排列的定义
对换与奇偶排列：下一页，用逆序数定义奇偶性
导论 · 关系与等价类：划分的定义与"不重不漏"的依据
1.3 $n$ 阶行列式：逆序数在行列式定义中的用处
首页：全站记号约定

位置 \(p\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)
\(i_p\)	\(2\)	\(4\)	\(6\)	\(5\)	\(7\)	\(1\)	\(3\)
后面比它小的个数	\(1\)	\(2\)	\(3\)	\(2\)	\(2\)	\(0\)	\(0\)

\(i\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)
\(i\) 前面比 \(i\) 大的数	\(2,4,6,5,7\)	无	\(4,6,5,7\)	无	\(6\)	无	无
\(m_i\)	\(5\)	\(0\)	\(4\)	\(0\)	\(1\)	\(0\)	\(0\)

\(i\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)	\(8\)
\(i\) 前面比 \(i\) 大的数	无	\(3,5,7\)	无	\(5,7\)	无	\(7\)	无	无
\(m_i\)	\(0\)	\(3\)	\(0\)	\(2\)	\(0\)	\(1\)	\(0\)	\(0\)