• Counting

CS 70 计数与组合数学精校笔记 (Note 12)

1. 序列计数 (Counting Sequences) —— 有序、不放回

1.1 核心场景

从含有 $n$ 个元素的集合 $S = \{1, 2, \dots, n\}$ 中，不放回（Without replacement）地依次抽取 $k$ ($k \le n$) 个元素组成一个序列。

• 特点：元素不能重复；顺序重要。例如，先抽到 $1$ 再抽到 $2$（结果为 $(1, 2)$）与先抽到 $2$ 再抽到 $1$（结果为 $(2, 1)$）被视为不同的结果。

1.2 计数原理：第一计数原理 (Product Rule)

第一计数原理（乘法原理）：如果一个对象的构建可以分为 $k$ 步连续的选择。第一步有 $n_1$ 种选择；无论第一步如何选择，第二步都有 $n_2$ 种选择；……；无论前 $k-1$ 步如何选择，第 $k$ 步都有 $n_k$ 种选择。那么，构建该对象的总方法数为：

$\text{总数} = n_1 \times n_2 \times n_3 \times \dots \times n_k$

1.3 实例应用：扑克牌序列

• 问题：从 52 张牌中，不放回地依次抽取 5 张牌，能产生多少种不同的有序序列？

• 解析：

  • 第 1 张牌：有 52 种选择；

  • 第 2 张牌：剩余 51 种选择；

  • 第 3 张牌：剩余 50 种选择；

  • 第 4 张牌：剩余 49 种选择；

  • 第 5 张牌：剩余 48 种选择。

  • 根据第一计数原理，总序列数为：

    $52 \times 51 \times 50 \times 49 \times 48 = \frac{52!}{(52-5)!} = \frac{52!}{47!} \text{ 种}$

2. 集合计数 (Counting Sets) —— 无序、不放回

2.1 核心场景

从集合 $S = \{1, 2, \dots, n\}$ 中抽取 $k$ 个不同的元素，但不关心抽取的顺序。

• 特点：元素不能重复；顺序不重要。我们关心的不再是序列，而是抽出来的元素构成的子集（例如集合 $\{1, 2\}$ 和 $\{2, 1\}$ 是同一个集合）。

2.2 实例应用：扑克牌手牌

• 问题：从 52 张牌中，抽取 5 张作为一手牌（不计顺序），一共有多少种可能的组合（集合）？

• 解析（使用“分箱法”）：

  1. 假设顺序重要，我们一共有 $\frac{52!}{47!}$ 个不同的有序序列。

  2. 我们把每一个“无序的 5 张牌集合”看作一个盒子（Bin）。

  3. 每一个盒子对应的无序集合，如果加上顺序，可以排成 $5!$ 种不同的有序序列。

  4. 也就是说，每 $5!$ 个有序序列，都对应唯一一个无序盒子。这是一个 $5!$ 对 $1$（$m$-to-$1$）的映射。

  5. 因此，无序盒子的总数（集合数）为：

     $\text{手牌组合数} = \frac{\text{有序序列数}}{\text{每个集合的排列数}} = \frac{52!}{47! \times 5!}$

2.3 核心工具：二项式系数 (Binomial Coefficient)

这种“从 $n$ 个不同元素中选出 $k$ 个元素且不计顺序”的方法数极为常用，记作 $\binom{n}{k}$，读作 “n choose k”（$n$ 选 $k$）：

$\binom{n}{k} = \frac{n!}{(n-k)! k!}$

2.4 第二计数原理 (Division Rule)

第二计数原理（除法原理）：设 $A$ 为所有有序对象的集合，$B$ 为所有无序对象的集合。如果存在一个从 $A$ 到 $B$ 的 $m$ 对 $1$ （$m$-to-$1$）的映射函数 $f$（即每一个无序对象都精确对应 $m$ 个不同的有序排列），则无序对象的总数为：

$|B| = \frac{|A|}{m}$

3. 有放回抽样 (Sampling with Replacement)

3.1 顺序重要（有放回，有顺序）

• 场景：每次抽取一个元素后，将它放回集合中，下一次还可以重复抽取，且抽取顺序会影响结果。

• 计算：每一次抽取都有完整的 $n$ 种可能。如果要抽取 $k$ 次，根据第一计数原理，总方法数为：

  $\text{总数} = \underbrace{n \times n \times \dots \times n}_{k \text{ 次}} = n^k$

• 典型实例：

  • 硬币投掷：投掷一枚硬币 $k$ 次。每次有 2 种结果（正面/反面），总结果数为 $2^k$。
  • 掷骰子：连续掷 2 次 6 面骰子，总结果数为 $6^2 = 36$ 种。

3.2 顺序不重要（有放回，无顺序）

• 场景：元素可以重复选择（有放回），但我们最终只关心每种元素被选了多少次，不关心选择的先后顺序。

思考：为什么此时第二计数原理（除法原理）失效了？

• 原因：因为不同的无序结果对应的有序排列数是不等的（即不存在一个统一的常数 $m$）。
• 举例：假设从水果（苹果 A, 香蕉 B）里选 5 个。
  • 若无序结果是“5 个香蕉 $\{B, B, B, B, B\}$”，其对应的有序序列只有 $1$ 种：$(B,B,B,B,B)$。
  • 若无序结果是“4 个香蕉，1 个苹果 $\{A, B, B, B, B\}$”，其对应的有序序列有 $\binom{5}{1} = 5$ 种（苹果可以在 5 个位置中的任意一个）。
  • 由于不同盒子的“装载量”不同，我们无法使用简单的除法（除以固定的 $m$）来求解。

救星：插板法 / 隔板法 (Stars and Bars)

我们将这个复杂的分配问题转化为二进制字符串（由小球 0 和隔板 1 组成）的排布问题。

• 例题：现在有无限量的苹果、香蕉和橙子（$n=3$ 种水果）。你想要选择 5 个水果（$k=5$）来制作一份水果沙拉。一共有多少种不同的选择方法？

• 解析：

  1. 设定 $3$ 个盒子（分别装苹果、香蕉、橙子）。我们用 5 个相同的小球（用 0 表示）代表选中的水果。

  2. 为了把小球隔开分进 3 个盒子，我们需要 $3 - 1 = 2$ 个隔板（用 1 表示）。

  3. 例如，二进制串 0010100 代表：

     • 第 1 个隔板前有 2 个 0 $\to$ 选 2 个苹果；
     • 两个隔板之间有 1 个 0 $\to$ 选 1 个香蕉；
     • 第 2 个隔板后有 2 个 0 $\to$ 选 2 个橙子。

  4. 这样，任何一种水果组合都一一对应于一个长度为 $k + (n - 1) = 5 + 2 = 7$ 的二进制串，其中包含 $k=5$ 个 0 和 $n-1=2$ 个 1。

  5. 这个问题等价于：在 7 个位置中，选择 5 个位置放 0（或选择 2 个位置放 1）。

  6. 因此，总方法数为：

     $\binom{n+k-1}{k} = \binom{3+5-1}{5} = \binom{7}{5} = \binom{7}{2} = 21 \text{ 种}$

     

总结：计数“四宫格”模型

在解决任何计数问题前，先问自己两个问题：1. 是否放回？ 2. 顺序是否重要？

抽取方式	顺序重要 (Ordered)	顺序不重要 (Unordered)
有放回 (With Replacement)	$n^k$(例: 投硬币, 掷骰子)	$\binom{n+k-1}{k}$ (例: 插板法, 水果沙拉问题)
不放回 (Without Replacement)	$\frac{n!}{(n-k)!}$(例: 第一计数原理, 牌组序列)	$\binom{n}{k}$ (例: 第二计数原理, 组合数)

4. 组合证明 (Combinatorial Proofs)

组合证明的精髓在于“讲故事”。我们要证明一个数学等式 $LHS = RHS$，只需说明等式左边和右边是在用不同的视角，计算同一个计数问题（同一个故事）。

4.1 组合恒等式

💡 核心：如何理解二项式定理？

二项式定理的公式长这样：

$(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k}$

它的物理本质其实是“做选择”。

把 $(a+b)^n$ 写成 $n$ 个括号相乘：

$(a+b)^n = \underbrace{(a+b)(a+b)\dots(a+b)}_{n \text{ 个}}$

当我们把这个式子展开时，每一个乘积项都是从这 $n$ 个括号中，要么挑 $a$，要么挑 $b$ 乘出来的。

• 如果你想得到项 $a^k b^{n-k}$，意味着你要在 $n$ 个括号中，挑选出 $k$ 个括号贡献出 $a$，剩下的 $n-k$ 个括号贡献出 $b$。
• 挑选括号的方法数，显然就是从 $n$ 里选 $k$ 的组合数：$\binom{n}{k}$。
• 所以，每一个 $a^k b^{n-k}$ 前面的系数就是 $\binom{n}{k}$。

📌 题目 (1)：求 $\sum_{k=0}^{n} \binom{n}{k}2^k$ 的具体值。

【代数法】

对比二项式定理，我们尝试让 $a = 2, b = 1$：

$\sum_{k=0}^{n} \binom{n}{k} (2)^k (1)^{n-k} = (2+1)^n = 3^n$

因为 $1^{n-k}$ 永远等于 1，所以左边就是 $\sum_{k=0}^{n} \binom{n}{k}2^k$。

结果就是 $3^n$。

📌 题目 (2)：求 $\sum_{k=0}^{n} \binom{n}{k}$ 的具体值。

【代数法】

我们看这个求和公式：$\sum_{k=0}^{n} \binom{n}{k}$。

如果我们对比二项式定理：

$\sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k}$

如果我们让 $a = 1, b = 1$，代入进去：

$\sum_{k=0}^{n} \binom{n}{k} (1)^k (1)^{n-k} = (1+1)^n = 2^n$

代数秒杀！

【代数法：微积分求导妙用 ⚡】

我们知道：

$(x+1)^n = \sum_{k=0}^{n} \binom{n}{k} x^k$

两边同时对 $x$ 求导：

$n(x+1)^{n-1} = \sum_{k=0}^{n} k \binom{n}{k} x^{k-1}$

(看！求导把指数上的 $k$ 提到了前面，这完美创造出了我们需要的 $k$！)

现在为了让右边的 $x^{k-1}$ 重新变回 $x^k$，我们在两边同时乘以 $x$：

$n x (x+1)^{n-1} = \sum_{k=0}^{n} k \binom{n}{k} x^k$

为了匹配我们的目标公式中的 $2^k$，我们只需要令 $x = 2$ 即可：

$\text{结果} = n \cdot 2 \cdot (2+1)^{n-1} = 2n \cdot 3^{n-1}$

(1) 二项式子集恒等式 (Total Subsets Identity)

$\binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{n} = 2^n$

• 故事背景：我们要计算一个含有 $n$ 个元素的集合 $S$ 的所有可能子集（幂集）的总数。
• 视角一 (LHS)：按子集的大小进行分类计数。
  • 大小为 0 的子集（空集）有 $\binom{n}{0}$ 种；
  • 大小为 1 的子集有 $\binom{n}{1}$ 种；
  • ……；
  • 大小为 $n$ 的子集有 $\binom{n}{n}$ 种。
  • 总数即为：$\sum_{i=0}^{n} \binom{n}{i}$。
• 视角二 (RHS)：对集合中的每个元素做决策。
  • 对于第 1 个元素，可以选择“在子集中”或“不在子集中”（2 种可能）；
  • 对于第 2 个元素，同样有 2 种可能；
  • ……；
  • 每个元素都有 2 种可能，总共 $n$ 个元素。
  • 根据第一计数原理，总子集数为：$\underbrace{2 \times 2 \times \dots \times 2}_{n \text{ 个}} = 2^n$。
• 结论：两边算的是同一个故事，因此 $LHS = RHS$。

(2) 曲棍球棒恒等式 (Hockey-stick Identity) —— 详细通俗解析 💡

$\binom{n}{k+1} = \binom{n-1}{k} + \binom{n-2}{k} + \dots + \binom{k}{k}$

【为什么叫曲棍球棒？】 在杨辉三角（Pascal’s Triangle）中，如果你从某一斜行最外侧的 $\binom{k}{k} = 1$ 开始向下累加，加到某一步 $\binom{n-1}{k}$ 时，它们求和的结果刚好等于它下一行往里拐弯的那一项 $\binom{n}{k+1}$。这在几何上连起来极像一个曲棍球棒！

💡 通俗“讲故事”证明：

• 故事背景：我们要从一共有 $n$ 个候选人（编号为 $1, 2, \dots, n$）的群体中，选出一个包含 $k+1$ 个人的委员会。

• 视角一 (LHS)：

  • 直接一步到位，从 $n$ 个人里选 $k+1$ 个人，方法数显然为：

    $LHS = \binom{n}{k+1}$

• 视角二 (RHS) —— 按“选中的人中，最小编号是谁”来分情况讨论： 我们可以把所有人排成一排，编号为 $1, 2, \dots, n$。

  • 情况 1：选中的人里，最小编号是 $1$。
    • 这意味着 $1$ 号被确定选中了。
    • 剩下我们必须从比 $1$ 大的候选人（即 $2, 3, \dots, n$，共 $n-1$ 个人）里，再挑选出 $k$ 个人。
    • 方法数为：$\binom{n-1}{k}$ 种。
  • 情况 2：选中的人里，最小编号是 $2$。
    • 这意味着 $1$ 号绝不能被选，且 $2$ 号被确定选中。
    • 剩下我们必须从比 $2$ 大的候选人（即 $3, 4, \dots, n$，共 $n-2$ 个人）里，再挑选出 $k$ 个人。
    • 方法数为：$\binom{n-2}{k}$ 种。
  • 情况 3：选中的人里，最小编号是 $3$。
    • 同理，$1, 2$ 号不选，$3$ 号必选。剩下从 $n-3$ 个人里选 $k$ 个。
    • 方法数为：$\binom{n-3}{k}$ 种。
  • ……
  • 最后一种情况：选中的人里，最小编号是 $n-k$。
    • 这意味着前 $n-k-1$ 个人都不能选，而 $n-k$ 号必选。
    • 此时后面只剩下 $k$ 个人（即 $n-k+1, \dots, n$），我们必须从中挑出 $k$ 个人。
    • 方法数为：$\binom{k}{k}$（即 1 种，后面的人全选）。
    • 注意：最小编号不可能大于 $n-k$，因为如果最小编号是 $n-k+1$，后面的人数不够凑满 $k$ 个了。

• 大团圆：因为这些情况是互斥且完备的，我们将所有情况的方法数加起来，就得到了：

  $RHS = \binom{n-1}{k} + \binom{n-2}{k} + \dots + \binom{k}{k}$

• 结论：两边结果必然相等，曲棍球棒恒等式得证！

【组合故事法】

• 故事：你要从 $n$ 个不同口味的甜甜圈里，挑选一些买回家（可以不买，也可以全买）。
• 视角一 (RHS)：对每一个甜甜圈，你都有 2 种决策：“买”或“不买”。一共 $n$ 个甜甜圈，根据乘法原理，总方法数为 $2^n$。
• 视角二 (LHS)：按照你“买了多少个”分类。
  • 买 0 个的方法数：$\binom{n}{0}$
  • 买 1 个的方法数：$\binom{n}{1}$
  • ……
  • 买 $n$ 个的方法数：$\binom{n}{n}$
  • 把所有情况加起来，总数就是：$\sum_{k=0}^{n} \binom{n}{k}$
• 结论：两个视角算的是同一个甜甜圈问题，所以 $\sum_{k=0}^{n} \binom{n}{k} = 2^n$。

【组合故事法】

• 故事：学校有 $n$ 个学生，我们要把每个学生分到以下三个组之一：【红队】、【蓝队】或【替补席（不参赛）】。

• 视角一 (RHS)：每个学生都有 3 种选择。$n$ 个学生总共有 $3^n$ 种分配方案。

• 视角二 (LHS)：我们先选出 $k$ 个“要上场参赛”的学生，剩下的 $n-k$ 个自动进替补席。

  1. 从 $n$ 个学生里挑出 $k$ 个上场队员：$\binom{n}{k}$ 种方法。

  2. 这 $k$ 个上场的队员，每个人可以选择加入【红队】或【蓝队】（2 种选择）：共 $2^k$ 种方法。

  3. 遍历所有可能的参赛人数 $k$（从 0 到 $n$ 并求和）：

     $\sum_{k=0}^{n} \binom{n}{k} 2^k$

• 结论：同一个故事，因此 $\sum_{k=0}^{n} \binom{n}{k}2^k = 3^n$。

4.2 排列与错位排列 (Derangements)

• 排列 (Permutations)： 将 $n$ 个不同的元素进行全排列，我们关心的是每一个元素在序列中的特定顺序，总排列数为 $n!$。如果第 $i$ 个元素恰好排在第 $i$ 个位置上（即 $\pi_i = i$），我们称其为该排列的一个不动点 (Fixed Point)。
• 错位排列 (Derangement)： 指没有任何一个元素留在它原本位置上的排列（即对所有 $i$，都有 $\pi_i \neq i$）。
  • 记 $D_n$ 为大小为 $n$ 的集合的错位排列总数。
  • 例如当 $n=3$ 时，总共有 $3! = 6$ 种排列。其中错位排列只有 2 种：$(2, 3, 1)$ 和 $(3, 1, 2)$。因此 $D_3 = 2$。

递推公式 (Theorem 12.2)

对于 $n \ge 3$，错位排列数满足以下递推关系：

$D_n = (n-1)(D_{n-1} + D_{n-2})$

递推关系的直观证明（故事法）：

考虑最后一个位置 $n$ 上的元素 $\pi_n$。因为是错位排列，位置 $n$ 上不能放元素 $n$。假设放了元素 $j$（共有 $n-1$ 种选择，即 $j \in \{1, 2, \dots, n-1\}$）。 对于确定的 $j$，我们讨论元素 $n$ 被放在了哪里：

• 情况 1：元素 $n$ 刚好放在了位置 $j$ 上（即 $n$ 与 $j$ 互换了位置）。
  • 此时 $j$ 和 $n$ 的位置已经锁死。剩下的 $n-2$ 个元素必须在剩下的 $n-2$ 个位置上实现错位排列。
  • 这种情况有 $D_{n-2}$ 种方法。
• 情况 2：元素 $n$ 没有放在位置 $j$ 上。
  • 我们可以把“不能放在位置 $j$ 上的元素 $n$”等价地看作“不能放在位置 $j$ 上的元素 $j$”。
  • 此时，除了已经放好在位置 $n$ 的元素 $j$ 之外，剩下的 $n-1$ 个元素（含元素 $n$）在 $n-1$ 个位置上进行错位排列。
  • 这种情况有 $D_{n-1}$ 种方法。

合并以上两种情况，并乘以 $j$ 的 $n-1$ 种选择，即得：$D_n = (n-1)(D_{n-1} + D_{n-2})$。

5. 容斥原理 (The Principle of Inclusion-Exclusion, PIE)

容斥原理的核心思想是：先不考虑重叠地把所有可能性加起来，再通过“奇加偶减”来修正多算或漏算的部分。

5.1 两个集合与三个集合的容斥

• 两个集合的并集（手写笔记内容修正）：

  $|A_1 \cup A_2| = |A_1| + |A_2| - |A_1 \cap A_2|$

  • 解析：直接相加会把重合部分 $A_1 \cap A_2$ 算两次，因此必须减去一次。

• 三个集合的并集（延伸补充）：

  $|A_1 \cup A_2 \cup A_3| = (|A_1| + |A_2| + |A_3|) - (|A_1 \cap A_2| + |A_2 \cap A_3| + |A_1 \cap A_3|) + |A_1 \cap A_2 \cap A_3|$

5.2 一般性容斥原理公式

对于任意 $n$ 个有限集合 $A_1, A_2, \dots, A_n$，其并集大小为：

$|A_1 \cup \dots \cup A_n| = \sum_{i=1}^{n}|A_i| - \sum_{i < j}|A_i \cap A_j| + \sum_{i < j < k}|A_i \cap A_j \cap A_k| - \dots + (-1)^{n-1}|A_1 \cap \dots \cap A_n|$

5.3 终极大杀器：用容斥原理求解错位排列 $D_n$

我们可以用容斥原理完美推导出错位排列的精确通项公式！

1. 定义属性：设整个排列空间的大小为 $n!$。设 $A_i$ 为“第 $i$ 个元素在原本位置上（即 $\pi_i = i$）”的所有排列集合。

2. 分析目标：错位排列是指“没有任何一个元素在原本位置上”，即：

   $D_n = n! - |A_1 \cup A_2 \cup \dots \cup A_n|$

3. 计算交集项：

   • 单个集合大小：$|A_i| = (n-1)!$（因为 $i$ 位置固定，其余 $n-1$ 个元素任意排），一共有 $\binom{n}{1}$ 个这样的集合。
   • 两个集合交集大小：$|A_i \cap A_j| = (n-2)!$，一共有 $\binom{n}{2}$ 个这样的两两交集。
   • 一般地， $k$ 个集合的交集大小为 $(n-k)!$，共有 $\binom{n}{k}$ 个。

4. 代入容斥原理：

   $|A_1 \cup \dots \cup A_n| = \sum_{k=1}^{n} (-1)^{k-1} \binom{n}{k} (n-k)!$

   因为 $\binom{n}{k} (n-k)! = \frac{n!}{k!(n-k)!} (n-k)! = \frac{n!}{k!}$，所以：

   $|A_1 \cup \dots \cup A_n| = n! \sum_{k=1}^{n} \frac{(-1)^{k-1}}{k!}$

5. 最终公式：

   $D_n = n! - n! \sum_{k=1}^{n} \frac{(-1)^{k-1}}{k!} = n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(-1)^n}{n!} \right)$

   写成求和形式即为：

   $D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$

【冷知识 💡】 当 $n \to \infty$ 时，泰勒展开式 $\sum_{k=0}^{\infty} \frac{(-1)^k}{k!} = e^{-1} \approx 0.3678$。 也就是说，当人数非常多时，所有人拿错作业的概率收敛于一个常数 $1/e \approx 36.8\%$！