核心问题:顺序重要吗?
排列与组合都是在计算从 n 个不同物品中选出 r 个物品的方式数,但它们回答的是两个不同的问题。排列计算的是选出并排列 r 个物品的方式数,因此包含相同物品但顺序不同的两种选取会被算作两个不同的结果。组合只计算选出 r 个物品的方式数,因此包含相同物品的两种选取,无论选取顺序如何,都只算作一个结果。
判断该用哪一个的简单方法是:设想两种选取方式使用了完全相同的物品,只是排列或列出的顺序不同。如果这两种选取代表着真正不同的现实结果——不同的名次排名、不同的密码、比赛中不同的完赛顺序——那么顺序重要,应使用排列。如果这两种选取代表的是同一个现实结果——同一个委员会、同一手牌、同一组彩票号码——那么顺序不重要,应使用组合。
公式:nPr 与 nCr,及一个经过验证的例子
从 n 个不同物品中选出 r 个的排列数为 nPr = n! / (n − r)!,组合数为 nCr = n! / [r! (n − r)!]——组合公式就是排列公式再除以 r!,因为除以 r! 去掉了每一组相同物品在排列计数中被当作不同结果的 r! 种排列方式。
实例演算:从 7 个物品中选出 3 个。排列数:7P3 = 7! / (7−3)! = 7 × 6 × 5 = 210。组合数:7C3 = 7! / (3! × 4!) = (7 × 6 × 5) / (3 × 2 × 1) = 210 / 6 = 35。组合数恰好等于排列数除以 3! = 6,验证了 nCr = nPr / r! 这一关系。
| 数量 | 公式 | n=7, r=3 时的取值 |
|---|---|---|
| 排列(顺序重要) | nPr = n! / (n − r)! | 7P3 = 7 × 6 × 5 = 210 |
| 组合(顺序不重要) | nCr = n! / [r!(n − r)!] | 7C3 = 210 / 3! = 35 |
允许重复 vs 不允许重复
以上两个公式都假设 n 个物品中的每一个最多只能被选取一次——即不放回抽样。当物品可以被重复使用时(即放回抽样,又称有放回抽样),计数公式就会发生变化。允许重复的排列数很简单,只需将 n 取 r 次方即可,因为每个位置都独立地拥有全部 n 种选择,与之前选了什么无关:n^r。
允许重复的组合数则采用另一个公式,C(n + r − 1, r),它计算的是从 n 种类型中选出 r 个、允许重复且顺序仍然不重要的方式数——这种情形较少用到,但会出现在诸如从 n 种口味中选出若干勺冰淇淋、且同一种口味可以被多次选中的场景中。
| 情形 | 公式 | 典型例子 |
|---|---|---|
| 排列,不重复 | n! / (n − r)! | 从 7 名决赛选手中排出前 3 名 |
| 排列,可重复 | n^r | 数字可重复的 4 位密码 |
| 组合,不重复 | n! / [r!(n − r)!] | 选出 6 个彩票号码 |
| 组合,可重复 | (n + r − 1)! / [r!(n − 1)!] | 从 5 种冰淇淋口味中选 3 勺,允许重复 |
实例演算:一个密码与一张彩票
一个 4 位密码,每一位可以是 0 到 9 中的任意数字,且数字可以重复(这是银行密码通常采用的规则),就是一个允许重复的排列例子:顺序重要(1234 与 4321 是不同的密码),而且允许重复,由此得到 10^4 = 10,000 种可能的密码。如果不允许数字重复,那么这个数字就会降为不允许重复的排列值,10P4 = 10 × 9 × 8 × 7 = 5,040——可能性更少,因为每用掉一个数字,剩下的位置就少一个可选项。
一种经典的彩票形式是从 49 个号码的号码池中抽出 6 个,号码不重复,而且抽出的顺序对中奖与否没有影响,这就是一个不允许重复的组合例子:C(49, 6) = 49! / (6! × 43!) = 13,983,816。这个巨大的数字正是这类彩票被称为「长赔率」游戏的原因——当 n 相对于 r 增大时,组合数会增长得非常快,因为它计算的是从一个很大的号码池中选出的无序组合,而不是从一个较小的固定集合中选出的有序排列。
快速记住该用哪个公式的方法
「排列」(Permutation)与「位置」(Position)在英文中都以 P 开头,一个有用的记忆方法是:排列关心的是位置——每个物品落在序列中的哪个位置。「组合」(Combination)描述的则是一个合并起来的群体,就像一个袋子或一个委员会的内容物,只有成员是谁才重要,选入的先后顺序并不重要。
密码、PIN 码、比赛名次,以及任何座位或日程安排问题,都是排列问题,因为交换顺序会改变结果。扑克牌手牌、彩票号码组合、委员会成员构成,以及任何无序群体的选取,都是组合问题,因为只有成员是谁才重要,而不是选取他们的先后顺序。
常见问题
排列与组合有什么区别?
排列计算的是顺序重要的排法数量,因此把相同的物品换一种顺序排列,就算作不同的结果。组合计算的是顺序不重要的选法数量,因此相同的物品无论以何种顺序出现,都只算作一个结果。两者都是从同一组 n 个物品中选出 r 个,但在相同的 n 和 r 下,排列数总是大于或等于对应的组合数。
7P3 是多少,怎么计算?
7P3 等于 210,即从 7 个不同物品中选出并排列 3 个、且顺序重要时的方式数。计算方法是 7P3 = 7! / (7 − 3)! = 7 × 6 × 5 = 210,把 7! 中最大的三个因子相乘,因为其余较小的因子会与分母 (7−3)! 相互抵消。
7C3 是多少,怎么计算?
7C3 等于 35,即从 7 个不同物品中选出 3 个、且顺序不重要时的方式数。计算方法是 7C3 = 7! / (3! × 4!) = (7 × 6 × 5) / (3 × 2 × 1) = 210 / 6 = 35——恰好是排列数 7P3 = 210 除以 3!(即每组 3 个物品可能的重新排列方式数),因为组合把同一组物品的所有排列方式都合并成了一个结果。
为什么密码用排列,而彩票用组合?
密码把 1234 与 4321 视为不同的代码,顺序会改变结果,这是排列的情形——对于典型的允许重复的 4 位密码,共有 10^4 = 10,000 种可能。彩票中奖只取决于抽出了哪些号码,而不取决于开出的先后顺序,因此两次开出相同号码但顺序不同的结果被视为同一个中奖结果,这是组合的情形——对于从 49 个号码中选 6 个的形式,共有 C(49,6) = 13,983,816 种可能的号码组合。
排列或组合公式中「允许重复」是什么意思?
它指的是同一个物品在同一个结果中可以被选中不止一次。允许重复的排列使用 n^r(r 个位置中每一个都独立拥有全部 n 种选择);允许重复的组合则使用 (n + r − 1)! / [r!(n − 1)!]。而在不允许重复的情形下,每个物品最多只能使用一次,这正是标准的 nPr 和 nCr 公式所假设的前提。
参考文献
- NIST Digital Library of Mathematical Functions (DLMF), §26 Combinatorial Analysis. dlmf.nist.gov.
- Rosen KH. Discrete Mathematics and Its Applications. 8th ed. McGraw-Hill, 2018 (permutations, combinations, and counting with repetition).
- Ross SM. A First Course in Probability. Pearson (combinatorial counting methods).
- Weisstein EW. "Permutation" and "Combination." MathWorld — A Wolfram Web Resource. mathworld.wolfram.com.