跳转至

对换与奇偶排列

本页面引入对换这一操作，用它给排列的"奇偶性"下一个可计算的刻画，并证明本节的核心定理：一次对换必然改变排列的奇偶性。

这条定理的证明本身就是一次方法论示范——从特殊到一般：先把一般情形化归为"被对换的两个数相邻"的特殊情形。这个手法在本课程后面会反复出现（老师说它在整个高等代数里要用到六七次）。

前置知识
  • 逆序与逆序数：逆序、逆序数 \(\tau\) 与两种计数方法
  • 数学归纳法（本页"工具"一节有复习）
  • 映射、单射、满射、双射（本页只用到最简单的部分，在奇排列与偶排列的个数里会集中交代）

引入：一个自然的问题

既然每个排列都有一个逆序数，而逆序数非奇即偶，排列就被分成两类：

定义（奇排列与偶排列）

设 \(i_1 i_2 \cdots i_n\) 是 \(n\) 阶排列。

  • 若 \(\tau(i_1 i_2 \cdots i_n)\) 是奇数，称它是奇排列；
  • 若 \(\tau(i_1 i_2 \cdots i_n)\) 是偶数，称它是偶排列。

逆序数为 \(0\) 的自然排列 \(1\,2\,\cdots\,n\) 是偶排列；由最大逆序数，反序排列的奇偶性取决于 \(n \bmod 4\)。

于是立刻有一个问题：在 \(n!\) 个排列中，奇排列和偶排列各有多少个？

这个问题靠"数出来"是回答不了的（\(n\) 一大就没法数）。我们需要找一个工具。工具就是"对换"。

对换

定义（对换）

在一个排列中，把其中任意两个数互换位置，其余的数保持不动，这样的操作称为一次对换。特别地，若被互换的两个数在排列中相邻，则称为一次相邻对换。

记号上，把排列中位于第 \(p\) 位与第 \(q\) 位的数互换，可记作 \((p\ q)\)；对换的对象是"数"，而每个数在排列中只出现一次，所以"互换两个数"与"互换两个位置"是同一件事。

对换的例子

对排列 \(i_1 i_2 \cdots i_7 = 2\,4\,6\,5\,7\,1\,3\) 做一次对换，把 \(4\) 与 \(7\) 互换位置：\(4\) 在第 \(2\) 位、\(7\) 在第 \(5\) 位，于是

\[ 2\,\boxed{4}\,6\,5\,\boxed{7}\,1\,3 \quad \longrightarrow \quad 2\,\boxed{7}\,6\,5\,\boxed{4}\,1\,3 . \]

得到新排列 \(2\,7\,6\,5\,4\,1\,3\)。

这是一次非相邻的对换（\(4\) 与 \(7\) 之间隔着 \(6, 5\)）。下面会看到，它把逆序数从 \(10\) 变成 \(15\)——奇偶性确实改变。

定理：对换改变奇偶性

定理（对换改变奇偶性）

对排列做一次对换，所得排列与原排列奇偶性相反：奇排列变成偶排列，偶排列变成奇排列。

等价的说法：一次对换使逆序数改变一个奇数。

证明（证明思想：从特殊到一般）

第一步：先证相邻对换的情形。

考虑排列中相邻的两个数 \(j, k\)，记这一段的上下文为

\[ \cdots\, j\, k\, \cdots \]

其余的数记成"\(\cdots\)"。做相邻对换后得到

\[ \cdots\, k\, j\, \cdots . \]

比较两个排列：

  • \(j\) 与它前面那些数的相对位置没变，所以由它们与 \(j\) 或 \(k\) 构成的逆序关系（谁大谁小）不变；
  • \(j\) 与它后面那些数的相对位置也没变，同理不产生新的逆序；
  • 唯一改变的是 \(j\) 与 \(k\) 这一对：对换前 \(j\) 在前、\(k\) 在后，对换后 \(k\) 在前、\(j\) 在后。
  • 若原来 \(j < k\)，则原来 \((j, k)\) 不是逆序，对换后 \((k, j)\) 是逆序，逆序数 \(+1\)；
  • 若原来 \(j > k\)，则原来 \((j, k)\) 是逆序，对换后 \((k, j)\) 不是逆序，逆序数 \(-1\)。

所以相邻对换使逆序数恰好改变 \(\pm 1\)，是奇数，奇偶性改变。

第二步：把一般情形化归为相邻情形。

设要互换的两数 \(j, k\) 之间有 \(s\) 个数，排列形如

\[ \cdots\, j\, i_1\, i_2\, \cdots\, i_s\, k\, \cdots . \]

先让 \(j\) 向右依次与 \(i_1, i_2, \dots, i_s, k\) 做相邻对换，共 \(s + 1\) 次，得到

\[ \cdots\, i_1\, i_2\, \cdots\, i_s\, k\, j\, \cdots ; \]

再让 \(k\) 向左依次与 \(i_s, i_{s-1}, \dots, i_1\) 做相邻对换，共 \(s\) 次，得到

\[ \cdots\, k\, i_1\, i_2\, \cdots\, i_s\, j\, \cdots . \]

（注意最终结果正是"互换 \(j\) 与 \(k\)"，中间那些数的相对次序还原了。）整个操作共用了

\[ (s + 1) + s = 2s + 1 \]

次相邻对换。\(2s + 1\) 是奇数，而由第一步每次相邻对换都改变奇偶性，奇数次改变的总效果仍是改变奇偶性。故一般的对换也改变奇偶性。

为什么要绕这一圈

如果直接从定义出发去数一般对换前后的逆序数之差，要分四种情形讨论（\(i_t\) 与 \(j, k\) 的大小关系），写起来长且容易漏。而"相邻情形"只有一种情形要讨论，"一般情形"则通过分解成相邻对换化归过去。这种"先易后难、把一般拆成特殊"的写法，是本课程最常用的证明组织方式。

回到例子：\(2\,4\,6\,5\,7\,1\,3 \to 2\,7\,6\,5\,4\,1\,3\)

互换 \(4\) 与 \(7\) 后：

\[ \tau(2\,4\,6\,5\,7\,1\,3) = 10, \qquad \tau(2\,7\,6\,5\,4\,1\,3) = 15 . \]

用两种计数方法核对第二个排列：从数字角度看

\[ m_1 + m_2 + \cdots + m_7 = 5 + 0 + 4 + 3 + 2 + 1 + 0 = 15 ; \]

从位置角度看

\[ l_1 + l_2 + \cdots + l_7 = 1 + 5 + 4 + 3 + 2 + 0 + 0 = 15 . \]

两者一致，且 \(10\) 与 \(15\) 一偶一奇——定理得到验证。这里 \(4\) 与 \(7\) 之间隔着 \(6, 5\) 两个数，即 \(s = 2\)，按第二步需 \(2s + 1 = 5\) 次相邻对换。

工具：数学归纳法

下一步要用归纳法证明"任意排列都能通过一系列对换化成自然排列"，这里把归纳法复习一遍。它是本课程最重要的证明方法，没有之一。

原理（数学归纳法）

要证明一个关于正整数 \(n\) 的命题 \(P(n)\) 对一切 \(n \ge n_0\) 成立，只需做两件事：

  1. 初始条件：验证 \(P(n_0)\) 成立（有时要验证好几个起点，如 \(n_0\) 与 \(n_0 + 1\)）；
  2. 递推关系：由"\(P\) 对更小的数成立"推出"\(P(n)\) 成立"。

递推关系有两种常见写法，二者的差别只在假设的强弱：

  • 第一数学归纳法：假设 \(P(n-1)\) 成立，证明 \(P(n)\) 成立；
  • 第二数学归纳法：假设 \(P(m)\) 对一切 \(m < n\) 成立，证明 \(P(n)\) 成立。

第二归纳法的假设更强，所以有时更好用；但凡是能用第一归纳法证明的，用第二归纳法也能证明，两者没有本质差别。

归纳法的核心

归纳法的核心是把关于 \(n\) 的命题化归为关于更小数的命题。若在证明 \(P(n)\) 时根本没有用到任何更小的情形，那说明这个命题本来就不需要归纳法。抓住这一点，就知道该在哪里"往下走一步"。

例题（递推关系的两种写法）

设数列 \(\{a_n\}\) 满足

\[ a_n = a_{n-1} + a_{n-2} \quad (n \ge 3), \qquad a_1 = a_2 = 1 . \]

这样的数列由初始条件 \(a_1, a_2\) 和递推关系完全确定；计算 \(a_3 = 2\)、\(a_4 = 3\)、\(a_5 = 5\) 时，每一步都用到了前两项，属于第二归纳法（假设"对小于 \(n\) 的都成立"）的典型场景。

反之，若递推关系是 \(a_n = a_{n-1} + 1\)、\(a_1 = 1\)，则每一步只用前一项，第一归纳法就够了。看递推关系用到了前面几项，就知道该用哪一种。

命题：任意排列都可以化为自然排列

命题（化为自然排列）

任意一个 \(n\) 阶排列都可以通过一系列对换化为自然排列 \(1\,2\,\cdots\,n\)；并且所用对换的个数的奇偶性与原排列的奇偶性相同。

证明（仅证第一个结论）

对排列的阶数 \(n\) 用第一数学归纳法。

初始条件：\(n = 2\) 时，\(2\) 阶排列只有 \(12\) 与 \(21\)。\(12\) 已经是自然排列（做 \(0\) 次对换）；\(21\) 做一次对换即得 \(12\)。命题成立。

归纳步骤：设结论对所有 \(n - 1\) 阶排列成立，要证它对 \(n\) 阶排列 \(j_1 j_2 \cdots j_n\) 也成立。对最后一个数 \(j_n\) 分类：

情形 1：\(j_n = n\)。 此时 \(j_1 j_2 \cdots j_{n-1}\) 是 \(1, 2, \dots, n-1\) 的一个 \((n-1)\) 阶排列。由归纳假设，它可以经过一系列对换化为 \(1\,2\,\cdots\,(n-1)\)；把这些对换作用在原排列上，得到

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

即自然排列。

情形 2：\(j_n \ne n\)。 设 \(n\) 出现在第 \(k\) 位（\(1 \le k \le n-1\)），即 \(j_k = n\)。先做一次对换，把 \(j_k = n\) 与 \(j_n\) 互换，排列变成

\[ j_1 \cdots j_{n-1}\, n , \]

这已化归为情形 1。于是再按情形 1 的办法，用一系列对换把它化为自然排列。

故结论对 \(n\) 阶排列成立，由归纳法原理命题得证。

关于第二个结论。 由对换改变奇偶性，每做一次对换，奇偶性翻转一次。自然排列 \(1\,2\,\cdots\,n\) 的逆序数是 \(0\)，是偶排列。若从原排列出发经过 \(t\) 次对换到达自然排列，则奇偶性共翻转 \(t\) 次，从"偶"倒推回去，原排列的奇偶性由 \(t\) 决定：\(t\) 为偶数时原排列是偶排列，\(t\) 为奇数时是奇排列。也就是说，\(t\) 与原排列的奇偶性相同。

容易读错的一句话

第二个结论说的是"对换个数与原排列奇偶性相同"，不是"对换个数的奇偶性与逆序数相同"，更不是"对换个数等于逆序数"。例如

\[ 2\,4\,6\,5\,7\,1\,3 \longrightarrow 1\,2\,3\,4\,5\,6\,7 \]

可以只用 \(5\) 次对换完成，但它的逆序数是 \(10\)。两者只共享"奇偶性"这一个信息。

推论（任意两个排列可以互化）

任意两个 \(n\) 阶排列都可以通过一系列对换互相转化。

证明

设两个排列为 \(a\) 与 \(b\)。由上面的命题，\(a\) 可以经过一系列对换化为自然排列；而每次对换都是"再对自己做一次就还原"的操作，所以这一列对换反过来做，就能把自然排列化为 \(a\)。

同理，\(b\) 也可以经过一系列对换化为自然排列。于是

\[ a \;\longrightarrow\; \text{自然排列} \;\longrightarrow\; b \]

给出了一条从 \(a\) 到 \(b\) 的对换路线（先把 \(a\) 化到自然排列，再把自然排列化到 \(b\) 的逆过程）。故任意两个排列可以互化。

这个推论的价值

要直接证明"任意两个排列可以互化"，得分很多种情形讨论，写好几页也未必说清。而借用"自然排列"作为中转站，整个证明只有两句话。找一个合适的中间对象，让两段路都变成已知的路，这是数学里非常常用的手法。

易错点

三个常见的错

  1. 以为"对换个数的奇偶性"依赖于具体做法。 由定理，无论用哪一串对换，个数的奇偶性是确定的（等于排列的奇偶性）。但具体次数可以不同，例如把 \(21\) 化为 \(12\) 也可以做 \(3\) 次（多绕两步）。
  2. 把"相邻对换"与"对换"混为一谈。 定理对两者都成立，但证明时只对相邻情形直接验证；一般情形是靠分解处理的。
  3. 对换的对象写错。 \((p\ q)\) 记的是位置，而"互换 \(j\) 与 \(k\)"说的是数值；由于排列中数值不重复，两种说法等价，但计算时不要一会儿看位置、一会儿看数值。

参见