跳转至

1.2 排列

本节是第一章里承上启下的一节。1.1 说清了"数"的范围，但只有数还不够：要写出 \(n\) 阶行列式的定义，必须先能把"选取哪些元素相乘"这件事说清楚，而这件事恰好就是"排列"。

一句话概括本节的作用：\(n\) 阶行列式的每一项都是"不同行不同列"的 \(n\) 个元素的乘积，而"不同行不同列"的取法正好由两个 \(n\) 阶排列描述。所以本节先建立排列的语言（排列、逆序数、对换、奇偶性），1.3 才可能把 \(n\) 阶行列式定义出来。

前置知识
  • 导论：集合与卡氏积、关系与等价类（特别是划分）、连加与连乘记号
  • 中学的排列数与组合数（本节会快速回顾，并给出记号上的统一）
  • 数学归纳法（本节在对换那一页会用到，那里有复习）

本节页面

页面 内容 定位
排列 排列数与组合数的回顾、\(n\) 阶排列及其相关概念 建立语言
逆序与逆序数 逆序、逆序数、两种科学的计数方法、最大逆序数 本节重点
对换与奇偶排列 对换、奇排列与偶排列、对换改变奇偶性 本节核心定理
奇排列与偶排列的个数 用双射证明奇、偶排列各占一半 定理的直接应用
数学建模：数字华容道 把拼图游戏翻译成排列问题，用奇偶性判定无解 建模示范
例题与练习 课堂例题与自拟练习，解答默认折叠 检验掌握程度

阅读顺序

  1. 先读排列与逆序与逆序数。 这两页给出本节的全部记号：\(n\) 阶排列 \(i_1 i_2 \cdots i_n\) 与它的逆序数 \(\tau(i_1 i_2 \cdots i_n)\)。逆序数的两种计数方法是这一页真正要交出去的东西——后面写行列式的一般项时，靠的就是它。
  2. 再读对换与奇偶排列。 "对换改变奇偶性"这条定理的证明是一次方法论演示：先把一般情形化归为相邻的特殊情形。这个"从特殊到一般"的手法在本课程后面会反复出现。
  3. 然后读奇排列与偶排列的个数与数学建模：数字华容道。 前者示范"用双射数个数"，后者示范"把现实问题翻译成数学问题"。
  4. 最后做例题与练习。 逆序数必须动手算，看一眼是学不会的。

本节要掌握到什么程度

  • 能写出 \(n\) 阶排列的定义，说清"由 \(1\) 到 \(n\) 组成""有序""每个数恰好出现一次"这三句话各自的作用；
  • 能对任意给定的排列熟练计算逆序数，并说明自己用的是哪种计数方法；
  • 能说清两种计数方法为什么不重不漏，并指出这一步用到了划分的哪条性质；
  • 能复述"对换改变奇偶性"的证明，并说清"一般情形为什么可以化归为相邻情形"；
  • 能写出"奇排列与偶排列各有 \(\dfrac{n!}{2}\) 个"的证明，并指出双射是什么；
  • 能用排列的奇偶性解释数字华容道中"只差最后一步"的局面为什么无解。

记号上的一个统一

中学把"从 \(n\) 个不同元素中取出 \(k\) 个排成一列"的种数记作 \(\mathrm{A}_n^k\)，把组合数记作 \(\mathrm{C}_n^k\)。本节统一改用国际通用的写法 \(n!\)、\(\binom{n}{k}\)，两种写法在正文里都会出现一次，之后只用后者。

参见