跳转至

排列

本页面回顾中学学过的排列数与组合数，然后给出本节真正要用的概念——\(n\) 阶排列，以及与之配套的几个名词（排列的相等、自然排列、反序排列）。

理解这一页的关键是转换视角：中学关心的是"有多少种排法"（一个数），而本课程关心的是"具体排成哪一个数组"（一个对象）。行列式需要的正是后者。

前置知识
  • 阶乘：\(n! = 1 \cdot 2 \cdots n\)，并约定 \(0! = 1\)
  • 集合中元素个数的记号 \(\#X\)
  • 连加与连乘：\(\sum\) 与 \(\prod\) 的用法

引入：排列数与组合数

中学的组合部分有两类基本计数问题。为了后面叙述方便，先把记号统一。

定义（排列数与组合数）

设 \(n, k\) 是正整数且 \(k \le n\)。

  • 从 \(n\) 个不同元素中取出 \(k\) 个排成一列的种数叫排列数，中学记作 \(\mathrm{A}_n^k\)，本笔记记作

    \[ n (n-1) (n-2) \cdots (n-k+1) = \frac{n!}{(n-k)!}; \]

  • 从 \(n\) 个不同元素中取出 \(k\) 个组成一组（不计次序）的种数叫组合数，中学记作 \(\mathrm{C}_n^k\)，本笔记记作

    \[ \binom{n}{k} = \frac{\mathrm{A}_n^k}{k!} = \frac{n!}{k!\,(n-k)!}. \]

两者的差别只有一句话：排列要排队，组合不排队。组合数之所以要除以 \(k!\)，是因为同一组 \(k\) 个元素被排列数重复数了 \(k!\) 次——中学里常说"去除重复计数"，说的就是这件事。

选球模型：一眼看清哪种计数

组合里的各种情形都可以用"把 \(k\) 个球放进 \(n\) 个盒子"来复述。只要问清"球是否相同""每盒是否至多一个"，公式就确定了：

模型 球是否相同 每盒是否至多一个 种数
球不同，盒子不同，每盒至多一个 不相同 是 \(\mathrm{A}_n^k = \dfrac{n!}{(n-k)!}\)
球相同，盒子不同，每盒至多一个 相同 是 \(\binom{n}{k} = \dfrac{n!}{k!\,(n-k)!}\)
球不同，盒子不同，每盒不限个数 不相同 否 \(n^k\)

前两行只差"球是否相同"：球若彼此有别，选出 \(k\) 个盒子后还要决定哪个球进哪个盒（\(k!\) 种），于是排列数比组合数多一个因子 \(k!\)。第三行允许一个盒子放多个球，每个球独立地挑盒子，所以是 \(n\) 个选择的 \(k\) 次方——它既不是排列数也不是组合数，套公式前先看模型。

超纲（可跳过）

组合数学是一门独立学科。 中学学的排列组合只是它最浅的一层：把"球与盒子"的四种变形（球是否相同 × 盒子是否相同）加上"放回 / 不放回"，就得到四类经典计数；再往后还有容斥原理、递推与生成函数、组合设计、代数组合、组合数论等分支。本课程只在需要时使用初等的计数事实（例如"\(n\) 阶排列共有 \(n!\) 个"），不展开这门学科本身。

\(n\) 阶排列

从这一小节开始，我们关注的不是"有多少种排法"，而是"排出来的那个数组本身"。

定义（\(n\) 阶排列）

由 \(1, 2, \dots, n\) 组成的一个有序数组

\[ j_1 j_2 \cdots j_n \]

称为一个 \(n\) 阶排列，其中每个数恰好出现一次。

换句话说，\(j_1 j_2 \cdots j_n\) 就是一个 \(n\) 阶排列，当且仅当 \(j_1, j_2, \dots, j_n\) 两两不同且都取自 \(\{1, 2, \dots, n\}\)。

定义里的三句话各有分工，缺一不可：

  • "由 \(1, 2, \dots, n\) 组成"——限定了取值范围；
  • "每个数恰好出现一次"——排除了重复，也保证 \(n\) 个位置被 \(n\) 个不同的数填满；
  • "有序"——\(132\) 与 \(312\) 是不同的排列，位置是有意义的。

命题（\(n\) 阶排列的个数）

\(n\) 阶排列共有 \(n!\) 个。

证明

逐个位置来选：第 \(1\) 个位置可以放 \(1, 2, \dots, n\) 中的任意一个，有 \(n\) 种选法；选定后第 \(2\) 个位置不能再用这个数，有 \(n - 1\) 种选法；依次下去，最后一个位置只剩下 \(1\) 种选法。由乘法原理，总数为

\[ n (n-1) (n-2) \cdots 2 \cdot 1 = n!. \]

这正是排列数 \(\mathrm{A}_n^n\) 在 \(k = n\) 时的值，与上面的公式一致。

注意（记号本身不重要）

排列里的元素不一定非得是数。字母、符号、甚至全班同学都可以排成一列。例如 \(b\,a\,c\) 是集合 \(\{a, b, c\}\) 上的一个 \(3\) 阶排列。排列只关心"谁在第几位"这个次序信息，不关心被排列的对象是什么。

本课程里我们始终用 \(1, 2, \dots, n\)，因为行列式的行指标与列指标恰好是 \(1\) 到 \(n\) 的编号。当同时讨论多个排列时，常用 \(j_1 j_2 \cdots j_n\)、\(i_1 i_2 \cdots i_n\) 两组字母区分。

几个配套的名词

定义（排列的相等）

两个 \(n\) 阶排列 \(i_1 i_2 \cdots i_n\) 与 \(j_1 j_2 \cdots j_n\) 相等，当且仅当对应位置上的数都相同，即

\[ i_1 = j_1, \quad i_2 = j_2, \quad \dots, \quad i_n = j_n . \]

定义（自然排列与反序排列）

按自然顺序排成的排列

\[ 1\,2\,\cdots\,n \]

称为自然排列（也叫标准排列）；反过来排成的排列

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

称为反序排列。

课堂上也把反序排列口语化地叫"全排列"，这只是习惯说法；严格说"全排列"通常指"全部的 \(n\) 阶排列"，阅读时按上下文判断即可。

这两个排列是"最有序"与"最颠倒"的两端，后面计算逆序数时会反复用到：自然排列的逆序数最小（为 \(0\)），反序排列的逆序数最大（见逆序与逆序数）。

为什么行列式需要排列

回到本节的目的。二阶行列式的两项

\[ a_{11} a_{22} - a_{12} a_{21} \]

有什么共同点？每一项里两个元素的行指标 \(1, 2\) 互不相同，列指标也互不相同；换句话说，每一项都是从方阵中"每行取一个、每列取一个"取出来的。三阶行列式的六项同样如此。

于是"写出 \(n\) 阶行列式"这件事可以拆成两步：

  1. 先把取法说清楚。 每行取一个元素 \(a_{1 j_1}, a_{2 j_2}, \dots, a_{n j_n}\)，只要 \(j_1 j_2 \cdots j_n\) 是一个 \(n\) 阶排列，"每列取一个"就自动满足；
  2. 再给每种取法配一个正负号。 符号由这个乘积的"颠倒程度"决定，这正是下一节逆序数要解决的事。

顺便得到一个重要结论：\(n\) 阶行列式的项数等于 \(n\) 阶排列的个数，即 \(n!\)。这解释了为什么二阶、三阶行列式分别有 \(2\) 项和 \(6\) 项，也预告了四阶行列式为什么必须换一种定义方式（四个广义对角线只能给出 \(8\) 项，而 \(4! = 24\)）——详见 1.3 \(n\) 阶行列式。

例题

例题 1

写出所有的 \(3\) 阶排列。

解 按第一个位置的数分类，共 \(3! = 6\) 个：

\[ 123, \quad 132, \quad 213, \quad 231, \quad 312, \quad 321 . \]

其中 \(123\) 是自然排列，\(321\) 是反序排列。

例题 2

计算 \(\mathrm{A}_5^3\) 与 \(\binom{5}{3}\)，并说明两者的关系。

解

\[ \mathrm{A}_5^3 = 5 \cdot 4 \cdot 3 = 60, \qquad \binom{5}{3} = \frac{5 \cdot 4 \cdot 3}{3!} = \frac{60}{6} = 10 . \]

从 \(5\) 个不同的数中取 \(3\) 个排成一列有 \(60\) 种；若不计次序只要选出来，则同一组 \(3\) 个数被数了 \(3! = 6\) 次，故组合数为 \(60 / 6 = 10\)。

例题 3

在 \(4\) 阶排列中，以 \(1\) 开头、以 \(4\) 结尾的排列共有多少个？

解 首尾固定后，中间两个位置填入剩下的两个数 \(2, 3\)，有 \(2! = 2\) 种：

\[ 1234, \quad 1324 . \]

一般地，"固定 \(k\) 个位置"后剩下的 \((n-k)\) 个位置可由 \((n-k)!\) 种方式填满。

参见