Bóna · 枚举与解析组合学导论 · 第 4 章 排列的计数
4.4 逆序数Inversions
本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。
在第 4.1 节中，我们研究了排列的下降（descent）。为此，我们把排列写成一行记号（one-line notation），然后考察相邻的两个元素是否处在错误的次序上，也就是较大的那个排在较小的那个前面。现在我们要做同样的事，但去掉“处于错误次序的两项必须相邻”这一要求。
本节目标把排列里“大的排在小的前面”这种逆序对数清楚，并由它引出排列的奇偶性（parity）。我们会看到：逆序数在排列写成轮换（cycle）乘积时仍然有用；逆序数的奇偶决定了一个排列是“偶排列”还是“奇排列”，并且这种奇偶性在排列相乘时像正负号一样运算——这正是交错群与排列符号（sign）的来历。
逆序对与逆序数
定义 4.40 设 \(p=p_1p_2\cdots p_n\) 是一个排列。若 \(ip_j\)，则称数对 \((p_i,p_j)\) 是 \(p\) 的一个逆序对（inversion）。\(p\) 的逆序对个数记为 \(i(p)\)，称为 \(p\) 的逆序数。
如果一个数对 \((p_i,p_j)\) 不是逆序对，那么它被称为——毫不令人吃惊地——一个非逆序对（non-inversion）。
例 4.41 排列 \(31524\) 有四个逆序对，它们是 \((3,1)\)、\((3,2)\)、\((5,2)\) 与 \((5,4)\)。
把例 4.41 一步步数出来
我们逐一检查每一对“左项 vs 右项”，只要左边的数比右边的数大，就是一个逆序对。排列写成带位置的形式：
\[ \underset{1}{3}\;\underset{2}{1}\;\underset{3}{5}\;\underset{4}{2}\;\underset{5}{4}. \]
- 以首项 \(3\) 为左项：右边有 \(1,5,2,4\)。比 \(3\) 小的是 \(1\) 和 \(2\)，得逆序对 \((3,1)\)、\((3,2)\)。
- 以 \(1\) 为左项：右边 \(5,2,4\) 全都比 \(1\) 大，没有逆序对。
- 以 \(5\) 为左项：右边 \(2,4\) 都比 \(5\) 小，得逆序对 \((5,2)\)、\((5,4)\)。
- 以 \(2\) 为左项：右边只有 \(4>2\)，无逆序对。末项 \(4\) 后面没有元素。
- 合计 \(i(31524)=2+0+2+0=4\)。♦
长度为 \(n\) 且恰有 \(k\) 个逆序对的排列个数记为 \(b(n,k)\)。注意：如果我们把 \(p\) 倒着读，那么每一个逆序对都变成了非逆序对，反之亦然。于是，长度为 \(n\) 且有 \(k\) 个逆序对的排列，与有 \(\binom{n}{2}-k\) 个逆序对的排列一样多。
为什么是 \(\binom{n}{2}-k\)
在一个长度为 \(n\) 的排列里，按位置 \(i具体验证：取 \(n=3\)，\(\binom{3}{2}=3\)。六个排列的逆序数为 \(123\!:0,\ 132\!:1,\ 213\!:1,\ 231\!:2,\ 312\!:2,\ 321\!:3\)。于是 \(b(3,0)=b(3,3)=1\)，\(b(3,1)=b(3,2)=2\)，确实关于 \(k\leftrightarrow 3-k\) 对称。
全图与逆置换
即便我们把排列看成轮换的乘积，排列 \(p\) 的逆序数依然是有趣的。为了证明这方面的一个简单结果，我们先定义函数 \(f:[n]\to[n]\) 的全图（full diagram）。这个图由 \(2n\) 个点组成：\(n\) 个对应 \(f\) 的定义域，\(n\) 个对应 \(f\) 的值域；这两个 \(n\) 元集合分别竖直排列、彼此相对。若 \(f(i)=j\)，则从第一组的点 \(i\) 向第二组的点 \(j\) 画一条箭头。
例 4.42 图 4.3 展示了排列 \(24153\) 的全图。
下面的命题把用一行记号定义的逆序概念，与把排列看作函数时定义的逆置换概念联系了起来。
命题 4.43 对每个排列 \(p\)，都有 \(i(p)=i(p^{-1})\)。
证明. 若我们画出函数 \(p:[n]\to[n]\) 的全图，则 \(i(p)\) 恰好等于该图中箭头交叉的个数。（请读者自行思考这一点。）然而，\(p^{-1}\) 的全图与 \(p\) 的全图相同，只是把箭头方向反转。因此 \(p^{-1}\) 全图中的交叉数与 \(p\) 全图中的交叉数相等，命题得证。♦
“逆序数 = 交叉数”是怎么回事
把左、右两列点都从上到下按 \(1,2,\dots,n\) 排好。考虑定义域里的两个点 \(i
两条箭头相交，当且仅当它们“上下次序反过来了”：左边 \(i\) 在 \(j\) 上方，但右边的落点 \(p(i)\) 却在 \(p(j)\) 下方，即 \(p(i)>p(j)\)。
而 \(ip(j)\) 正是“位置 \(i,j\) 构成一个逆序对”的定义。
所以每个逆序对对应恰好一处交叉，交叉总数 \(=i(p)\)。
把全图所有箭头掉头，得到的是 \(p^{-1}\) 的全图（因为 \(p(i)=j\) 反过来就是 \(p^{-1}(j)=i\)）。掉头不改变任何两条线是否相交，故交叉数不变，得 \(i(p)=i(p^{-1})\)。♦
在图 4.3 中数一数交叉，恰好是 \(4\) 个，与 \(i(24153)=4\) 吻合。
奇排列与偶排列
下面这个概念在组合学之外的许多数学分支中都很有用。
定义 4.44 若 \(i(p)\) 为偶数，则称排列 \(p\) 为偶排列（even）。类似地，若 \(i(p)\) 为奇数，则称 \(p\) 为奇排列（odd）。
人们会觉得“偶”和“奇”应当是出现得一样频繁的性质。下面的命题表明事实确实如此。
命题 4.45 设 \(n\ge 2\)。则 \(n\)-排列中偶排列（等价地，奇排列）的个数为 \(n!/2\)。
证明. 设 \(p\) 是任意一个 \(n\)-排列，并设 \(p'\) 是把 \(p\) 的前两项对调得到的排列。那么 \(i(p)\) 与 \(i(p')\) 的差为 \(+1\) 或 \(-1\)，所以它们奇偶性不同。对所有 \(n\)-排列重复这一论证，可见 \(S_n\) 能被分成大小相等的两个子集：一个由偶排列组成，另一个由奇排列组成。♦
为什么对调前两项差恰为 \(\pm1\)
设 \(p=p_1p_2p_3\cdots p_n\)，对调前两项得 \(p'=p_2p_1p_3\cdots p_n\)。除了第 \(1,2\) 位之间这一对，其余所有数对的相对位置都没变，逆序状态完全不变。唯一改变的是 \(p_1\) 与 \(p_2\) 这一对：
- 若原来 \(p_1
- 若原来 \(p_1>p_2\)（逆序对），对调后变成非逆序对，逆序数 \(-1\)。
- 无论哪种情形，\(i(p)\) 与 \(i(p')\) 都相差 \(1\)，奇偶必然相反。
- “对调前两项”把每个排列与另一个排列一一配对（再对调一次就回到自己），每对里一奇一偶。于是奇、偶各占一半，各 \(n!/2\) 个。♦
排列矩阵
事实证明，如果我们知道排列 \(p\) 与 \(q\) 的奇偶性，就能确定 \(pq\) 与 \(qp\) 的奇偶性。做到这一点的一种方法，是借助下面这种非常有用的、用矩阵表示排列的方式。
定义 4.46 设 \(p\in S_n\)，\(p=p_1p_2\cdots p_n\)。\(p\) 的排列矩阵（permutation matrix）是 \(n\times n\) 矩阵 \(A_p\)，定义为
\[ A_p(i,j)=\begin{cases}1 & \text{若 }p_i=j,\\[2pt] 0 & \text{否则.}\end{cases} \]
换言之，\(A_p\) 的每一行、每一列都恰好含一个 \(1\) 和 \(n-1\) 个 \(0\)。要确定第 \(i\) 行中哪个元素等于 \(1\)，只需找出 \(p\) 第 \(i\) 个位置上的值；要确定第 \(j\) 列中哪个元素等于 \(1\)，只需找出 \(p\) 中处在第 \(j\) 个位置的元素，即 \(p_j\)。
例 4.47 若 \(p=3241=(2)(431)\)，则
\[ A_p=\begin{pmatrix}0&0&1&0\\0&1&0&0\\0&0&0&1\\1&0&0&0\end{pmatrix}. \]
用矩阵 \(A_p\) 表示排列的关键性质在于：这是一个同态（homomorphism），也就是说，这些矩阵相乘的规律与对应排列相乘的规律一致。
引理 4.48 设 \(p=p_1p_2\cdots p_n\) 与 \(q=q_1q_2\cdots q_n\) 为 \(n\)-排列，则
\[ A_pA_q=A_{pq}. \]
证明. 由排列矩阵的定义知 \(A_p\)、\(A_q\)、\(A_{pq}\) 都是 \(0\text{-}1\) 矩阵。容易看出 \(A_pA_q\) 也是 \(0\text{-}1\) 矩阵：它的元素可由 \(A_p\) 的某一行与 \(A_q\) 的某一列做点积得到，因此只能是 \(0\) 或 \(1\)。于是只需证明
\[ x=A_{pq}(i,j)=1 \iff y=(A_pA_q)(i,j)=1. \]
由矩阵乘法的定义直接得到
\[ y=(A_pA_q)(i,j)=\sum_{k=1}^{n}A_p(i,k)\,A_q(k,j). \]
也就是说，\(y=1\) 当且仅当存在某个 \(k\in[n]\) 使得 \(A_p(i,k)=1\) 与 \(A_q(k,j)=1\) 同时成立。把 \(p,q\) 看作函数，这等价于 \(p(i)=k\) 且 \(q(k)=j\)，意味着 \(q(p(i))=(pq)(i)=j\)，而这按定义又等价于 \(x=A_{pq}(i,j)=1\)。♦
本书的乘法约定
注意上面用到 \((pq)(i)=q(p(i))\)：在本书中，乘积 \(pq\) 表示先作用 \(p\)、再作用 \(q\)。点积 \(\sum_k A_p(i,k)A_q(k,j)\) 之所以“只在一个 \(k\) 处取到 \(1\)”，是因为 \(A_p\) 第 \(i\) 行只有 \(k=p(i)\) 处为 \(1\)，而要让乘积非零还需 \(A_q(k,j)=1\)，即 \(q(k)=q(p(i))=j\)。这恰好给出了 \(pq\) 的像，于是矩阵乘法“自动”实现了排列的复合。
关于 \(p\) 的许多重要信息都能轻松地从 \(A_p\) 中读出。
命题 4.49 排列 \(p\) 是奇排列当且仅当 \(\det A_p=-1\)；类似地，\(p\) 是偶排列当且仅当 \(\det A_p=1\)。换言之，
\[ \det A_p=(-1)^{i(p)}. \]
证明. 我们对 \(n\) 作归纳证明。当 \(n=1\) 与 \(n=2\) 时命题为真。假设命题对 \(n-1\) 成立，设 \(p=p_1p_2\cdots p_n\)，并设 \(p_j=1\)。则由行列式的展开定理可知
\[ \det A_p=(-1)^{\,j-1}\det A_{p'}, \]
其中 \(p'\) 是把 \(p\) 中的元素 \(1\) 删去并重新标号后得到的 \((n-1)\)-排列。事实上，把 \(A_p\) 按它的第一列展开，便得到上式。最后注意 \(i(p)=i(p')+(j-1)\)，再对 \(p'\) 应用归纳假设，命题即得证。♦
把命题 4.49 用到例 4.47
取 \(p=3241\)。先数它的逆序数：逆序对为 \((3,2),(3,1),(2,1),(4,1)\)，共 \(4\) 个，故 \(i(p)=4\) 为偶，预期 \(\det A_p=(-1)^4=1\)。
- \(p\) 中 \(1\) 在第 \(4\) 位，故 \(j=4\)，符号因子 \((-1)^{j-1}=(-1)^3=-1\)。
- 删去 \(1\) 后剩 \(3\,2\,4\)，重新标号（把 \(2,3,4\) 换成 \(1,2,3\)）得 \(p'=2\,1\,3\)，其逆序数 \(i(p')=1\)。
- 核对 \(i(p)=i(p')+(j-1)=1+3=4\)，一致。
- 由归纳 \(\det A_{p'}=(-1)^{1}=-1\)，于是 \(\det A_p=(-1)^3\cdot(-1)=1=(-1)^4\)。结论吻合。♦
推论 4.50 图 4.4 显示了把不同奇偶性的排列相乘会发生什么。
推论 4.50 为什么成立
由命题 4.49，\(\det A_p=(-1)^{i(p)}\)；由引理 4.48，\(A_pA_q=A_{pq}\)。行列式有乘法性 \(\det(A_pA_q)=\det A_p\cdot\det A_q\)，于是
\[ (-1)^{i(pq)}=\det A_{pq}=\det A_p\cdot\det A_q=(-1)^{i(p)}\,(-1)^{i(q)}=(-1)^{i(p)+i(q)}. \]
所以 \(i(pq)\) 的奇偶性 \(=\,i(p)+i(q)\) 的奇偶性。把“偶”当作 \(+1\)、“奇”当作 \(-1\)，乘积的符号就是两者符号之积，这正是图 4.4 的内容。
特别地，偶排列之积总是偶排列，所以偶排列的集合关于乘法封闭。类似地，偶排列的逆也总是偶排列。因此所有偶 \(n\)-排列组成的集合本身就很有意思，它被称为\(n\) 次交错群（alternating group of degree \(n\)），记作 \(A_n\)。
我们指出，排列的奇偶性常被称为该排列的符号（sign）。原因正如我们刚才所见：不同奇偶性的排列相乘的规律，就像不同正负号的实数相乘一样。
对换与轮换的奇偶性
一个仅把 \([n]\) 中两个元素互换、而保持其余所有元素不动的排列，称为一个对换（transposition）。结果表明，对换全都是奇排列。
命题 4.51 若 \(p\) 是一个对换，则 \(i(p)\) 为奇数。
证明. 先假设 \(p=(i\ \ i+1)\)，即 \(p\) 互换 \([n]\) 中两个相邻元素。则 \(p\) 恰有一个逆序对，命题成立。再假设 \(p=(i,\ i+k)\)，即 \(p\) 所移动的两项之间隔着 \(k-1\) 个元素。我们断言 \(i(p)=2k-1\)。事实上，位于 \(i\) 与 \(i+k\) 之间的每一个元素都参与了两个逆序对：一个与 \(i\) 构成，一个与 \(i+k\) 构成；这 \(k-1\) 个中间元素共贡献 \(2(k-1)\) 个逆序对。再加上 \((i,\,i+k)\) 自身构成的最后一个逆序对，得 \(i(p)=2(k-1)+1=2k-1\)，为奇数。♦
用具体数字数对换的逆序数
取 \(n=5\)，对换 \(p=(2,5)\)（即 \(i=2,\ k=3\)），它把位置 \(2\) 与 \(5\) 上的值互换。把它写成一行记号：恒等排列 \(12345\) 互换第 \(2,5\) 项得 \(p=1\,5\,3\,4\,2\)。
- 中间元素是 \(3,4\)（共 \(k-1=2\) 个）。
- \(5\) 与中间各项：\((5,3),(5,4)\)，\(2\) 个逆序对。
- 中间各项与末位 \(2\)：\((3,2),(4,2)\)，\(2\) 个逆序对。
- 大端 \(5\) 与小端 \(2\) 自身：\((5,2)\)，\(1\) 个逆序对。
- 合计 \(i(p)=2+2+1=5=2k-1=2\cdot3-1\)，奇数。♦
下面这个引理听起来或许有点违反直觉。
引理 4.52 由一个 \(n\)-轮换组成的排列 \(a=(a_1a_2\cdots a_n)\) 是偶排列，当且仅当 \(n\) 为奇数。
证明. 为本证明之便，我们在排列的轮换记号中略去所有 \(1\)-轮换。例如 \(6\)-排列 \((1)(32)(54)(6)\) 将写作 \((32)(54)\)。这不会造成歧义，因为轮换记号中没有出现的元素必定是不动点。
我们对 \(n\) 作归纳证明。初始情形 \(n=1\) 与 \(n=2\) 为真：因为排列 \((x)\) 的逆序数为偶（即 \(0\)），而排列 \((y\ z)\) 的逆序数为奇——这正是命题 4.51 所示。
现在假设命题对所有小于 \(n\) 的正整数成立，设 \(a=(a_1a_2\cdots a_n)\)。关键的观察是
\[ a=(a_{n-1}\ a_n)(a_1a_2\cdots a_{n-1}). \]
令 \(q=(a_{n-1}\ a_n)\)，\(a'=(a_1a_2\cdots a_{n-1})\)，则有 \(a=q\,a'\)。两边取行列式，并利用命题 4.49，得
\[ \det A_a=\det A_q\cdot\det A_{a'}=-\det A_{a'}, \]
其中由命题 4.51 知 \(\det A_q=-1\)。所以 \(a\) 的奇偶性与 \(a'\) 的相反，归纳步骤完成，证明结束。♦
把引理 4.52 算成具体数
一个 \(n\)-轮换可以写成 \(n-1\) 个对换之积。按本书“\(pq\) 表示先作用 \(p\) 再作用 \(q\)”的约定（见上文），反复使用引理证明里的关键观察 \((a_1\cdots a_k)=(a_{k-1}\,a_k)(a_1\cdots a_{k-1})\)，就得到
\[ (a_1a_2\cdots a_n)=(a_{n-1}\,a_n)(a_{n-2}\,a_{n-1})\cdots(a_1\,a_2). \]
共 \(n-1\) 个对换。每个对换是奇排列（命题 4.51），由推论 4.50 的符号相乘规律，整个轮换的奇偶性 \(=(-1)^{\,n-1}\)。
- \(n\) 为奇数 \(\Rightarrow n-1\) 为偶 \(\Rightarrow(-1)^{n-1}=+1\Rightarrow\) 偶排列。
- \(n\) 为偶数 \(\Rightarrow n-1\) 为奇 \(\Rightarrow(-1)^{n-1}=-1\Rightarrow\) 奇排列。
- 验证：\(3\)-轮换 \((1\,2\,3)\) 写成一行记号是 \(231\)，逆序数 \(2\)，偶（\(n=3\) 奇，✓）；\(2\)-轮换（即对换）\(n=2\) 偶 \(\Rightarrow\) 奇排列，✓。
返回 全书目录