Hunt Bao

书籍《单页Web应用》译者，微信公众号《前端人生》作者

9 分钟阅读

在正式介绍排列组合之前，我们先来看看一些基本的计数法则。

乘积法则

乘积法则：如果一个实验包含 $n$ 个步骤，第一步有 $n_1$ 种可能，第二步有 $n_2$ 种可能，依此类推，第 $n$ 步有 $n_n$ 种可能，那么整个实验有 $n_1 \times n_2 \times \cdots \times n_n$ 种可能。

举例：一个人有 3 件上衣、2 条裤子、2 双鞋子，那么他有 $3 \times 2 \times 2 = 12$ 种穿法。

求和法则

求和法则：如果一个实验可以分解为 $n$ 种互斥的情况（任务不能同时完成），第一种情况有 $n_1$ 种可能，第二种情况有 $n_2$ 种可能，依此类推，第 $n$ 种情况有 $n_n$ 种可能，那么整个实验有 $n_1 + n_2 + \cdots + n_n$ 种可能。

举例：假定要选一位数学学院的老师或者数学专业的学生作为校委会的代表，数学学院有 10 位老师和 20 位学生，那么这个代表有 $10 + 20 = 30$ 种可能。

减法法则

减法法则：如果一个实验或者可以通过 $n_1$ 种方法完成，或者可以通过 $n_2$ 种另外一种方法完成，那么这个实验有 $n_1 + n_2$ 减去两类方法中相同的的方法。

减法法则也称为容斥原理。

举例：以 1 开始或者以 00 结束的 8 位二进制数有多少个？

  1. 以 1 开始的 8 位二进制数有 $2^7 = 128$ 种，这是由乘法法则得到的，因为第一位是 1，所以有 1 种可能，后面 7 位每一位都有 2 种可能。
  2. 以 00 结束的 8 位二进制数有 $2^6 = 64$ 种，这也是由乘法法则得到的，因为最后两位是 00，所以有 1 种可能，前面 6 位每一位都有 2 种可能。
  3. 以 1 开始且以 00 结束的 8 位二进制数有 $2^5 = 32$ 种，这也是由乘法法则得到的，因为第一位是 1，最后两位是 00，所以有 1 种可能，中间 5 位每一位都有 2 种可能。

其中，第 3 种情形，1 和 2 都包括了，重复算了一次，所以这个问题的答案是 $2^7 + 2^6 - 2^5 = 160$。

除法法则

除法法则：如果一个实验能由一个可以用 $n$ 种方式完成的过程实现，而对于每种完成任务的方式 $w$，在 $n$ 种方式中正好有 $d$ 种与之对应，那么完成这个实验的方法数为 $n/d$。

举例：假设在牧场中有一个计数奶牛腿数的系统。假设这个系统统计出该牧场的奶牛共有 572 条退，则牧场中的奶牛数是多少？假设每只奶牛有 4 条腿，而且没有其他动物。

这个问题可以通过除法法则解决。每只奶牛有 4 条腿，所以 572 条腿对应于 $572/4 = 143$ 只奶牛。

鸽巢原理

鸽巢原理：如果 $n$ 个物品被放入 $m$ 个箱子，其中 $n > m$，那么至少有一个箱子包含两个或者两个以上的物品。

鸽巢原理也叫做狄利克雷抽屉原理。

举例：假设有 13 个人，每个人的生日都在 1 月到 12 月之间，那么至少有两个人的生日在同一个月。

广义鸽巢原理：如果 $n$ 个物品被放入 $m$ 个箱子，其中 $n > km$，那么至少有一个箱子包含了至少 $k+1$ 个物品。

举例：在 100 个人中，至少有 $ 100 / 12 = 9$ 个人的生日在同一个月。

下面开始介绍排列和组合。

排列

排列是指从 $n$ 个不同的元素中取出 $r$ 个元素，按照一定的顺序排列，这个排列的个数称为排列数，记作 $P(n, r)$，称为一个 $n$ 元集的 $r$ 排列。

排列数的计算公式为：

$P(n, r) = n(n-1)(n-2) \cdots (n-r+1) = \frac{n!}{(n-r)!}$

注意，只要 $n$ 是非负整数，则 $p(n, 0) = 1$， 因为恰好有一种方法来排列 0 个元素，也就是说，恰好有一个排列中没有元素，即空排列。

举例1：从 5 个学生中选出 3 个学生站成一行照相，有多少种选择方法？让 5 个学生站成一行照相，有多少种排列方法？

首先，注意选择学生时的次序是有限制的。从 5 个学生中选择第一个学生站在一行的第一个位置有 5 种选择，一旦这个学生被选定后，剩下的 4 个学生中选择一个站在第二个位置有 4 种选择，最后一个学生站在第三个位置有 3 种选择。所以，根据乘积法则，选择 3 个学生站成一行的照相有 $5 \times 4 \times 3 = 60$ 种选择方法。

同理，5 个学生站成一行的照相有 $5 \times 4 \times 3 \times 2 \times 1 = 120$ 种排列方法。

举例2：在进人竞赛的100个不同的人中有多少种方法选出一个一等奖得主、一个二等奖得主和一个三等奖得主?

不管哪个人得哪个奖，选取 3 个得奖人的方法数是从 100 个元素的集合中有序选择 3 个元素的方法数，即 100 个元素的集合的3排列数。因此，答案是：

$P(100, 3) = 100 \times 99 \times 98 = 970200$

举例3：字母 ABCDEFGH 有多少种排列包含串 ABC?

由于字母 ABC 必须成组出现，我们可以通过找 6 个对象，即组 ABC 和单个字母 D、E、F、G 和 H 的排列数得到答案。由于这 6 个对象可以按任何次序出现，因此，存在 $P(6, 6) = 6! = 720$ 种 ABCDEFGH 字母的排列， 其中 ABC 成组出现。

组合

组合是指从 $n$ 个不同的元素中取出 $r$ 个元素，不考虑元素的顺序，这个组合的个数称为组合数，记作 $C(n, r)$，称为一个 $n$ 元集的 $r$ 组合。

集合元素的一个 $r$ 组合是从这个集合无序选取的 $r$ 个元素。于是，简单地说，一个 $r$ 组合是这个集合的一个 $r$ 个元素的子集。

组合数的计算公式为：

$C(n, r) = \frac{P(n, r)}{r!} = \frac{n!}{r!(n-r)!}$

举例1：从 4 个学生中选出 3 个学生组成一个委员会，有多少种选择方法?

为了回答这个问题，只需从含有 4 个学生的集合中找到具有 3 个元素的子集的个数。选择 3 个学生等价于从 4 个学生中选出 1 个人离开这个集合，我们知道，在含有 4 个学生的集合中包含 1 个人的子集有 4 个，每一个子集对应 4 个学生的 1 个。这就意味着有 4 种方法选择 3 个学生组成一个委员会，这与学生的次序是无关的。使用组合公式，我们可以得到： $C(4, 3) = \frac{4!}{3!(4-3)!} = 4$。

举例2：从一副 52 张标准扑克牌中选出 5 张，共有多少种不同方法？从一副 52 张标准扑克牌中选出 47 张，又有多少种不同方法？

对于第一个问题，我们可以使用组合公式，得到：

$C(52, 5) = \frac{52!}{5!(52-5)!} = 2598960$

对于第二个问题，我们可以使用组合公式，得到：

$C(52, 47) = \frac{52!}{47!(52-47)!} = 2598960$

不难发现，这两个问题的答案是一样的，这是因为从 52 张牌中选出 5 张和从 52 张牌中选出 47 张是等价的，$C(52, 5) = C(52, 47)$，更为一般的推论是 $C(n, r) = C(n, n-r)$。

排列和组合的区别

排列和组合的区别在于是否考虑元素的顺序。排列是有序的，组合是无序的。

举例：假设有 3 个学生，分别是 A、B 和 C，从这 3 个学生中选出 2 个学生，有多少种选择方法？

  1. 如果考虑学生的顺序，则有 $P(3, 2) = 3 \times 2 = 6$ 种选择方法，分别是 AB、AC、BA、BC、CA 和 CB。
  2. 如果不考虑学生的顺序，则有 $C(3, 2) = 3$ 种选择方法，分别是 AB、AC 和 BC。

生日问题

生日问题是一个经典的概率问题，问题描述如下：在一个班级里，至少要有多少人，才能使得他们中有两个人生日相同的概率超过 50%？

这个问题可以通过排列和组合的知识来解决。假设有 $n$ 个人，那么他们中没有人生日相同的概率为：

$P(n) = \frac{365}{365} \times \frac{364}{365} \times \cdots \times \frac{365-n+1}{365}$

那么他们中至少有两个人生日相同的概率为：

$1 - P(n)$

我们可以通过计算 $1 - P(n)$ 的值来找到满足条件的 $n$ 的值。回到最初的问题，我们要找到满足 $1 - P(n) > 0.5$ 的最小的 $n$ 的值，这个问题可以通过计算机程序来解决：

function birthdayProblem() {
  const p = 1 / 365;
  let n = 1;
  let probability = 1;
  while (probability > 0.5) {
    probability *= 1 - n * p;
    n++;
  }
  return n;
}

console.log(birthdayProblem()); // 输出 23

所以在一个有 23 个人的班级里，他们中至少有两个人生日相同的概率就会超过 50%。这问题有时也称生日悖论。

特定人数对应的2个人生日一样的概率图如下：

birthday-problem

参考资料

  1. 本文的很多内容和示例都来自于《离散数学及其应用》第 8 版，作者 Kenneth H. Rosen。
  2. 生日问题

留下评论

猜您还喜欢