6.2 排列与组合
第 6.1 节用乘法计算多阶段选择。当选择不能重复时，乘法原理仍然成立，只是每个阶段的可选数量会减少。
同时还要判断：改变顺序是否产生新结果。这个区别把与分开。
假设把 n 个互不相同的对象排成一行。
- 选走一个对象后，第二个位置有 n−1 种；
由乘法原理，排列数为
n(n−1)(n−2)⋯2⋅1. 这个乘积称为 ：
n!=n(n−1)(n−2)⋯2⋅1. 例如，
4!=4⋅3⋅2⋅1=24. 规定
它表示空对象有一种空排列，也会让后续公式在边界情况下保持成立。
是对互不相同对象进行的有序安排。
集合 {A,B,C} 的六个排列为
ABC, ACB, BAC, BCA, CAB, CBA. ABC 与 BAC 不同，因为对象所处位置不同。
从 n 个不同对象中取出并排列 r 个，称为 。
第一个位置有 n 种选择，第二个有 n−1 种，第 r 个位置有
种。因此
P(n,r)=n(n−1)⋯(n−r+1). 用阶乘表示：
P(n,r)=(n−r)!n!. 分母会约掉没有使用的尾部：
(n−r)!n!=(n−r)!n(n−1)⋯(n−r+1)(n−r)!. 示例：领奖台位置
8 名选手争夺金、银、铜牌。同一人不能占两个位置，而且三种奖牌代表不同位置，所以
P(8,3)=8⋅7⋅6=336. 这里不能用 (38)，因为同样三个人以不同奖牌顺序出现，会产生不同结果。
假设五个人 A,B,C,D,E 排成一行，并要求 A 必须在第一个位置。第一阶段已经固定，剩下
种排列。
如果要求 A,B 必须相邻，可以暂时把二者视为一个块。排列单位为
[AB],C,D,E, 共有 4! 种排列。块内部还可以是 AB 或 BA，因此共有
4!⋅2!=48 种。
块方法成立，是因为每个有效排列都能唯一编码为：
1. 这个块与其他对象的排列；
2. 块内部的顺序。
如果一些对象无法区分，n! 会重复计数。
单词 有 5 个字母：
如果暂时把两个 L 标记为 L1,L2，交换标记不会改变可见单词。每个可见排列因 L 的标签被计算 2! 次，又因 E 的标签被计算 2! 次。
因此不同排列数为
2!2!5!=30. 一般地，若 n 个对象中各类型的重复数为
n1,n2,…,nk且n1+⋯+nk=n, 不同排列数为
n1!n2!⋯nk!n!. 把成员安排到角色敏感的位置，并实时切换限制：固定座位、相邻搭档、禁止位置和重复徽章。排列金库会比较原始阶段乘积与块编码，明确显示什么时候两个排列真的不同。
只选择一个子集，不给成员分配位置。
选择委员会成员 {A,B,C} 时，无论按
还是
的顺序选出，最终都是同一个委员会。
从 n 个不同对象中选择 r 个的方法数记作
读作“n 选 r”。
先计算 r 个对象的有序选择：
P(n,r)=(n−r)!n!. 每个无序的 r 元组恰好以
种顺序出现。为了合并这些重复顺序，需要相除：
(rn)=r!P(n,r)=r!(n−r)!n!. 不同地区使用的公式相同，但字母位置经常不同。本课程用 P(n,r) 表示有序选择，用 (rn) 表示无序选择。中国大陆教材常写 Anr 与 Cnr，总数 n 放在下标，选取数 r 放在上标；英文教材还常见 nPr、nCr 或 C(n,r)。
| 计数对象 | 本课程记号 | 中国教材常用记号 | 其他国际记号 |
|---|
| 有序、不重复 | P(n,r) | Anr | nPr |
| 无序、不重复 | (rn) | Cnr | nCr 或 C(n,r) |
因此
Anr=P(n,r)=(n−r)!n!,Cnr=(rn)=r!(n−r)!n!. 代入数字前要先确认定义：Cnr 与 (rn) 表示同一个计数，只是上下标的视觉位置不同。
示例：选择团队
从 8 人中选 3 人组成没有等级的团队：
(38)=3!5!8!=3⋅2⋅18⋅7⋅6=56. 如果三名成员随后分别担任队长、分析员和演示者，顺序重新出现：
(38)⋅3!=56⋅6=336=P(8,3). 选择零个对象有一种方法：
(0n)=1. 选择全部对象也有一种方法：
(nn)=1. 选择要保留的 r 个对象，等价于选择要排除的 n−r 个对象。取补集是一个双射，所以
(rn)=(n−rn). 例如，
(310)=(710). 左边选择包含的 3 人，右边选择排除的 7 人，二者都唯一决定同一划分。
问自己：
> 保留相同对象，只改变它们的顺序，会不会得到不同结果？
比较：
| 问题 | 顺序重要吗？ | 计数 |
|---|
| 从 n 人中颁发金、银、铜牌 | 是 | P(n,3) |
| 选择三名委员会成员 | 否 | (3n) |
| 选择三名成员，再指定一名主席 | 部分重要 | (3n)⋅3 |
| 制作长度为 3 且不重复的编码 | 是 | P(n,3) |
混合问题应拆分成阶段，而不是强行套用一个公式。
从名单中选出无序团队，再激活角色，观察每个团队展开成 r! 个有序副本。重复折叠舱会把成员相同的选择聚在一起，让“排列除以 r! 得到组合”成为可见过程。
“选择”不自动表示组合。关键要看最终结果是否记录位置、角色或先后顺序。
排列与组合给出可能性的精确数量。有些问题提出另一种要求：即使不知道具体安排，什么重复一定会发生？第 6.3 节将介绍鸽巢原理，仅凭数量就证明碰撞不可避免。
