跳转至

习题（1.2 排列）

本页面收录课本 1.2 的习题与思考题、课堂例题以及依课堂内容自拟的补充练习。解答默认折叠——建议先自己写一遍，再展开对照。

关于题目来源

  • 课本习题（习题 1–4）与思考题（思考题 1）的题干按课本原文整理；
  • 课堂例题（例 1–3）来自本次课的板书与课件；
  • 补充练习（练习 1–6）是整理笔记时按同一考点自拟的，题面不是教材原题。

同一道题若有两种成色不同的做法，会并列写成方法一 / 方法二：方法一取最短的那条路，方法二一般保留课堂上讲的思路（步骤多一些，但示范了某个会反复用到的手法）。做题时的最低要求是：写出用的是哪种计数方法（从数字角度还是位置角度），并说明为什么这样分类不重不漏。

前置知识

课本习题

习题 1 · 求逆序数与奇偶性

试确定下列排列的逆序数及奇偶性。

  1. \(3\,1\,4\,2\,9\,6\,7\,5\,8\)；
  2. (思考方式与T3一致，略)
  3. \((2n)\,1\,(2n-1)\,2\,(2n-2)\,3\,\cdots\,(n+1)\,n\)。
解答（1）

排列 \(3\,1\,4\,2\,9\,6\,7\,5\,8\) 是 \(9\) 阶排列。按定义逐对检查要检验 \(\binom{9}{2} = 36\) 对，用计数方法只需 \(9\) 步。

方法一（从位置角度） 从左到右数每个位置后面比它小的数的个数 \(l_i\)：

位置 \(1\) \(2\) \(3\) \(4\) \(5\) \(6\) \(7\) \(8\) \(9\)
数字 \(3\) \(1\) \(4\) \(2\) \(9\) \(6\) \(7\) \(5\) \(8\)
\(l_i\) \(2\) \(0\) \(1\) \(0\) \(4\) \(1\) \(1\) \(0\) \(0\)
\[ \tau = 2 + 0 + 1 + 0 + 4 + 1 + 1 + 0 + 0 = 9 . \]

方法二（从数字角度） 数每个数前面比它大的数的个数 \(m_i\)。只有 \(6\) 个位置非零：

\(i\) \(1\) \(2\) \(5\) \(6\) \(7\) \(8\)
\(m_i\) \(1\) \(2\) \(3\) \(1\) \(1\) \(1\)

其余 \(m_3 = m_4 = m_9 = 0\)，故

\[ \tau = 1 + 2 + 3 + 1 + 1 + 1 = 9 . \]

两种方法都是 \(9\)，互为验算。\(\tau = 9\) 是奇数，故该排列是奇排列。

解答（3）

记排列为 \((2n)\,1\,(2n-1)\,2\,(2n-2)\,3\,\cdots\,(n+1)\,n\)：奇数位上是递减的大数 \(2n, 2n-1, \dots, n+1\)，偶数位上是递增的小数 \(1, 2, \dots, n\)。用统一写法，第 \(2t-1\) 位是 \(2n-t+1\)，第 \(2t\) 位是 \(t\)（\(t = 1, 2, \dots, n\)）。

方法一（从数字角度）

  • 对小数 \(i\)（\(1 \le i \le n\)）：\(i\) 在第 \(2i\) 位，它前面有 \(2n, 2n-1, \dots, 2n-i+1\) 共 \(i\) 个大数都比它大，故 \(m_i = i\)；
  • 对大数 \(v = n + t\)（\(1 \le t \le n\)）：\(v\) 在第 \(2t - 1\) 位，它前面的大数只有 \(2n, 2n-1, \dots, v+1\) 共 \(n - t\) 个，故 \(m_v = n - t\)。

于是

\[ \tau = \sum_{i=1}^{n} i + \sum_{t=1}^{n} (n-t) = \frac{n(n+1)}{2} + \frac{n(n-1)}{2} = n^2 . \]

方法二（从位置角度，更短） 大数没有"贡献"、小数一律贡献，可以分开看：

  • 第 \(2t\) 位的数是 \(t\)，它后面全是比它大的数，故 \(l_{2t} = 0\)；

  • 第 \(2t - 1\) 位的数是 \(2n-t+1\)，它后面比它小的数分两部分：小数 \(t, t+1, \dots, n\)（共 \(n-t+1\) 个）以及大数 \(2n-t, 2n-t-1, \dots, n+1\)（共 \(n-t\) 个），所以

    \[ l_{2t-1} = (n-t+1) + (n-t) = 2n - 2t + 1 . \]

于是

\[ \tau = \sum_{t=1}^{n} (2n-2t+1) = 2n^2 - n(n+1) + n = n^2 . \]

两种方法都得 \(\tau = n^2\)。

奇偶性：因为

\[ n^2 - n = n(n-1) \]

是偶数，所以 \(n^2\) 与 \(n\) 奇偶性相同。故

  • \(n\) 为奇数时 \(\tau = n^2\) 为奇数，该排列是奇排列；
  • \(n\) 为偶数时 \(\tau = n^2\) 为偶数，该排列是偶排列。

验算：\(n = 2\) 时排列为 \(4\,1\,3\,2\)，\(\tau = 4 = 2^2\)，是偶排列；\(n = 3\) 时排列为 \(6\,1\,5\,2\,4\,3\)，\(\tau = 9 = 3^2\)，是奇排列。

习题 2 · 求 \(i\) 和 \(j\)

求 \(i\) 和 \(j\)，使得

  1. \(2\,9\,4\,7\,i\,1\,5\,j\,8\) 是偶排列；
  2. \(4\,2\,8\,i\,5\,3\,j\,7\) 是奇排列。
先定出 \(\{i, j\}\)

排列中出现的数字必须是 \(1\) 到 \(n\) 各一次，所以 \(i, j\) 只能取"剩下的那两个数"：

  • (1) 是 \(9\) 个位置，数字取 \(1, \dots, 9\)；已知 \(2,9,4,7,1,5,8\)，故 \(\{i, j\} = \{3, 6\}\)，只有两种取法；
  • (2) 是 \(8\) 个位置，数字取 \(1, \dots, 8\)；已知 \(4,2,8,5,3,7\)，故 \(\{i, j\} = \{1, 6\}\)，也只有两种取法。

于是每道小题只需在两种情形里挑一个，问题变成"一次判断"。

解答（1）

方法一（把 \(i, j\) 插入后，分块数逆序）

把逆序按来源分成四块：已知数字内部的、\(i\) 与已知数字的、\(j\) 与已知数字的、以及 \(i\) 与 \(j\) 之间的。先算已知数字按原顺序排成的排列 \(2\,9\,4\,7\,1\,5\,8\)：

\[ \tau(2\,9\,4\,7\,1\,5\,8) = 1 + 5 + 1 + 2 = 9, \]

（从位置角度：每位后面比它小的个数依次为 \(1, 5, 1, 2, 0, 0, 0\)。）

情形 \(\{i, j\} = \{3, 6\}\)，即 \(i = 3\)、\(j = 6\)： 排列为 \(2\,9\,4\,7\,3\,1\,5\,6\,8\)。

  • \(i = 3\) 在第 \(5\) 位：前面比它大的有 \(9, 4, 7\)（\(3\) 个），后面比它小的有 \(1\)（\(1\) 个）；
  • \(j = 6\) 在第 \(8\) 位：前面比它大的有 \(9, 7\)（\(2\) 个），后面比它小的没有；
  • \(i\) 与 \(j\)：\(3 < 6\)，不构成逆序。

合计 \(9 + 3 + 1 + 2 + 0 + 0 = 15\)，是奇排列。

情形 \(i = 6\)、\(j = 3\)： 排列为 \(2\,9\,4\,7\,6\,1\,5\,3\,8\)。

  • \(i = 6\)：前面比它大的有 \(9, 7\)（\(2\) 个），后面比它小的有 \(1, 5, 3\)（\(3\) 个）；
  • \(j = 3\)：前面比它大的有 \(9, 4, 7, 5\)（\(4\) 个），后面比它小的没有；
  • \(i\) 与 \(j\)：\(6 > 3\) 且 \(6\) 在前，构成 \(1\) 个逆序。

合计 \(9 + 2 + 3 + 4 + 0 + 1 = 18\)，是偶排列。故

\[ i = 6, \qquad j = 3 . \]

（用数字角度核对：\(2\,9\,4\,7\,6\,1\,5\,3\,8\) 的非零 \(m_i\) 为 \(m_1 = 5\)、\(m_3 = 5\)、\(m_4 = 1\)、\(m_5 = 3\)、\(m_6 = 2\)、\(m_7 = 1\)、\(m_8 = 1\)，和也是 \(18\)。）

方法二（用"对换改变奇偶性"，只算一种情形）

两种情形只差"把 \(i\) 与 \(j\) 互换位置"，也就是对排列做一次对换。由对换改变奇偶性，这两个排列的奇偶性必然相反。所以：

  • 本题一定只有一个正确答案（不必怀疑两种情形都对或都不对）；
  • 只需完整算出一种情形，另一种由定理直接反推。

取 \(i = 3\)、\(j = 6\) 算出 \(\tau = 15\)（奇），则 \(i = 6\)、\(j = 3\) 必为偶排列，正是所求。一半的计算量省掉了——这就是"参数只有两种取法、且两种取法互为一次对换"时的通用技巧。

解答（2）

方法一（插入计数）

已知数字按原顺序为 \(4\,2\,8\,5\,3\,7\)，

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

情形 \(i = 1\)、\(j = 6\)： 排列为 \(4\,2\,8\,1\,5\,3\,6\,7\)。

  • \(i = 1\) 在第 \(4\) 位：前面比它大的有 \(4, 2, 8\)（\(3\) 个），后面比它小的没有；
  • \(j = 6\) 在第 \(7\) 位：前面比它大的有 \(8\)（\(1\) 个），后面比它小的没有；
  • \(i\) 与 \(j\)：\(1 < 6\)，不构成逆序。

合计 \(6 + 3 + 0 + 1 + 0 + 0 = 10\)，是偶排列。

情形 \(i = 6\)、\(j = 1\)： 排列为 \(4\,2\,8\,6\,5\,3\,1\,7\)。

  • \(i = 6\) 在第 \(4\) 位：前面比它大的有 \(8\)（\(1\) 个），后面比它小的有 \(5, 3\)（\(2\) 个）；
  • \(j = 1\) 在第 \(7\) 位：前面比它大的有 \(4, 2, 8, 5, 3\)（\(5\) 个），后面比它小的没有；
  • \(i\) 与 \(j\)：\(6 > 1\) 且 \(6\) 在前，构成 \(1\) 个逆序。

合计 \(6 + 1 + 2 + 5 + 0 + 1 = 15\)，是奇排列。故

\[ i = 6, \qquad j = 1 . \]

用数字角度核对 \(4\,2\,8\,6\,5\,3\,1\,7\)：非零 \(m_i\) 为 \(m_1 = 6\)、\(m_2 = 1\)、\(m_3 = 4\)、\(m_5 = 2\)、\(m_6 = 1\)、\(m_7 = 1\)，和为 \(15\)，一致。

方法二 与方法一相同：两种情形只差一次对换，奇偶性必相反。算出 \(i = 1\)、\(j = 6\) 是偶排列，即知 \(i = 6\)、\(j = 1\) 是奇排列。

插入计数的三个易错点

  1. 别忘了 \(i\) 与 \(j\) 之间的那一对。 它容易被漏掉：在情形 \(i = 6\)、\(j = 3\) 中它贡献 \(1\)，在 \(i = 1\)、\(j = 6\) 中它贡献 \(0\)。
  2. 数 \(j\) 的"前面比它大"时，不要把 \(i\) 也算进去，否则 \(i, j\) 之间那一对会被重复计数。换句话说，四块必须两两不交、并起来是全部逆序——这正是划分的要求。
  3. 先用"取值范围"把 \(\{i, j\}\) 定死。 忘记"\(n\) 阶排列必须把 \(1\) 到 \(n\) 各用一次"，就容易把 \(i, j\) 当成任意的数而算不出结果。

习题 3 · 倒序排列的逆序数

设排列 \(i_1 i_2 \cdots i_{n-1} i_n\) 的逆序数为 \(k\)。求排列 \(i_n i_{n-1} \cdots i_2 i_1\) 的逆序数。

解答

答案是

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

证明 任取一对下标 \(p < q\)，考察这两个位置上的数 \(i_p\) 与 \(i_q\)。

  • 在原排列 \(i_1 i_2 \cdots i_n\) 中，\(i_p\) 在前；
  • 在倒序排列 \(i_n \cdots i_2 i_1\) 中，\(i_q\) 在前。

两者位置关系完全颠倒。又 \(i_p \ne i_q\)，所以大小关系只有两种可能：

  • 若 \(i_p > i_q\)：原排列中 \((i_p, i_q)\) 是逆序，倒序排列中这一对不是逆序；
  • 若 \(i_p < i_q\)：原排列中不是逆序，倒序排列中是逆序。

可见每一对数对恰好在两个排列之一中贡献 \(1\) 个逆序：既不重复（每对数对只被看一次），也不遗漏（每对数对都会落进上面两种情形之一）。而这样的数对共有 \(\binom{n}{2}\) 个，故

\[ \tau(i_1 \cdots i_n) + \tau(i_n \cdots i_1) = \binom{n}{2}, \]

代入 \(\tau(i_1 \cdots i_n) = k\) 即得倒序排列的逆序数为 \(\binom{n}{2} - k\)。

验算 取 \(n = 4\)、排列 \(3\,1\,4\,2\)，它的 \(\tau = 3\)；倒序排列 \(2\,4\,1\,3\) 的 \(\tau\) 也是 \(3\)，而 \(\binom{4}{2} = 6\)，\(6 - 3 = 3\)，一致。

特例：自然排列 \(1\,2\,\cdots\,n\) 的 \(\tau = 0\)，它的倒序就是反序排列 \(n\,\cdots\,2\,1\)，逆序数为 \(\binom{n}{2} - 0 = \binom{n}{2}\)，与最大逆序数的结论吻合。

习题 4 · 两个逆序数之和的奇偶性

设 \(i_1 i_2 \cdots i_n\)，\(j_1 j_2 \cdots j_n\)，\(k_1, k_2, \dots, k_n\) 都是 \(n\) 阶排列。证明

\[ \tau(i_1 i_2 \cdots i_n) + \tau(j_1 j_2 \cdots j_n) \quad \text{与} \quad \tau(i_{k_1} i_{k_2} \cdots i_{k_n}) + \tau(j_{k_1} j_{k_2} \cdots j_{k_n}) \]

的奇偶性相同。

先把记号读准：\(i_{k_1} i_{k_2} \cdots i_{k_n}\) 是什么

下标的意思就是"取第几项"：\(i_{k_1} i_{k_2} \cdots i_{k_n}\) 表示把 \(i\) 的第 \(k_1\) 项、第 \(k_2\) 项、……、第 \(k_n\) 项依次取出、排成的新排列。

例如 \(n = 4\)，\(i = 3\,1\,4\,2\)，\(k = 3\,1\,4\,2\)。由 \(k_1 = 3\)、\(k_2 = 1\)、\(k_3 = 4\)、\(k_4 = 2\) 得

\[ i_{k_1} i_{k_2} i_{k_3} i_{k_4} = i_3\, i_1\, i_4\, i_2 = 4\,3\,2\,1 . \]

三点说明：

  • 因为 \(i\) 与 \(k\) 都是排列，取出的这 \(n\) 项仍然把 \(1\) 到 \(n\) 各取一次，所以 \(i_{k_1} \cdots i_{k_n}\) 也是一个 \(n\) 阶排列；
  • 它只是"把 \(i\) 的项换个顺序抄一遍"，没有产生任何新数字；
  • \(i_{k_t}\) 的下标是数值 \(k_t\)，不是位置 \(t\)。
解答（方法一：同一串对换同时把两条链送到终点）

关键观察：\(u \mapsto u_k\) 是同一个位置重排。

在 \(u_k = u_{k_1} u_{k_2} \cdots u_{k_n}\) 中，第 \(t\) 项是 \(u_{k_t}\)，也就是"第 \(t\) 位取 \(u\) 原来的第 \(k_t\) 位"。而自然排列 \(1\,2\,\cdots\,n\) 按同样的取法得到 \(k_1 k_2 \cdots k_n\)。所以

\[ u \mapsto u_k \quad\text{与}\quad 1\,2\,\cdots\,n \mapsto k_1 k_2 \cdots k_n \]

是同一个位置重排，与 \(u\) 的内容无关：序列里装的是什么，都不影响"哪些位置搬到哪里"。

于是同一串对换能同时走完两条链

由化为自然排列的命题，上面的位置重排可以用有限次对换实现。设需要 \(m\) 次（\(m\) 只依赖于 \(k\)，并且由该命题的第二条，\(m \equiv \tau(k_1 \cdots k_n) \pmod 2\)）。

既然这个重排与序列内容无关，把这同一串 \(m\) 次对换作用上去：

  • 作用在 \(i_1 i_2 \cdots i_n\) 上，得到 \(i_{k_1} i_{k_2} \cdots i_{k_n}\)；
  • 作用在 \(j_1 j_2 \cdots j_n\) 上，得到 \(j_{k_1} j_{k_2} \cdots j_{k_n}\)。

两条链是被同一串对换一起送过去的，翻转的次数自然都是 \(m\)。

写出奇偶性。 每做一次对换奇偶性翻转一次（对换改变奇偶性），所以

\[ \begin{aligned} \tau(i_{k_1} \cdots i_{k_n}) &\equiv \tau(i_1 \cdots i_n) + m \pmod 2, \\ \tau(j_{k_1} \cdots j_{k_n}) &\equiv \tau(j_1 \cdots j_n) + m \pmod 2 . \end{aligned} \]

（模 \(2\) 之下 \(+m\) 与 \(-m\) 是一回事，所以写成 \(\tau(i_1 \cdots i_n) \equiv \tau(i_{k_1} \cdots i_{k_n}) + m\) 也完全一样。）

两式相加。 左边是待比较的两个和，右边多出一个 \(2m\)：

\[ \tau(i_{k_1} \cdots i_{k_n}) + \tau(j_{k_1} \cdots j_{k_n}) \equiv \tau(i_1 \cdots i_n) + \tau(j_1 \cdots j_n) + 2m \pmod 2 . \]

而 \(2m\) 是偶数，可以直接丢掉，于是

\[ \tau(i_{k_1} \cdots i_{k_n}) + \tau(j_{k_1} \cdots j_{k_n}) \equiv \tau(i_1 \cdots i_n) + \tau(j_1 \cdots j_n) \pmod 2 , \]

这正是要证的结论。

为什么这条路最短

两件事凑在一起，结论就只剩一句话：

  1. \(i \mapsto i_k\) 与 \(j \mapsto j_k\) 是同一个位置重排（只由 \(k\) 决定，与序列内容无关），所以可以用同一串对换同时完成；
  2. "每做一次对换奇偶性翻转一次"只关心次数，不关心换了谁。

于是两条链翻转的次数相同（都是 \(m\)），两个和的变化量都是 \(2m\) 的倍数——模 \(2\) 之下当然相等。既不必分特殊情形与一般情形，也不必引入符号或双射。

用记号说明里的例子核对

取 \(n = 4\)、\(k = 3\,1\,4\,2\)、\(i = 3\,1\,4\,2\)、\(j = 1\,2\,3\,4\)。位置重排是"新第 \(1,2,3,4\) 位分别取旧第 \(3,1,4,2\) 位"，可用 \(3\) 次对换实现，故 \(m = 3\)（奇数）；对换序列取"换第 \(1,3\) 位 → 换第 \(2,3\) 位 → 换第 \(3,4\) 位"。

起点 经 \(m = 3\) 次对换后 逆序数变化
\(i\) \(3\,1\,4\,2\) \(4\,3\,2\,1\) \(3 \to 6\)
\(j\) \(1\,2\,3\,4\) \(3\,1\,4\,2\) \(0 \to 3\)

两条链的逆序数都翻转了奇偶性（\(3 \to 6\) 偶、\(0 \to 3\) 奇），所以两个和 \(3 + 0 = 3\) 与 \(6 + 3 = 9\) 奇偶性相同。这与结论一致。

解答（方法二：先证特殊情形，再沿一条"链"化归到一般情形（课堂讲法））

第一步：考虑特殊情形——\(i_1 i_2 \cdots i_n\) 与 \(j_1 j_2 \cdots j_n\) 都是自然排列。

此时 \(\tau(i_1 \cdots i_n) + \tau(j_1 \cdots j_n) = 0\)。又自然排列满足 \(i_m = m\)、\(j_m = m\)，逐项代值即得

\[ i_{k_1} i_{k_2} \cdots i_{k_n} = k_1 k_2 \cdots k_n, \qquad j_{k_1} j_{k_2} \cdots j_{k_n} = k_1 k_2 \cdots k_n, \]

于是

\[ \tau(i_{k_1} \cdots i_{k_n}) + \tau(j_{k_1} \cdots j_{k_n}) = 2\,\tau(k_1 k_2 \cdots k_n) \equiv 0 \pmod 2 . \]

所以特殊情形下原命题成立。

第二步：考虑一般情形

记 \(a_1 \cdots a_n\) 为自然排列（即 \(a_m = m\)），再记三个对换次数：

  • \(x\)：把 \(i_1 \cdots i_n\) 化为自然排列所需的对换次数；
  • \(y\)：把 \(j_1 \cdots j_n\) 化为自然排列所需的对换次数；
  • \(r\)：把自然排列化为 \(k_1 \cdots k_n\) 所需的对换次数。

由化为自然排列的命题，对换个数的奇偶性等于排列的奇偶性，所以

\[ x \equiv \tau(i_1 i_2 \cdots i_n) \pmod 2, \quad y \equiv \tau(j_1 j_2 \cdots j_n) \pmod 2, \quad r \equiv \tau(k_1 k_2 \cdots k_n) \pmod 2 . \]

逐步说明：

  1. 把 \(i\) 化为自然排列用 \(x\) 次对换，把 \(j\) 化为自然排列用 \(y\) 次对换，这就是 \(x, y\) 的定义。
  2. 从自然排列到 \(k_1 \cdots k_n\)。注意 \(a_{k_1} \cdots a_{k_n}\) 就是 \(k_1 \cdots k_n\)，且两条链的自然排列是相同的，所以两条链的第 2 步是同一个操作，次数都记作 \(r\)。
  3. 从 \(a_{k_1} \cdots a_{k_n}\) 到 \(i_{k_1} \cdots i_{k_n}\)，用的是第 1 步那一串对换，只是作用对象由 \(i\) 换成了 \(i_k\)；第 1、3 步用的既然是同一串对换，次数自然一致。

于是

\[ i_1 \cdots i_n \longrightarrow i_{k_1} \cdots i_{k_n} \quad \text{共经} \quad x + r + x = 2x + r \ \text{次对换}, \]
\[ j_1 \cdots j_n \longrightarrow j_{k_1} \cdots j_{k_n} \quad \text{共经} \quad y + r + y = 2y + r \ \text{次对换}. \]

每做一次对换奇偶性翻转一次，所以

\[ \tau(i_{k_1} \cdots i_{k_n}) \equiv \tau(i_1 \cdots i_n) + (2x + r) \equiv x + r \pmod 2, \]
\[ \tau(j_{k_1} \cdots j_{k_n}) \equiv \tau(j_1 \cdots j_n) + (2y + r) \equiv y + r \pmod 2 . \]

两式相加，右边的 \(2r\) 是偶数、可以丢掉：

\[ \tau(i_{k_1} \cdots i_{k_n}) + \tau(j_{k_1} \cdots j_{k_n}) \equiv x + y \equiv \tau(i_1 i_2 \cdots i_n) + \tau(j_1 j_2 \cdots j_n) \pmod 2 . \]

这就是要证的结论。

补一句：第 3 步凭什么能用"同一串对换"

对换是"互换排列中的两个数"，不涉及位置。若一次对换把 \(i\) 中的数 \(u, v\) 互换，那么它作用在 \(i_{k_1} \cdots i_{k_n}\) 上同样是"把数 \(u, v\) 互换"——因为 \(i_k\) 的每一项都取自 \(i\)。写成等式就是

\[ (i')_{k_1} (i')_{k_2} \cdots (i')_{k_n} = \big(i_{k_1} i_{k_2} \cdots i_{k_n}\big)', \]

即对换与"按 \(k\) 取出"这两种操作可以交换次序：第 1 步那串对换把 \(i\) 变成自然排列，作用在 \(i_k\) 上就把它变成"自然排列按同样下标取出"的结果，也就是 \(k_1 \cdots k_n\)。

方法二的关键动作

整个证明只有两招：先把命题在"排列是自然排列"这种最特殊的情形下验证，再用"化为自然排列所需的对换次数"把一般情形接回特殊情形。这与对换定理本身的证明是同一种思路——化归到特殊情形。

超纲（可跳过）

同一个结论的另一条视角：符号。 若记 \(\operatorname{sgn}(i_1 i_2 \cdots i_n) = (-1)^{\tau(i_1 i_2 \cdots i_n)}\)，则"符号关于复合是乘性的"这句话本身就蕴含本题：\(i_{k_1} \cdots i_{k_n}\) 对应的正是复合映射 \(m \mapsto i_{k_m}\)，于是

\[ \tau(i_{k_1} \cdots i_{k_n}) \equiv \tau(i_1 \cdots i_n) + \tau(k_1 \cdots k_n) \pmod 2, \]

\(j\) 同理；两式相加，多出的 \(2\,\tau(k_1 \cdots k_n)\) 是偶数，结论立得。这是对称群 \(S_n\) 与"群同态"的语言（\(\operatorname{sgn}: S_n \to \{\pm 1\}\)），本课不要求；列在这里只是说明同一个事实还可以怎么表述——它与方法一里"\(m \equiv \tau(k_1 \cdots k_n)\)"是同一件事。

思考题

思考题 1 · 两段各自递增的排列

设 \(a_1 a_2 \cdots a_k b_1 b_2 \cdots b_{n-k}\) 为一个 \(n\) 阶排列。若

\[ a_1 < a_2 < \cdots < a_k, \qquad b_1 < b_2 < \cdots < b_{n-k}, \]

求该排列的逆序数。

解答

答案是

\[ \tau(a_1 a_2 \cdots a_k b_1 b_2 \cdots b_{n-k}) = \sum_{i=1}^{k} (a_i - i) = \sum_{i=1}^{k} a_i - \frac{k(k+1)}{2} . \]

证明 前半段与后半段各自递增，所以段内任意两个数都不构成逆序。逆序只能来自"某个 \(a\) 在前、某个 \(b\) 在后，且 \(a > b\)"这样的跨段数对。于是逐个去数每个 \(a_i\) 与后半段的贡献。

固定 \(a_i\)。比 \(a_i\) 小的数共有 \(a_i - 1\) 个（它们是 \(1, 2, \dots, a_i - 1\)）。这些数分成两部分：

  • 落在前半段的：因为 \(a_1 < a_2 < \cdots < a_i\)，前半段中比 \(a_i\) 小的恰好是 \(a_1, \dots, a_{i-1}\)，共 \(i - 1\) 个。它们都排在 \(a_i\) 前面，与 \(a_i\) 不构成逆序；
  • 落在后半段的：共有 \((a_i - 1) - (i - 1) = a_i - i\) 个。它们都比 \(a_i\) 小，又都排在 \(a_i\) 后面，所以每一个都与 \(a_i\) 构成一个逆序。

所以 \(a_i\) 贡献 \(a_i - i\) 个逆序。把各个 \(a_i\) 的贡献相加：

\[ \tau = \sum_{i=1}^{k} (a_i - i). \]

按"前一个数所在的位置"分类，这些贡献两两不交、并起来正好是全部逆序（段内没有逆序），故没有重复也没有遗漏。

验算 取 \(n = 8\)、\(k = 2\)，\(a_1 = 6\)、\(a_2 = 7\)，后半段为 \(1,2,3,4,5,8\)。公式给出

\[ \tau = (6 - 1) + (7 - 2) = 10 . \]

直接检查 \(6\,7\,1\,2\,3\,4\,5\,8\)：\(6\) 与后面 \(1,2,3,4,5\) 构成 \(5\) 个逆序，\(7\) 与后面 \(1,2,3,4,5\) 构成 \(5\) 个逆序，共 \(10\) 个，一致。

顺带得到一个上界

由 \(a_i\) 后面还有 \(k - i\) 个比它大的数都在前半段，可知 \(a_i\) 最大只能取到 \(n - (k-i)\)，于是

\[ a_i - i \le \big(n - (k-i)\big) - i = n - k . \]

每项都不超过 \(n-k\)，共有 \(k\) 项，所以

\[ \tau \le k(n - k). \]

这个上界可以取到：当前半段取最大的 \(k\) 个数，即 \(a_i = n - k + i\) 时，每项都等于 \(n-k\)，此时 \(\tau = k(n-k)\)（前半段每个数都大于后半段每个数）。

课堂例题

例 1 · 用两种方法计算逆序数

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

解答

记排列为 \(2\,4\,6\,5\,7\,1\,3\)。

从数字角度（数 \(i\) 前面比 \(i\) 大的数的个数 \(m_i\)）：

\(i\) \(1\) \(2\) \(3\) \(4\) \(5\) \(6\) \(7\)
\(m_i\) \(5\) \(0\) \(4\) \(0\) \(1\) \(0\) \(0\)
\[ \tau = 5 + 0 + 4 + 0 + 1 + 0 + 0 = 10 . \]

从位置角度（数第 \(i\) 个位置后面比它小的数的个数 \(l_i\)）：依次为 \(1, 2, 3, 2, 2, 0, 0\)，

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

故 \(\tau(2\,4\,6\,5\,7\,1\,3) = 10\)，是偶排列。

例 2 · 对换改变奇偶性

把 \(2\,4\,6\,5\,7\,1\,3\) 中的 \(4\) 与 \(7\) 互换位置，求所得排列的逆序数，并验证奇偶性改变。

解答

\(4\) 在第 \(2\) 位、\(7\) 在第 \(5\) 位，互换后得到 \(2\,7\,6\,5\,4\,1\,3\)。

从数字角度：

\(i\) \(1\) \(2\) \(3\) \(4\) \(5\) \(6\) \(7\)
\(m_i\) \(5\) \(0\) \(4\) \(3\) \(2\) \(1\) \(0\)
\[ \tau = 5 + 0 + 4 + 3 + 2 + 1 + 0 = 15 . \]

从位置角度：\(l_i\) 依次为 \(1, 5, 4, 3, 2, 0, 0\)，

\[ \tau = 1 + 5 + 4 + 3 + 2 + 0 + 0 = 15 . \]

两个结果都是 \(15\)。逆序数由 \(10\) 变为 \(15\)，\(10\) 偶、\(15\) 奇，奇偶性确实改变，与定理一致。

顺便核对定理证明中的步数：被互换的 \(4\) 与 \(7\) 之间隔着 \(6, 5\) 两个数，即 \(s = 2\)，故需要 \(2s + 1 = 5\) 次相邻对换。

例 3 · 讨论反序排列的逆序数

\(n\) 阶反序排列 \(n\,(n-1)\,\cdots\,2\,1\) 的逆序数是多少？它什么时候是奇排列？

解答

反序排列中任意两个数都构成逆序，故

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

这是 \(n\) 阶排列的最大逆序数。写成 \(n = 4k + r\)（\(r = 0, 1, 2, 3\)）可知它是奇排列当且仅当 \(n \equiv 2, 3 \pmod 4\)：

\(n \bmod 4\) \(0\) \(1\) \(2\) \(3\)
反序排列的奇偶性 偶 偶 奇 奇

例如 \(n = 3\) 时 \(\tau = 3\) 为奇排列，\(n = 4\) 时 \(\tau = 6\) 为偶排列。

补充练习

练习 1

求 \(\tau(5\,3\,1\,4\,2)\)，并判断它是奇排列还是偶排列。

解答

从数字角度：\(m_i\) 依次为

\(i\) \(1\) \(2\) \(3\) \(4\) \(5\)
\(i\) 前面比 \(i\) 大的数 \(5,3\) \(5,3,4\) \(5\) \(5\) 无
\(m_i\) \(2\) \(3\) \(1\) \(1\) \(0\)
\[ \tau = 2 + 3 + 1 + 1 + 0 = 7 . \]

从位置角度核对：\(l_i\) 依次为 \(4, 2, 0, 1, 0\)，和为 \(7\)，一致。

故 \(\tau(5\,3\,1\,4\,2) = 7\)，是奇排列。

练习 2

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

解答

从数字角度：\(m_i\) 依次为

\(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 = 0 + 3 + 0 + 2 + 0 + 1 + 0 + 0 = 6 . \]

是偶排列。（从位置角度：\(l_i\) 依次为 \(0,1,2,3,0,0,0,0\)，和为 \(6\)，一致。）

这类"先排奇数、再排偶数"的排列是练习中的常客。若逐对检查要检查 \(\binom{8}{2} = 28\) 对，而按数字分类只需看 \(8\) 项。

练习 3

写出全部 \(3\) 阶排列，指出每个排列的逆序数与奇偶性，并验证奇、偶排列各占一半。

解答

\(3! = 6\) 个排列如下。

排列 逆序 \(\tau\) 奇偶性
\(1\,2\,3\) 无 \(0\) 偶
\(1\,3\,2\) \((3,2)\) \(1\) 奇
\(2\,1\,3\) \((2,1)\) \(1\) 奇
\(2\,3\,1\) \((2,1),(3,1)\) \(2\) 偶
\(3\,1\,2\) \((3,1),(3,2)\) \(2\) 偶
\(3\,2\,1\) 全部 \(3\) 对 \(3\) 奇

奇排列 \(3\) 个、偶排列 \(3\) 个，各为 \(\dfrac{3!}{2} = 3\)，与定理一致。

练习 4

判断：一个排列做一次对换后，逆序数一定增加或一定减少吗？

解答

都不一定，只能肯定改变一个奇数，即奇偶性翻转。

  • 对换 \(2\,4\,6\,5\,7\,1\,3\) 中的 \(4, 7\)（原为顺序），逆序数由 \(10\) 增至 \(15\)，增加 \(5\)；
  • 对换 \(2\,7\,6\,5\,4\,1\,3\) 中的 \(7, 4\)（原为逆序），逆序数由 \(15\) 减至 \(10\)，减少 \(5\)。

相邻对换时变化量必为 \(\pm 1\)；一般对换时变化量是奇数，但绝对值可以大于 \(1\)（本例中为 \(5 = 2s+1\)，\(s = 2\)）。

练习 5

用归纳法证明：反序排列 \(n\,(n-1)\,\cdots\,2\,1\) 可以经过 \(\binom{n}{2}\) 次相邻对换化为自然排列。

解答

对 \(n\) 归纳。

\(n = 2\)：\(2\,1\) 做 \(1\) 次相邻对换得 \(1\,2\)，而 \(\binom{2}{2} = 1\)，成立。

归纳步骤：设结论对 \(n - 1\) 成立。考虑反序排列 \(n\,(n-1)\,\cdots\,2\,1\)。把最前面的 \(n\) 依次与它右边的数做相邻对换，向右移动 \(n - 1\) 次，得到

\[ (n-1)\,(n-2)\,\cdots\,2\,1\,n . \]

前 \(n - 1\) 个数恰好是 \((n-1)\) 阶反序排列。由归纳假设，它可用 \(\binom{n-1}{2}\) 次相邻对换化为 \(1\,2\,\cdots\,(n-1)\)，此时整个排列成为 \(1\,2\,\cdots\,(n-1)\,n\)。总次数为

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

故结论成立。

顺便注意到：这一次数恰好等于它的逆序数。事实上"用相邻对换排序，最少需要且只需逆序数那么多次"，这是冒泡排序的原理，属于超纲内容（算法与组合），这里只用到上面的特例。

练习 6

设 \(n \ge 2\)。说明为什么不能把"奇排列与偶排列各 \(\dfrac{n!}{2}\) 个"这个结论照搬到 \(n = 1\)。

解答

\(n = 1\) 时只有一个排列 \(1\)，它的逆序数为 \(0\)，是偶排列，奇排列有 \(0\) 个。此时 \(\dfrac{n!}{2} = \dfrac{1}{2}\) 不是整数，结论自然不成立。

回看定理的证明，其中用到的映射 \(\varphi\) 是"互换前两个位置上的数"，这要求排列至少有 \(2\) 个位置，即 \(n \ge 2\)。这就是定理限定 \(n \ge 2\) 的原因。

参见