flykhan
2536c937e3
翻译自英文原版 maths-cs-ai-compendium，共 20 章全部完成。 第01章 向量 | 第02章 矩阵 | 第03章 微积分 第04章 统计学 | 第05章 概率论 | 第06章 机器学习 第07章 计算语言学 | 第08章 计算机视觉 | 第09章 音频与语音 第10章 多模态学习 | 第11章 自主系统 | 第12章 图神经网络 第13章 计算与操作系统 | 第14章 数据结构与算法 第15章 生产级软件工程 | 第16章 SIMD与GPU编程 第17章 AI推理 | 第18章 ML系统设计 第19章 应用人工智能 | 第20章 前沿人工智能 翻译说明： - 所有数学公式 $...$ / $$...$$、代码块、图片引用完整保留 - mkdocs.yml 配置中文导航 + language: zh - README.md 已翻译为中文（兼 docs/index.md） - docs/ 目录包含指向各章文件的 symlink - 约 29,000 行中文内容，排除 .cache/ 构建缓存
168 lines
8.1 KiB
Markdown
168 lines
8.1 KiB
Markdown
# 计数
|
||
|
||
*计数是计算概率的前提——在分配可能性之前，你必须先知道有多少种结果。本文涵盖乘法与加法规则、阶乘、排列、组合、二项式系数，以及支撑机器学习中采样、哈希和概率分析的基本组合工具。*
|
||
|
||
- 在计算概率之前，我们需要先数清结果的数量。如果你想知道在扑克中拿到一手赢牌的概率，你必须先知道一共有多少种可能的牌型，以及其中有多少种是赢牌。计数正是让概率精确化的基础工具。
|
||
|
||
- 最简单的计数原则是**乘法规则**。如果一个选择有 $m$ 种选项，另一个独立的选择有 $n$ 种选项，那么组合起来的总结果数为 $m \times n$。
|
||
|
||
- 想象早上穿衣服的场景。你有 3 件衬衫和 4 条裤子。每件衬衫都能与每条裤子搭配，共有 $3 \times 4 = 12$ 种穿搭。
|
||
|
||
|
||
|
||
- 乘法规则可以推广到任意数量的选择。如果你还有 2 双鞋，那么总穿搭数就变成 $3 \times 4 \times 2 = 24$。每个新的独立选择都会乘到总计数中。
|
||
|
||
- **加法规则**处理"或"的场景。如果事件 A 有 $m$ 种发生方式，事件 B 有 $n$ 种发生方式，且它们不能同时发生（互斥），那么总的方式数为 $m + n$。
|
||
|
||
- 假设你要从城市 X 前往城市 Y：开车有 3 条路线，坐火车有 2 条路线。你无法同时选择两者，因此总选项数为 $3 + 2 = 5$。
|
||
|
||
- 当事件有重叠时，需要减去被重复计数的结果。如果 $A$ 和 $B$ 可以同时发生，计数为 $|A \cup B| = |A| + |B| - |A \cap B|$。这就是容斥原理，它将在我们讨论概率加法规则时再次出现。
|
||
|
||
- 非负整数 $n$ 的**阶乘**是从 1 到 $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 名女性。要组成一个 5 人委员会，其中恰好包含 3 名男性和 2 名女性，有多少种方式？
|
||
|
||
- **第 1 步**：从 8 人中选 3 名男性。
|
||
|
||
$$\binom{8}{3} = \frac{8!}{3! \cdot 5!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$$
|
||
|
||
- **第 2 步**：从 6 人中选 2 名女性。
|
||
|
||
$$\binom{6}{2} = \frac{6!}{2! \cdot 4!} = \frac{6 \times 5}{2 \times 1} = 15$$
|
||
|
||
- **第 3 步**：应用乘法规则。每种男性选择可以与每种女性选择配对：
|
||
|
||
$$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!$ 倍。
|
||
```python
|
||
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 名女性），并通过枚举所有有效委员会来验证。
|
||
```python
|
||
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 位密码有多少种（允许重复）。然后统计没有重复字母的密码有多少种。
|
||
```python
|
||
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% 的位置。
|
||
```python
|
||
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()
|
||
```
|