排列组合：数清每一种可能
排队、抽签、设密码、组队参赛……这些日常小事背后，藏着一门叫“数一数有多少种可能”的学问。为什么 3 个人排队拍照会有 6 种站法，而从 3 个人里选 2 个当代表却只有 3 种选法？一个“顺序”之差，答案天差地别。这一课，我们就把“数数”这件事，数得明明白白。
两个计数原理：加法与乘法的分工
要解决排列组合问题，先要会计数。“一共有多少种可能？”这个问题的答案，全靠两台“发动机”：加法原理和乘法原理。它们看起来简单，却是后面一切公式的源头。
分类加法计数原理（加法原理，addition principle）：完成一件事，有 类互不干扰的办法。第 类有 种方法，第 类有 种方法……第 类有 种方法，那么完成这件事共有
例如从北京到上海，可以坐飞机（每天 5 个航班）、坐高铁（每天 8 个车次）或坐长途汽车（每天 3 个班次）。三类方式互不重叠，任选其一即可到达，所以共有 种出行选择。
完成一件事有 类办法，各类办法互不重叠——任选一类就能完成任务。总方法数等于各类方法数之和：。
分步乘法计数原理（乘法原理，multiplication principle）：完成一件事需要依次经过 个步骤。第 步有 种方法，第 步有 种方法……第 步有 种方法，那么完成这件事共有
比如搭配衣服：你有 3 件上衣和 2 条裤子，穿法必须“先选上衣、再选裤子”，两步缺一不可。上衣有 3 种选法，裤子有 2 种选法，于是共有 种搭配。下面这张树状图把 6 条路径全部画了出来——每条从“上衣”走到“裤子”的完整路线，就是一种搭配。
怎么区分加法还是乘法？ 看各方案之间的关系：是“或”——选了这个就不用选那个——就用加法；是“且”——每一步都必须完成——就用乘法。
类类相加，步步相乘。 问自己一句：“我只需要选一种方案，还是必须依次完成所有步骤？”
排列：顺序一变，就是新的结果
把元素排成一列时，同样的元素换个顺序就是不同的结果，这就是排列（permutation）。排队、密码、名次，都离不开排列。
定义：从 个不同元素中取出 （）个元素，按照一定的顺序排成一列，叫做从 个不同元素中取出 个元素的一个排列。所有这些排列的个数，叫做排列数，记作 。
公式怎么来的？ 想象有 个空位要依次填满。第 个空位有 种选择；填好后只剩 个元素，第 个空位有 种选择；第 个空位有 种……到第 个空位时还剩 种选择。用乘法原理一乘即得：
这里出现了阶乘（factorial）：，并约定 。特别地，当 时是全排列：。
3 个同学排队照相：第一个位置 3 人选，第二个 2 人选，第三个 1 人选，共 种站法。下面的动画把这 6 种排列逐一摆出来——注意，同样的三个人，换个位置就是全新的排法。
密码是排列思想的典型应用。用 0–9 这 10 个数字组成 4 位密码（每位可重复）：每位数码都有 10 种选择，共 种。若要求 4 个数码互不相同，才是排列数 。可见“能否重复”会大幅改变答案。
① 元素互不相同；② 取 个不重复；③ 按顺序排列。顺序一变，就算新的排列。
组合：只选不排，顺序无所谓
很多时候我们只关心“选了谁”，不关心“谁先谁后”。从 5 人中选 2 人当代表，{甲, 乙} 和 {乙, 甲} 是同一件事。这就是组合（combination）。
定义：从 个不同元素中取出 （）个元素组成一组，不考虑顺序，叫做从 个不同元素中取出 个元素的一个组合。所有组合的个数叫组合数，记作 。
关键区别：排列里“甲乙”与“乙甲”算两种，组合里算一种。所以对同一组 个元素，排列数比组合数多，多出来的倍数正是这 个元素内部的排列数 。
公式推导：从 个元素里取 个并排成一列，有 种。换个角度看：先“选一组”（ 种），再把这 个元素排顺序（ 种）。两步相乘应等于排列数，于是 ，移项得：
从 5 人中选 2 人： 种。下面的图把 10 种组合与 20 种排列并列展示：每一组无序对（如 {甲,乙}）对应 2 个有序对（甲乙、乙甲），恰好是 倍的关系。
握手问题：8 人聚会，每两人握一次手，共握几次？每次握手对应“从 8 人中选 2 人”，甲乙握手和乙甲握手是同一件事，与顺序无关，所以是 次。
① 元素互不相同；② 取 个不重复；③ 不排序。{甲,乙} 与 {乙,甲} 算同一种。
排列与组合的联系：一座桥，一把钥匙
排列与组合不是两套无关的公式，它们共用同一套乘法原理，只差一个“要不要排序”。
记住这座桥：。遇到计数题，先问自己：“选出来之后，还需要排顺序吗？”需要就用排列，不需要就用组合。
| 对比项 | 排列 | 组合 |
|---|---|---|
| 是否考虑顺序 | 考虑，顺序不同结果不同 | 不考虑，只看选了谁 |
| 典型场景 | 排队、密码、名次 | 选代表、握手、抽样 |
| 公式 | ||
| 关系 |
组合数有三个常用性质：
- （一个不选或全部选，都只有一种方式）；
- （选出 个，等价于留下 个）；
- （选或不选某个特定元素）。
第三条性质正是杨辉三角（Pascal's triangle）的递推规律：每个数等于它左上方与右上方两数之和。第 行第 个数就是 。试试下面交互图，点开每个格子看它的来历。
彩蛋：杨辉三角与二项式定理
把 连乘展开： 的系数 是杨辉三角第 2 行； 的系数 是第 3 行。二项式定理（binomial theorem） 说： 的展开系数正是第 行的组合数。
对称性质还很实用：计算 不必硬算，，一步到位。
综合演练：你学会数数了吗？
下面五道题覆盖了加法、乘法、排列、组合四类方法。先读题判断“类还是步”“排还是不排”，再作答。
“任取 1 本”意味着两类书是“或”的关系，取数学书或取语文书都能完成任务，用加法原理： 种。
“各取 1 本”是两步“且”的关系：先取数学书（4 种）再取语文书（3 种），用乘法原理： 种。
5 人全部参与排队，顺序不同就是不同的站法，是全排列： 种。
只选人不排顺序，{甲,乙,丙} 与 {丙,乙,甲} 是同一组，用组合： 种。
每位数字可以重复，所以每一位都有 10 种选择，用乘法原理：。若要求 4 位互不相同才是排列数 5040。
8 人聚会，每两人握一次手，一共握了多少次？先独立算一算，再点开核对。
每次握手对应“从 8 人中选 2 人”。甲乙握手与乙甲握手是同一件事，与顺序无关，用组合： 次。
回顾主线：计数靠两个原理——类类相加、步步相乘；取元素时，要排序用排列 ，不排序用组合 ；两者由 相连。下次遇到“有多少种可能”，先判断“加还是乘、排还是不排”，答案就水到渠成。