- 能陈述排列与全排列的定义，说明“选取 + 排序”两个要素；
- 会用计数基本原理逐位填空，独立推导排列数公式 \(P(n,k)=n(n-1)\cdots(n-k+1)=n!/(n-k)!\)；
- 能解释 \(0!=1\) 这一约定的组合意义，并熟练计算阶乘与排列数；
- 能依据“是否允许重复”“次序是否重要”两个判别问题，判断实际问题应使用排列、乘法原理还是后续章节的工具；
- 体会阶乘的爆炸增长（\(20!\approx 2.4\times10^{18}\)），并能据此估计枚举计算的规模与整数溢出风险。
1. 什么是排列：次序就是信息
上一节的计数基本原理（乘法原理）解决的是“分阶段过程的结果总数”问题。本节把它应用到一类最基本、也最常见的计数对象上——按次序安排一组对象。赛跑要分出名次，颁奖台上的金、银、铜牌各归其主；书架上的书有左右之分；密码的每一位有先后位置。在这些情境里，“谁排在前、谁排在后”本身就是结果的一部分：同样三个人按不同顺序登上领奖台，是三个不同的结果。我们把这类计数问题统称为排列问题。
设 \(S\) 是含 \(n\) 个不同对象的集合。从 \(S\) 中任取 \(k\) 个对象（\(1\le k\le n\)）按照一定次序排成一列，称为从 \(n\) 个不同对象中取 \(k\) 个对象的一个排列(permutation)；当 \(k=n\) 时称为全排列(full permutation)。所有这样的排列的总个数称为排列数(number of permutations)，记作 \(P(n,k)\)（国内教材也常记作 \(A_n^k\)，Ross 原书记作 \(n!/(n-k)!\)）。
排列包含两个动作：先从 \(n\) 个对象中选取 \(k\) 个，再把它们排定次序(order)。定义隐含两条限制：对象两两不同；每个对象至多出现一次，即不允许重复选取。若允许重复（如电话号码各位数字可以相同），问题不属于此处的排列，应直接回到计数基本原理（见第 4 小节）。
先用最小的例子把概念看清楚：把字母 A、B、C 排成一列，一共能排出多少个不同的“单词”？图 1 的树形图(tree diagram)给出了完整答案——每条从根到叶的路径就是一个排列。
图 1 与 1.2 节的菜单树形图形似而“神”不同：菜单问题中每层的选择数固定不变（前菜 3 种、主菜 5 种）；这里第 1 层 3 个分支、第 2 层只剩 2 个、第 3 层只剩 1 个——对象一旦用过便从后续阶段中除去。关键在于：每一层的选择数只依赖层数（还剩多少对象可用），而不依赖之前具体选了谁，因此计数基本原理的条件依然满足，结果数就是各层分支数的连乘积。这正是下面定理的证明思路。
2. 排列数公式与阶乘
把图 1 的“三层树”推广到一般的 \(n\) 与 \(k\)，就得到本节的核心公式。
\[ P(n,k)=n(n-1)(n-2)\cdots(n-k+1)=\frac{n!}{(n-k)!},\qquad 1\le k\le n. \] 特别地，取 \(k=n\) 得全排列数 \(P(n,n)=n\,!\)。
\[ n! = n\times(n-1)\times(n-2)\times\cdots\times2\times1 \qquad (n=1,2,3,\ldots), \] 读作“\(n\) 阶乘”(\(n\) factorial)；并约定 \(0!=1\)。
约定 \(0!=1\) 并非任意的硬性规定，而是三条相互一致的理由：(i) 把 \(0\) 个对象排成一列恰有一种方式（“空排列”），故 \(P(n,0)=1\)，而公式给出 \(n!/n!=1\)，正要求 \(0!=1\)；(ii) 递推关系 \(n!=n\cdot(n-1)!\) 若对 \(n=1\) 也成立，即 \(1!=1\times0!\)，同样要求 \(0!=1\)；(iii) 下一节的组合数 \(\binom{n}{k}=n!/(k!(n-k)!)\) 在 \(k=0\) 与 \(k=n\) 处取值为 \(1\)，也依赖这一约定。
9 名选手参加百米赛跑，设前三名分别获得金、银、铜牌（不设并列）。领奖台上“人—奖牌”的搭配共有多少种可能？
把 5 本互不相同的书放到一个 5 层书架上，每层恰放一本，共有多少种放法？若书架只有 3 层（3 格），又有多少种？
某地固定电话号码为 7 位。若要求 7 位数字互不相同（首位允许为 0），共能编出多少个不同的号码？若还要求首位不为 0 呢？
3. 阶乘的爆炸增长
公式 \(P(n,n)=n!\) 形式上极其简单，数值上却增长惊人：每递增 1，阶乘至少翻倍，因为 \((n+1)!=(n+1)\cdot n!\ge 2\,n!\)。到 \(n=20\) 时，\(20!\approx 2.43\times10^{18}\)，已逼近 64 位整数所能表示的上限。图 2 用柱状图展示了 \(n=1,\ldots,10\) 时 \(n!\) 的量级——注意纵轴采用对数刻度(logarithmic scale)：柱高与 \(\lg(n!)\) 成正比，柱顶标注的是真实数值。即便在对数刻度下，柱高依然近乎匀速上扬，意味着真实数值呈指数式飙升。
下表给出若干具体的阶乘数值，供本节及后续各节查阅。
| \(n\) | \(n!\) | 直观参照 |
|---|---|---|
| 1 | 1 | 空无一物的对照：只有一种“排法” |
| 2 | 2 | — |
| 3 | 6 | 图 1 的三字母全排列 |
| 4 | 24 | — |
| 5 | 120 | 5 本书排满 5 格书架（例 2） |
| 6 | 720 | PENCIL 的字母全排列（练习 2） |
| 7 | 5 040 | — |
| 8 | 40 320 | — |
| 9 | 362 880 | — |
| 10 | 3 628 800 | 每秒枚举一种，穷举需约 42 天 |
| 13 | 6 227 020 800 | 已超出 32 位有符号整数上限 |
| 15 | 1 307 674 368 000 | — |
| 20 | 2 432 902 008 176 640 000 | \(\approx 2.43\times10^{18}\)，约为宇宙年龄的 56 倍（秒） |
三个换算可以帮助体会阶乘增长之快：(i) 若每秒枚举一种排列，穷举 \(10!=3\,628\,800\) 种需 \(3\,628\,800\) 秒 \(\approx 42\) 天；(ii) 同样速度穷举 \(20!\) 需约 \(2.43\times10^{18}\) 秒 \(\approx 7.7\times10^{10}\) 年（约 770 亿年），约为宇宙年龄（约 138 亿年）的 56 倍——穷举在计算上永远不可行，这正是需要计数公式的根本原因；(iii) 编程实现时须警惕整数溢出：\(13!\) 已超出 32 位有符号整数的上限（约 \(2.1\times10^9\)），\(21!\approx5.1\times10^{19}\) 超出 64 位的上限（约 \(9.2\times10^{18}\)），大阶乘运算应改用对数或斯特林(Stirling)近似来估计量级。
把 \(n\) 个两两不同的球放入 \(n\) 个两两不同的盒子，每个盒子里恰放一个球，共有多少种放法？
4. 何时使用排列：一个判别准则
面对一个实际计数问题，建议依次追问两个问题。问题一：允许重复吗？排列要求每个对象至多用一次。若允许重复选取（如密码各位字符可重复、电话号码各位数字可相同），应直接用计数基本原理得 \(n^k\)，那不是排列。问题二：次序重要吗？交换两个已选对象的位置，结果是否随之改变？若改变——名次、席位、出场先后、密码的字符位置——就是排列问题；若不改变——委员会的成员名单、一次握手的双方、分组名单——次序不携带信息，按排列计数会对同一结果重复计入 \(k!\) 次，正确的工具是 1.4 节的组合。
对比一组例子：“从 10 人中选 3 人分别担任班长、学习委员、文体委员”，三个职务各不相同，交换两人的职务得到不同的班委，故为排列：\(P(10,3)=10\times9\times8=720\)（见练习 1）；而“从 10 人中选 3 人组成委员会”，3 人不分次序、不分角色，应为组合：\(\binom{10}{3}=120\)。两数恰好相差 \(3!=6\) 倍——这正揭示了排列与组合的一般关系：排列数 = 组合数 \(\times k!\)，其完整讨论见 1.4 节。
(a) 不要一见到“安排”“选人”就套用 \(n!\)：先检验次序是否真的重要，否则会成倍多算。(b) 若对象本身有重复（如单词 LEVEL 含两个 L、两个 E），交换相同字母并不产生新的可区分排列，直接用 \(n!\) 会多算，其修正公式 \(n!/(n_1!n_2!\cdots n_r!)\) 将在 1.5 节多项式系数中给出（见练习 3 的预演）。(c) \(0!=1\) 是“空排列恰有一种方式”这一事实的体现，而非人为的硬性规定，它在例 3 的 \(10!/3!\)、定理 1 取 \(k=n\) 等处已反复发挥作用。
5. 本节小结
- 排列 = 选取 + 排序：从 \(n\) 个不同对象中取 \(k\) 个排成一列；对象互异且不许重复选取。
- 排列数公式：\(P(n,k)=n(n-1)\cdots(n-k+1)=\dfrac{n!}{(n-k)!}\)；全排列 \(P(n,n)=n!\)；约定 \(0!=1\)（空排列恰有一种）。
- 证明思路：逐位填空——第 \(i\) 位恰有 \(n-i+1\) 种选择，各阶段选择数不依赖前面的结果，计数基本原理连乘即得。
- 阶乘爆炸增长：\(10!\approx3.6\times10^6\)，\(20!\approx2.43\times10^{18}\)；穷举不可行，计算须防整数溢出。
- 判别准则：允许重复 \(\to n^k\)（乘法原理）；次序无关 \(\to\) 组合（1.4 节）；对象含重复 \(\to\) 多项式系数（1.5 节）。
练习
练习 1-3-1
某班要从 10 名候选人中选出班长、学习委员、文体委员各 1 人（任何人不得兼任），共有多少种选法？若 3 个职务改为“组成一个 3 人代表团”（不分角色），又有多少种？
答案与提示职务两两不同，交换两人职务得到不同班委，是排列：\(P(10,3)=10\times9\times8=720\)。代表团不分次序，是组合：\(\binom{10}{3}=120\)（1.4 节），恰为前者的 \(1/3!\)。此题对比正是第 4 小节判别准则的直接应用。
练习 1-3-2
英文单词 PENCIL 的 6 个字母互不相同。(a) 6 个字母的全排列共有多少个？ (b) 任取其中 4 个字母排成一列，共有多少个？
答案与提示(a) \(6!=720\)。(b) \(P(6,4)=6\times5\times4\times3=360\)，即 \(6!/(6-4)!=720/2=360\)。注意“字母互不相同”是使用排列公式的前提——这正是下一题的反面。
练习 1-3-3
单词 LEVEL 由 L、L、E、E、V 五个字母组成。它的 5 个“字母”共有 \(5!=120\) 个排列吗？
答案与提示不是。两个 L 互换位置、两个 E 互换位置都不产生新的可区分排列，因此 \(120\) 中每一“真正不同的排法”被数了 \(2!\times2!=4\) 遍，实际只有 \(5!/(2!\,2!)=120/4=30\) 种。一般地，\(n\) 个对象中有重复（第 \(i\) 种出现 \(n_i\) 次）时，排列数为 \(n!/(n_1!\,n_2!\cdots n_r!)\)，即 1.5 节的多项式系数——本题为那一节做了预告。
练习 1-3-4
证明恒等式：\(1\cdot1!+2\cdot2!+\cdots+n\cdot n!=(n+1)!-1\)。
答案与提示利用裂项 \(k\cdot k!=(k+1-1)\,k!=(k+1)!-k!\)，求和时相邻项依次相消（telescoping sum，裂项相消）：\(\sum_{k=1}^{n}\big[(k+1)!-k!\big]=(n+1)!-1!\)。验证 \(n=3\)：\(1+4+18=23=4!-1\)。此恒等式也说明“前 \(n\) 项之和总比下一个阶乘少 1”，可视为阶乘增长的一种累积刻画。