高等代数 · 第9集 · 排列的奇偶性

☰本集目录

◎学习目标

理解 n 元排列与自然系排列（即 \(1,2,\dots,n\)）的概念，明确排列的总数为 \(n!\)；
掌握逆序数的定义：一个排列中「逆序数对」的数目，记作 \(\tau\)；
学会区分偶排列（逆序数为偶数）与奇排列（逆序数为奇数），并能对一个具体排列数出逆序数；
理解对换（相邻两个数互换位置）的定义，并记住核心定理：对换改变排列的奇偶性；
理解任意 n 元排列可以通过一系列相邻对换变成自然系排列；
记住推论：把任意排列 \(j_1 j_2 \dots j_n\) 变成自然系排列 \(1\,2\,\dots\,n\) 所做的对换次数 \(S\)，与该排列本身的奇偶性相同。

1回顾：n 元排列与自然系排列 ⏱ 00:00

上一节（第 8 集）已经介绍了 n 元排列的基本概念。这里回顾一下：把 \(1,2,\dots,n\) 这 \(n\) 个自然数排成一列，就得到一个n 元排列，记作 \(j_1 j_2 \dots j_n\)。n 元排列的总数为 \(n!\)（即 \(1\times2\times\cdots\times n\)）。⏱ 00:42

其中一种特殊排列是把数按从小到大（自然顺序）排好：

1, 2, 3, \dots, n

这个排列没有任何「逆序」（没有前面比后面大的数对），因此它的逆序数为 0，是偶排列。⏱ 01:18

本集路线逆序数与奇偶性 \(\to\) 对换的定义 \(\to\) 相邻对换改变奇偶性（先证特殊情形） \(\to\) 一般对换的证明（用相邻对换分解） \(\to\) 任意排列变成自然系排列 \(\to\) 对换次数与奇偶性同奇偶。

2逆序数与排列的奇偶性 ⏱ 00:27

2.1 什么是逆序（逆序对）

在一个排列中，如果某两个数 \(a\) 在前、\(b\) 在后，但 \(a > b\)（即前面的数比后面的数大），就称这一对数为一个逆序（逆序数对）。例如在排列 2431 中，逐对检查：2>1、4>3、4>1、3>1，共 4 个逆序。⏱ 00:27

2.2 逆序数的定义

定义 · 逆序数与奇偶排列一个排列中逆序的数目称为该排列的逆序数，用符号 \(\tau\) 表示。

逆序数为偶数的排列称为偶排列；
逆序数为奇数的排列称为奇排列。

一个排列非偶即奇，二者必居其一。

2.3 例子：数排列 2431 的逆序数

排列 \(2\,4\,3\,1\)：从左往右看，2 后面有 1 比它小（1 个逆序：2>1）；4 后面有 3、1 比它小（2 个逆序：4>3, 4>1）；3 后面有 1 比它小（1 个逆序：3>1）。合计 \(\tau = 1+2+1 = 4\)，是偶数，所以 2431 是偶排列。⏱ 01:12

排列	逆序数 \(\tau\)	奇偶性
\(1\,2\,3\,4\)	0	偶
\(2\,4\,3\,1\)	4	偶
\(1\,3\,2\,4\)	1	奇
\(4\,3\,2\,1\)	6	偶
\(3\,1\,2\)	2	偶
\(2\,1\,3\)	1	奇

3对换（互换位置） ⏱ 02:50

定义 · 对换在排列中，把其中两个数互换位置，其余各数不动，这个操作称为一次对换（相邻对换即互换的两个数在原排列中相邻）。

j_1 \; j_2 \; \cdots \; j_n \quad \xrightarrow{\text{对换 } i \text{ 和 } j} \quad j_1 \; j_2 \; \cdots \; j_n \quad (\text{其中 } i \leftrightarrow j)

对换的记号：把 4 和 1 对换，记作 \((4\,1)\)。

3.1 对换改变排列奇偶性的观察

对偶排列 \(2\,4\,3\,1\)（\(\tau=4\)）做对换 \((4\,1)\)，得到 \(2\,1\,3\,4\)。它的逆序数：只有 \(2>1\) 一个，即 \(\tau=1\)，是奇排列。可以看到对换把偶排列变成了奇排列。⏱ 03:34

核心定理（本节） 对换改变排列的奇偶性。即：对任何一个排列做一次对换后，排列的奇偶性必然翻转（偶变奇、奇变偶）。

4相邻对换改变奇偶性（特殊情形） ⏱ 04:04

证明策略是「从简单到一般」：先看对换的两个数相邻的情形（即 \(i\) 和 \(j\) 挨着），再处理一般情形。⏱ 06:24

证明：相邻对换使逆序数恰好改变 1

设排列中 \(i\) 和 \(j\) 相邻，对换前 \(i\) 在前、\(j\) 在后，对换后 \(j\) 在前、\(i\) 在后。其他所有数 \(P, Q, \dots\) 的位置不变。

对于 \(P, Q\) 中任一个数 \(X\)，\(X\) 与 \(i\) 的相对顺序、\(X\) 与 \(j\) 的相对顺序，在对换前后都没有变（因为 \(P, Q\) 都不动）；
唯一发生变化的是 \(i\) 和 \(j\) 之间的相对顺序：如果原来 \(i > j\)（逆序），对换后变成顺序；反之亦然。

因此逆序数只改变 1（+1 或 −1），奇偶性必然翻转。

证毕。\(\square\)

例 · 验证排列 \(3\,1\,2\)（\(\tau=2\)，偶）。对换相邻的 \(1\) 和 \(2\)，得 \(3\,2\,1\)（逆序：3>2, 3>1, 2>1，\(\tau=3\)，奇）。奇偶性确实翻转。

5一般对换的证明 ⏱ 09:39

当 \(i\) 和 \(j\) 不相邻时，设它们之间隔了 \(S\) 个数 \(K_1, K_2, \dots, K_S\)。可以把一次一般对换分解为一系列相邻对换来完成。⏱ 10:10

证明思路：一般对换 = 相邻对换的组合

设排列中 \(i\) 和 \(j\) 不相邻，中间有 \(S\) 个数 \(K_1, \dots, K_S\)。具体分解方式：

先把 \(i\) 逐步右移：\(i\) 与 \(K_1\) 对换、再与 \(K_2\) 对换、……、与 \(K_S\) 对换，最后与 \(j\) 对换，共 \(S+1\) 次相邻对换（\(S\) 次越过中间数 + 1 次与 \(j\) 本身对换），\(i\) 移到 \(j\) 原来的位置；
再把 \(j\) 逐步左移：\(j\) 与 \(K_S\) 对换、与 \(K_{S-1}\) 对换、……、与 \(K_1\) 对换，共 \(S\) 次相邻对换，\(j\) 移到 \(i\) 原来的位置。

总共做了 \((S+1) + S = 2S+1\) 次相邻对换。\(2S+1\) 是奇数，每次相邻对换翻转一次奇偶性，奇数次翻转后奇偶性确实翻转——这就证明了一般对换也改变排列的奇偶性。

更简洁的说法：一般对换 \(i \leftrightarrow j\) 可以用 \(2S+1\) 次相邻对换实现，\(2S+1\) 是奇数，每次相邻对换翻转一次，奇数次翻转后奇偶性确实翻转。⏱ 14:31

证毕。\(\square\)

注意这里的关键逻辑是：因为相邻对换（已证）每次翻转奇偶性，所以任何由相邻对换组合而成的操作，其奇偶性翻转次数等于相邻对换的次数。一般对换 \(i\leftrightarrow j\)（中间隔 \(S\) 个数）恰好用 \(2S+1\) 次相邻对换实现（奇数次），故也翻转一次。

6任意排列可以变成自然系排列 ⏱ 14:44

核心结论：任何一个 n 元排列 \(j_1\, j_2 \, \dots \, j_n\)，都可以通过一系列对换（特别是相邻对换）变成自然系排列 \(1\,2\,\dots\,n\)。⏱ 15:18

6.1 构造方法（从后往前）

对 n 元排列 \(j_1 j_2 \dots j_n\)，用如下策略把它变成 \(1, 2, \dots, n\)：⏱ 15:37

先看最后一个位置：如果是 \(n\) 以外的数，把 \(n\) 通过相邻对换「挪」到最后；
再倒数第二位：把 \(n-1\) 挪到倒数第二位；
依此类推，直到第 1 位变成 1。

这个过程一定能完成，因为每个数总可以通过相邻对换到达指定位置。

6.2 例子：25143 \(\to\) 12345

五元排列 \(2\,5\,1\,4\,3\) 变自然系 \(1\,2\,3\,4\,5\)：⏱ 15:30

把 5 放到最后：对换 \((5\,3)\)，得 \(2\,3\,1\,4\,5\)；
把 4 放到倒数第二位：对换 \((3\,1)\)，得 \(2\,1\,3\,4\,5\)；
把 1 放到第一位：对换 \((2\,1)\)，得 \(1\,2\,3\,4\,5\)。

共做了 3 次对换（奇数）。而 \(2\,5\,1\,4\,3\) 本身：逆序有 (2,1),(5,1),(5,4),(5,3),(4,3)，共 5 个，是奇排列。对换次数 3 也是奇数——两者奇偶性相同！⏱ 18:10

7对换次数与排列奇偶性相同 ⏱ 19:35

定理设 n 元排列 \(j_1\, j_2 \, \dots \, j_n\) 经过 \(S\) 次对换变成自然系排列 \(1\,2\,\dots\,n\)，则对换次数 \(S\) 的奇偶性与排列 \(j_1\, j_2 \, \dots \, j_n\) 的奇偶性相同。

若 \(j_1\, j_2 \, \dots \, j_n\) 是奇排列，则 \(S\) 必为奇数；
若 \(j_1\, j_2 \, \dots \, j_n\) 是偶排列，则 \(S\) 必为偶数。

证明

注意：自然系排列 \(1\,2\,\dots\,n\) 是偶排列（逆序数 0）。每次对换翻转一次奇偶性。

若 \(j_1\, j_2 \, \dots \, j_n\) 是奇排列，要变成偶排列 \(1\,2\,\dots\,n\)，必须做奇数次对换（因为奇数次翻转才能让奇变偶）；
若 \(j_1\, j_2 \, \dots \, j_n\) 是偶排列，要变成偶排列 \(1\,2\,\dots\,n\)，必须做偶数次对换（因为偶数次翻转后奇偶性不变）。

因此对换次数 \(S\) 与排列本身的奇偶性相同。⏱ 20:05

证毕。\(\square\)

重要说明这个结论说明「把一个排列变成自然系排列所需的对换次数」的奇偶性是唯一确定的（不依赖于你选择哪条路径）——因为无论怎么对换，次数奇偶性都一样。这是后面定义行列式（用对换次数定号）的基础。

★重点回顾

1

逆序：排列中前面比后面大的数对；逆序数 \(\tau\)：逆序的总数，用于判定排列的奇偶性。

2

偶排列（\(\tau\) 为偶数）与奇排列（\(\tau\) 为奇数）；自然系排列 \(1\,2\,\dots\,n\) 是偶排列（\(\tau=0\)）。

3

对换：排列中两个数互换位置、其余不动。核心定理：对换改变排列的奇偶性。

4

证明方法「从简单到一般」：先证相邻对换（逆序数恰好改变 1），再一般对换 = 相邻对换的组合（\(2S+1\) 次，奇数次翻转 → 奇偶性翻转）。

5

任意 n 元排列都可以通过一系列对换变成自然系排列 \(1\,2\,\dots\,n\)；所需对换次数 \(S\) 的奇偶性唯一确定，且与排列本身的奇偶性相同。

6

这些结论为下一节（n 阶行列式定义）中「按列指标排列定号」提供理论依据：\((-1)^{\tau}\) 中 \(\tau\) 是列指标排列的逆序数。

⚠易错点提醒

常见错误

逆序数数错：数逆序时，对每个位置上的数，看它右边有多少个比它小的数，累加起来。要逐位检查，不要遗漏。例如 2431 中：2 右边比它小的有 {1}，4 右边比它小的有 {3,1}，3 右边比它小的有 {1}，共 1+2+1=4。
认为对换不改变奇偶性：错！一次对换一定翻转奇偶性。这是本节核心结论。
混淆相邻对换与一般对换的次数：一般对换（中间隔 S 个数）等价于 \(2S+1\) 次相邻对换，是奇数次。不要误算成 \(2S\) 次（偶数）。
认为「对换次数唯一」：对换的次数不唯一（可以用不同路径），但次数奇偶性唯一确定。这是关键区别。
把「偶排列」与「偶数排列」混淆：「偶排列」指逆序数为偶数的排列，不是指排列中包含偶数。
自然系排列的奇偶性记错：\(1\,2\,\dots\,n\) 没有逆序（\(\tau=0\)），是偶排列。0 是偶数。

✎自测与作业

求排列 \(3\,5\,1\,4\,2\) 的逆序数 \(\tau\)，判断它是奇排列还是偶排列。
对排列 \(2\,4\,1\,3\) 做一次对换 \((4\,3)\)，写出新排列，数它的逆序数，验证对换改变了奇偶性。
写出 4 元排列中所有偶排列（共 12 个，提示：4! = 24，其中偶、奇各 12 个），并给出 5 个例子说明。
证明：五元排列 \(5\,4\,3\,2\,1\) 的逆序数为 10，是偶排列；把它变成 \(1\,2\,3\,4\,5\) 至少需要多少次对换？（答案：奇数次，至少 1 次对换 \((5\,1)\) 不够——需 10 次相邻对换；但一般对换最少 5 次：(5,1), (4,2), (3,不动), …… 思考最优方案。）
解释为什么「把排列 \(j_1\, j_2 \, \dots \, j_n\) 变成自然系排列所做的对换次数 \(S\)」的奇偶性唯一确定，且等于排列本身的奇偶性。
（思考题）如果自然系排列不是 \(1\,2\,\dots\,n\) 而是 \(n\,(n-1)\,\dots\,1\)，对换次数奇偶性还有同样的性质吗？（提示：\(n(n-1)\dots 1\) 的逆序数为 \(\binom{n}{2}\)，奇偶性取决于 n。）

下一集预告第 10 集 · n 阶行列式的定义、上三角形行列式：利用本集排列奇偶性结论，给出 n 阶行列式的定义（\(n!\) 项和、按列指标排列定号），并推导上（下）三角形行列式值 = 主对角线乘积。