计数

计数

计数是计算概率的前提——你必须先知道有多少种可能的结果，才能为它们分配概率。本文件介绍乘法原理与加法原理、阶乘、排列、组合以及二项式系数，这些组合工具是机器学习中采样、哈希和概率分析的基础。

• 在计算概率之前，我们得先数清楚结果。想知道拿到一手赢牌的概率，你首先得知道总共有多少种可能的牌型，其中又有多少种是赢牌。计数正是让概率变得精确的工具。

• 最简单的计数原理是乘法原理（multiplication rule）。如果第一个决定有 m 个选项，第二个独立决定有 n 个选项，那么组合后的结果总数是 m \times n。

• 想象你早上穿衣服。你有 3 件衬衫和 4 条裤子。每件衬衫都能和每条裤子搭配，于是你共有 3 \times 4 = 12 套穿搭。

• 乘法原理可以推广到任意多个选择。如果你还有 2 双鞋，总穿搭数就变成 3 \times 4 \times 2 = 24。每一个新的独立选择都会让总数翻倍地乘上去。

• **加法原理（addition rule）**处理的是"或"的场景。如果事件 A 可以以 m 种方式发生，事件 B 可以以 n 种方式发生，且它们不能同时发生（互斥），那么总方式数就是 m + n。

• 假设你从城市 X 到城市 Y 可以开车（3 条路线）或坐火车（2 条路线）。你不可能同时用两种方式，所以总选项是 3 + 2 = 5。

• 当事件有重叠时，你需要减去被重复计算的结果。如果 A 和 B 可以同时发生，总数就是 |A \cup B| = |A| + |B| - |A \cap B|。这就是容斥原理（inclusion-exclusion principle），等我们讨论概率加法法则时会再次出现。

• 非负整数 n 的**阶乘（factorial）**是所有不超过 n 的正整数的乘积：

• 可以把阶乘理解为在回答：把 n 个不同的物体排成一列有多少种排法？书架上的 3 本书可以有 3! = 3 \times 2 \times 1 = 6 种排法。按惯例，0! = 1。

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

• **排列（permutation）**是物体的一种有序安排。当你从 n 个不同物体中取出 r 个且顺序重要时，排列数是：

• 想象从 10 个人的社团里选出社长、副社长和财务。第一个职位有 10 个候选人，第二个剩下 9 个，第三个剩下 8 个，于是 P(10, 3) = 10 \times 9 \times 8 = 720。公式也印证了这一点：\frac{10!}{7!} = 720。

• **组合（combination）**是一种无序的选择。当你从 n 个物体中取出 r 个且顺序不重要时，我们要把多余的排序除掉：

• 记号 \binom{n}{r} 读作"n 选 r"。关键的洞见是：每一个组合对应 r! 个排列（被选中的 r 个物体可以有 r! 种重排方式），所以我们要把排列数除以 r!。

• 例子：从 10 个人中选出 3 人委员会有多少种选法？顺序不重要（没有社长副社长之分，只有成员），所以我们用组合：

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

• 组合是概率的核心。二项式系数 \binom{n}{r} 统计的是在 n 次试验中恰好取得 r 次成功的方式数，这正是二项分布（在第 3 节讨论）的核心。

• 我们来做一道融合多种计数思想的经典委员会问题。

• 问题：一个社团有 8 男 6 女。要组成一个 5 人委员会，其中恰好包含 3 男 2 女，有多少种选法？

• 第 1 步：从 8 个男生中选 3 个。

• 第 2 步：从 6 个女生中选 2 个。

• 第 3 步：套用乘法原理。每一种男生的选法都能和每一种女生的选法配对：

• 这种把复杂计数问题拆成若干独立子选择、再相乘的模式，是组合数学中的标准做法。

• 还有可重复排列（permutations with repetition）。当物品可以重复时，从 n 类物品中取 r 个会得到 n^r 种结果。一个用 0-9 数字的 4 位 PIN 码有 10^4 = 10{,}000 种可能。每一位有 10 个选项，乘法原理搞定剩下的部分。

• 可重复组合（combinations with repetition）（也叫"隔板法"）统计的是允许重复且顺序不重要时，从 n 类物品中取 r 个的方式数：

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

• 总结一下计数工具箱：

• 每一个涉及等可能结果的概率计算都用公式 P(\text{event}) = \frac{\text{favourable outcomes}}{\text{total outcomes}}。计数为我们提供了分子分母两个数字。有了这个基础，我们就可以在下一节正式定义概率本身了。

编程练习（使用 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} (should equal {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"Formula: {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"Enumeration: {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 repetition:    {with_rep:>10,}")
print(f"Without repetition: {without_rep:>10,}")
print(f"Fraction with repeats: {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("Group size (k)")
plt.ylabel("P(at least one shared birthday)")
plt.title(f"Birthday Problem (crosses 50% at k={cross})")
plt.legend()
plt.grid(alpha=0.3)
plt.show()
​