计数

计数是计算概率的前提，你必须在分配概率之前知道有多少种结果存在。本文涵盖乘法规则、加法规则、阶乘、排列、组合以及二项式系数，这些组合数学工具是 ML 中采样、哈希和概率分析的基础。

• 在计算概率之前，我们需要对结果进行计数。如果你想知道扑克游戏中抓到一手好牌的概率，首先需要知道所有可能的手牌数量，以及其中有多少是赢牌。计数是使概率精确化的机制。

• 最简单的计数原理是乘法规则。如果一个决策有 \(m\) 个选项，另一个独立决策有 \(n\) 个选项，那么组合结果的总数为 \(m \times n\)。

• 想象一下早上穿衣服。你有 3 件衬衫和 4 条裤子。每件衬衫都可以与每条裤子搭配，共有 \(3 \times 4 = 12\) 种可能的搭配。

• 乘法规则可以推广到任意数量的选择。如果你还有 2 双鞋，搭配总数变为 \(3 \times 4 \times 2 = 24\)。每增加一个独立的选择，数量就乘以一次。

• 加法规则处理"或"的情景。如果事件 A 可以以 \(m\) 种方式发生，事件 B 可以以 \(n\) 种方式发生，且它们不能同时发生（互斥），则总方式数为 \(m + n\)。

• 假设你可以乘车（3 条路线）或乘火车（2 条路线）从城市 X 前往城市 Y。两者不能同时进行，所以总选项为 \(3 + 2 = 5\)。

• 当事件有重叠时，你需要减去重复计数的结果。如果 \(A\) 和 \(B\) 可以同时发生，则计数为 \(|A \cup B| = |A| + |B| - |A \cap B|\)。这是容斥原理，当我们讨论概率加法规则时还会再次出现。

• 非负整数 \(n\) 的阶乘是所有不超过 \(n\) 的正整数之积：

\[n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1\]

• 把阶乘想象成回答这个问题：将 \(n\) 个不同的物体排成一排有多少种方式？书架上的三本书可以 \(3! = 3 \times 2 \times 1 = 6\) 种方式排列。按惯例，\(0! = 1\)。

• 阶乘增长极快。\(10! = 3{,}628{,}800\)，\(20!\) 已经超过 \(2.4 \times 10^{18}\)。这种爆炸式增长是组合问题中暴力搜索变得不切实际的原因。

• 排列是对象的有序排列。当从 \(n\) 个不同对象中选取 \(r\) 个且顺序重要时，排列数为：

\[P(n, r) = \frac{n!}{(n - r)!}\]

• 想象从一个有 10 名成员的俱乐部中选出主席、副主席和财务主管。第一个职位有 10 名候选人，第二个有 9 名，第三个有 8 名。因此 \(P(10, 3) = 10 \times 9 \times 8 = 720\)。公式验证了这一点：\(\frac{10!}{7!} = 720\)。

• 组合是无序的选择。当从 \(n\) 个对象中选取 \(r\) 个且顺序不重要时，我们除去冗余的排列：

\[C(n, r) = \binom{n}{r} = \frac{n!}{r!(n - r)!}\]

• 符号 \(\binom{n}{r}\) 读作"n 选 r"。关键在于每种组合对应 \(r!\) 种排列（所选的 \(r\) 个元素可以以 \(r!\) 种方式重新排列），所以我们将排列数除以 \(r!\)。

• 例：从 10 人中组成 3 人委员会有多少种方式？顺序不重要（没有主席或副主席，只有成员），所以使用组合：

\[\binom{10}{3} = \frac{10!}{3! \cdot 7!} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120\]

• 同样的 10 人产生 720 种排列但只有 120 种组合，因为每组 3 人有 \(3! = 6\) 种内部排列。

• 组合在概率论中至关重要。二项式系数 \(\binom{n}{r}\) 计算在 \(n\) 次试验中恰好获得 \(r\) 次成功的方式数，这是二项分布的核心（见第 03 篇）。

• 让我们通过一个结合多种计数思想的经典委员会问题来练习。

• 问题：一个俱乐部有 8 名男性和 6 名女性。组成一个恰好包含 3 名男性和 2 名女性的 5 人委员会有多少种方式？

• 第一步：从 8 名男性中选 3 名。

\[\binom{8}{3} = \frac{8!}{3! \cdot 5!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56\]

• 第二步：从 6 名女性中选 2 名。

\[\binom{6}{2} = \frac{6!}{2! \cdot 4!} = \frac{6 \times 5}{2 \times 1} = 15\]

• 第三步：应用乘法规则。每种男性的选法都可以与每种女性的选法配对：

\[56 \times 15 = 840 \text{ 种委员会}\]

• 这种模式——将复杂的计数问题分解为独立的子选择并相乘——是组合数学中的标准方法。

• 还有有重复的排列。当物品可以重复时，从 \(n\) 种类型中选 \(r\) 个有 \(n^r\) 种结果。使用数字 0-9 的 4 位 PIN 码有 \(10^4 = 10{,}000\) 种可能。每个位置有 10 个选项，乘法规则处理其余部分。

• 有重复的组合（也称为"星条法"）计算在允许重复且不考虑顺序时，从 \(n\) 种类型中选 \(r\) 个的方式数：

\[\binom{n + r - 1}{r} = \frac{(n + r - 1)!}{r!(n - 1)!}\]

• 例：从 4 种冰淇淋口味中选 3 球（允许重复）有 \(\binom{4 + 3 - 1}{3} = \binom{6}{3} = 20\) 种选择。

• 计数工具箱总结：

情景	公式
有序，不重复（排列）	\(P(n,r) = \frac{n!}{(n-r)!}\)
无序，不重复（组合）	\(\binom{n}{r} = \frac{n!}{r!(n-r)!}\)
有序，有重复	\(n^r\)
无序，有重复	\(\binom{n+r-1}{r}\)

• 每一个涉及等可能结果的概率计算都使用公式 \(P(\text{事件}) = \frac{\text{有利结果数}}{\text{总结果数}}\)。计数给出了这两个数字。有了这个基础，我们就可以在下一篇文章中正式化概率本身了。

编程任务（使用 CoLab 或 notebook）

1. 用阶乘公式和直接计算分别计算 \(P(10, 3)\) 和 \(\binom{10}{3}\)。验证排列数始终是组合数的 \(r!\) 倍。

   import jax.numpy as jnp
   from math import factorial
   
   n, r = 10, 3
   
   perm = factorial(n) // factorial(n - r)
   comb = factorial(n) // (factorial(r) * factorial(n - r))
   
   print(f"P({n},{r}) = {perm}")
   print(f"C({n},{r}) = {comb}")
   print(f"P / C = {perm // comb} (应等于 {r}! = {factorial(r)})")
   

2. 用编程方式解决委员会问题（从 8 名男性中选 3 名，从 6 名女性中选 2 名），并通过枚举所有有效委员会进行验证。

   from itertools import combinations
   from math import factorial
   
   def comb_count(n, r):
       return factorial(n) // (factorial(r) * factorial(n - r))
   
   # 公式法
   men_ways = comb_count(8, 3)
   women_ways = comb_count(6, 2)
   print(f"公式法: {men_ways} × {women_ways} = {men_ways * women_ways}")
   
   # 枚举法
   men = [f"M{i}" for i in range(1, 9)]
   women = [f"W{i}" for i in range(1, 7)]
   count = sum(1 for _ in combinations(men, 3) for _ in combinations(women, 2))
   print(f"枚举法: {count}")
   

3. 计算由 26 个小写字母组成的 4 字符密码的数量（允许重复）。然后计算不含重复字母的数量。

   from math import factorial
   
   n = 26
   r = 4
   
   with_rep = n ** r
   without_rep = factorial(n) // factorial(n - r)
   
   print(f"允许重复:    {with_rep:>10,}")
   print(f"不允许重复: {without_rep:>10,}")
   print(f"含重复的比例: {1 - without_rep/with_rep:.2%}")
   

4. 模拟生日问题：在 \(k\) 人的群体中，至少两人同一天生日的概率是多少？绘制 \(k = 1\) 到 \(60\) 的概率，并找到概率超过 50% 的位置。

   import jax
   import jax.numpy as jnp
   import matplotlib.pyplot as plt
   
   def birthday_prob_exact(k):
       """k 人群体中至少有一对同生日的概率。"""
       p_no_match = 1.0
       for i in range(k):
           p_no_match *= (365 - i) / 365
       return 1 - p_no_match
   
   ks = list(range(1, 61))
   probs = [birthday_prob_exact(k) for k in ks]
   
   plt.figure(figsize=(8, 4))
   plt.plot(ks, probs, color="#3498db", linewidth=2)
   plt.axhline(y=0.5, color="#e74c3c", linestyle="--", alpha=0.7, label="50%")
   cross = next(k for k, p in zip(ks, probs) if p >= 0.5)
   plt.axvline(x=cross, color="#e74c3c", linestyle="--", alpha=0.7)
   plt.xlabel("群体规模 (k)")
   plt.ylabel("P(至少一对同生日)")
   plt.title(f"生日问题（在 k={cross} 时超过 50%）")
   plt.legend()
   plt.grid(alpha=0.3)
   plt.show()