跳转至

奇排列与偶排列的个数

本页面回答对换与奇偶排列开头提出的问题：\(n\) 阶排列中奇排列与偶排列各有多少个？ 答案是各占一半，即各有 \(\dfrac{n!}{2}\) 个。

证明的工具是双射：只要在两个有限集之间建立一个双射，就能断定它们元素个数相等。这也是本课程第一次用"数个数"的方式（而不是逐个去数）比较两个集合。

前置知识
  • 对换与奇偶排列：对换的定义与"一次对换改变奇偶性"的定理
  • 映射、单射、满射、双射：本页"准备工作"一节从头交代
  • 集合中元素个数的记号 \(\#X\)（首页记号表）、划分

问题的提出

设 \(n \ge 2\)。由逆序数的定义，每个 \(n\) 阶排列的逆序数非奇即偶，所以每个排列要么是奇排列，要么是偶排列，二者必居其一。于是

\[ \#\{\text{奇排列}\} + \#\{\text{偶排列}\} = n! . \]

若还能知道两者相等，就得到各为 \(\dfrac{n!}{2}\)。直观上它们"应该一样多"，但"直观"不是证明——需要一套工具。

准备工作：用映射比较两个有限集的元素个数

定义（映射、单射、满射、双射）

设 \(X, Y\) 是集合。一个从 \(X\) 到 \(Y\) 的映射 \(\varphi: X \to Y\) 是指：对每个 \(x \in X\)，都指定了唯一的 \(y \in Y\) 与之对应，记作 \(y = \varphi(x)\)。

  • 若 \(x_1 \ne x_2\) 必有 \(\varphi(x_1) \ne \varphi(x_2)\)，即"不同的元素像不同"，称 \(\varphi\) 是单射；
  • 若对每个 \(y \in Y\) 都存在 \(x \in X\) 使 \(\varphi(x) = y\)，即"\(Y\) 中每个元素都被打到"，称 \(\varphi\) 是满射；
  • 若 \(\varphi\) 既是单射又是满射，称它是双射（也叫一一对应、可逆映射）。

命题（用映射比较元素个数）

设 \(X, Y\) 是有限集，\(\varphi: X \to Y\) 是映射。

  1. 若 \(\varphi\) 是单射，则 \(\#X \le \#Y\)；
  2. 若 \(\varphi\) 是满射，则 \(\#X \ge \#Y\)；
  3. 若 \(\varphi\) 是双射，则 \(\#X = \#Y\)。

证明

1. \(\varphi\) 是单射，说明 \(X\) 中不同的元素在 \(Y\) 中有不同的像。于是映射 \(x \mapsto \varphi(x)\) 把 \(X\) 与它在 \(Y\) 中的像集 \(\varphi(X)\) 一一对应，故 \(\#X = \#\varphi(X)\)。又 \(\varphi(X) \subseteq Y\)，所以 \(\#X = \#\varphi(X) \le \#Y\)。

2. \(\varphi\) 是满射，说明 \(Y\) 中每个元素都至少是 \(X\) 中一个元素的像，即 \(Y = \varphi(X)\)。把 \(X\) 按"像等于谁"分组，每组非空，组数恰为 \(\#Y\)；每组至少含 \(1\) 个元素，故 \(\#X \ge \#Y\)。

3. 由 1 得 \(\#X \le \#Y\)，由 2 得 \(\#X \ge \#Y\)，故 \(\#X = \#Y\)。

第 3 条才是我们真正要用的

第 1、2 条只是陪衬，实际做题几乎只用第 3 条：想证明两个有限集元素个数相等，就造一个双射。 这也是后面处理"两个集合一样大""两种东西一样多"这类命题的标准套路。

定理与证明

定理（奇排列与偶排列的个数相等）

设 \(n \ge 2\) 是正整数。则 \(n\) 阶奇排列与 \(n\) 阶偶排列的个数相等，均为

\[ \frac{n!}{2}. \]

证明

记号。 设

  • \(S_n\) 为所有 \(n\) 阶排列构成的集合，\(\#S_n = n!\)；
  • \(A_n\) 为所有 \(n\) 阶偶排列构成的集合；
  • \(B_n\) 为所有 \(n\) 阶奇排列构成的集合。

第一步：\(S_n\) 是 \(A_n\) 与 \(B_n\) 的不交并。 每个排列非奇即偶，且不能既是奇又是偶，所以 \(A_n \cap B_n = \varnothing\) 且 \(S_n = A_n \cup B_n\)。因此

\[ \#A_n + \#B_n = \#S_n = n! . \]

第二步：造一个从 \(A_n\) 到 \(B_n\) 的映射。 规定

\[ \varphi: A_n \to B_n, \qquad \varphi\big((i_1 i_2 \cdots i_n)\big) = (i_2 i_1 i_3 \cdots i_n), \]

即"把前两个位置上的数互换"。这一步是一次对换，所以由对换改变奇偶性，偶排列经过它变成奇排列，\(\varphi\) 确实落在 \(B_n\) 中，定义合理。

同样规定

\[ \psi: B_n \to A_n, \qquad \psi\big((j_1 j_2 \cdots j_n)\big) = (j_2 j_1 j_3 \cdots j_n). \]

第三步：\(\varphi\) 与 \(\psi\) 互逆。 对任意 \((i_1 i_2 \cdots i_n) \in A_n\)，

\[ \psi\big(\varphi(i_1 i_2 \cdots i_n)\big) = \psi(i_2 i_1 i_3 \cdots i_n) = (i_1 i_2 i_3 \cdots i_n), \]

因为"互换前两个位置"再做一次就还原了。同理 \(\varphi \circ \psi\) 也是恒等映射。故 \(\varphi\) 与 \(\psi\) 互逆，\(\varphi\) 是双射。

第四步：结论。 由准备工作的第 3 条，\(\#A_n = \#B_n\)。结合第一步，

\[ \#A_n = \#B_n = \frac{n!}{2}. \]

也可以直接验单射与满射

不想用"互逆 ⟹ 双射"这条路，也可以分别验证：

  • 单射：若 \(\varphi(i_1 i_2 \cdots i_n) = \varphi(i'_1 i'_2 \cdots i'_n)\)，即互换前两位后的排列相同，那么互换回去也相同，故 \((i_1 i_2 \cdots i_n) = (i'_1 i'_2 \cdots i'_n)\)；
  • 满射：任取 \((j_1 j_2 \cdots j_n) \in B_n\)，互换它的前两位得到 \((j_2 j_1 j_3 \cdots j_n) \in A_n\)，它的像正是 \((j_1 j_2 \cdots j_n)\)。

两条都成立，故 \(\varphi\) 是双射。两种写法等价，选顺手的即可。

为什么要求 \(n \ge 2\)

\(n = 1\) 时只有排列 \(1\)，它是偶排列，没有奇排列，\(\dfrac{1!}{2}\) 也不是整数。上面证明中"互换前两个位置"在 \(n = 1\) 时无从谈起，所以定理必须要求 \(n \ge 2\)。

\(n = 0\) 或规定 \(0! = 1\) 的情形同样要单独处理，本课程只讨论 \(n \ge 2\)。

这个证明的范式

把上面的证明抽出来看，它做的是三件事：

  1. 把要数的对象写成集合（\(A_n\)、\(B_n\)），把已知的计数写成方程（\(\#A_n + \#B_n = n!\)）；
  2. 在两个集合之间造一个映射，并验证它落在目标集合里（用的是刚证过的定理）；
  3. 验证这个映射是双射（通过"互逆"或"单射 + 满射"），从而得到两个集合一样大。

以后遇到"证明两类对象一样多""证明两个集合等势"的问题，都可以照这个范式走。本课程后面（例如矩阵的秩、线性空间的维数）会反复出现"造双射 / 造一一对应"的思想。

参见