# 排列组合与概率基础

[[MCS/day4/00 学习指南|day4 学习指南]] · [[MCS/00 MCS学习总览|十一天总览]] · [[MCS/day4/阅读核验与疑问|阅读核验与疑问]] · 上一篇：[[MCS/day4/03 推荐系统算法课堂记录|推荐系统算法课堂记录]] · 下一篇：[[MCS/day4/05 投骰子、先手优势与独立性|投骰子、先手优势与独立性]]

> 来源：[[MCS/day4排列组合与概率|day4排列组合与概率]]。用途：主线。原有推导、追问与解答保留；阅读时请结合本日核验说明。

## 排列组合与概率：从计数到理解不确定性

排列组合研究“有多少种可能”，概率研究“各种结果发生的可能性有多大”。它们共同构成了人类理解和应对不确定性的基本工具。

### 一、概率论的发展：从赌桌问题到统计推断

概率论的早期发展与赌博中的公平分配问题密切相关：如果一场赌局提前结束，应该怎样根据双方未来获胜的可能性分配赌注？

- **帕斯卡与费马**：讨论赌局中断后的赌注分配问题，推动了概率论的早期发展。公平分配需要考虑未来可能的结果，而不只是当前比分。
    
- **伯努利**：研究大数定律，说明在一定条件下，重复试验的频率会趋近于概率。
    
- **贝叶斯**：研究逆概率问题，即如何根据观察到的结果，更新对未知情况的判断。
    
- **拉普拉斯**：系统发展古典概率和概率推断，将直觉判断转化为数学计算。
    

概率论的一条发展主线是：**从计算可能结果，到量化不确定性，再到根据证据更新判断。**

### 二、排列组合：先数清楚可能性

#### 1. 加法原理：分类完成，任选其一

如果完成一件事有两类**互不重叠**的方法，分别有 $M$ 种和 $N$ 种，那么总方法数为：

$$  
M+N  
$$

例如，从杭州到北京，可以选择 3 班飞机中的一班，或者 5 班高铁中的一班，共有：

$$  
3+5=8  
$$

种选择。

关键词是：**或、分类、互斥**。如果两类方法有重叠，就不能直接相加，需要去除重复计数。

#### 2. 乘法原理：分步完成，步步都要

如果完成一件事需要两个步骤，第一步有 $M$ 种选择，并且对第一步的每一种选择，第二步都有 $N$ 种选择，那么总方法数为：

$$  
M\times N  
$$

例如，先从 2 种交通方式中选择一种，每种交通方式又都有 3 种座位选择，总共有：

$$  
2\times3=6  
$$

种组合。

关键词是：**且、分步、依次**。

> **分类用加法，分步用乘法；“或则加”要注意互斥，“且则乘”要数清每一步的选择数。**

#### 3. 排列与组合：是否区分顺序或角色

从 $n$ 个不同元素中取出 $k$ 个，且不重复选取：

| 方法  | 是否区分顺序 | 公式                               |
| --- | ------ | -------------------------------- |
| 排列  | 区分     | $P_n^k=A_n^k=\dfrac{n!}{(n-k)!}$ |
| 组合  | 不区分    | $\binom nk=\dfrac{n!}{k!(n-k)!}$ |
· $C_{n}^{k}$ 这套：习惯把总数放下面，因为 $C$ 的 下 标 常 表 示 “ 总 范 围 ” 。 
· $\binom nk$ 这套：习惯把总数放上面，因为它来自二项式展开 $(1+x)^n$ 的系数排列，上面写属次 $n$,下面写第几项 $k_{\mathrm{。}}$

例如，从 10 人中选 3 人参加任务，只关心选中了谁，用组合：

$$  
\binom{10}{3}=120  
$$

如果还要分别指定正队长、副队长和后勤负责人，角色不同就算不同安排，用排列：

$$  
A_{10}^{3}=10\times9\times8=720  
$$

### 三、概率基础：量化事件发生的可能性

#### 1. 古典概率

当样本空间有限，且每个基本结果**等可能**时：

$$  
P(A)=\frac{\text{事件 }A\text{ 包含的基本结果数}}  
{\text{全部基本结果数}}  
$$

排列组合帮助我们计算分子和分母，但使用这个公式之前，必须确认基本结果等可能。

#### 2. 条件概率

条件概率表示：已知事件 $B$ 发生时，事件 $A$ 发生的概率。

$$  
P(A\mid B)=\frac{P(A\cap B)}{P(B)},  
\qquad P(B)>0  
$$

已知的信息发生变化，我们计算概率时所依据的范围也会变化。

#### 3. 独立事件

如果事件 $A$ 与 $B$ 独立，那么：

$$  
P(A\cap B)=P(A)P(B)  
$$

一般情况下应使用：

$$  
P(A\cap B)=P(B)P(A\mid B)  
$$

**独立不等于互斥**：独立表示一个事件的发生不改变另一个事件的概率；互斥表示二者不能同时发生。

### 四、常见分布：描述随机结果的规律

#### 1. 二项分布：固定次数中成功多少次

进行 $n$ 次相互独立的试验，每次成功概率都为 $p$。设成功次数为 $X$，则：

$$  
X\sim\operatorname{Bin}(n,p)  
$$

$$  
P(X=k)=\binom nk p^k(1-p)^{n-k},  
\qquad k=0,1,\ldots,n  
$$

其中，$\binom nk$ 表示成功出现在其中哪 $k$ 次试验的选法。

它可以描述抛硬币的正面次数、投骰子出现指定点数的次数，也可在独立且成功概率相同的近似条件下，描述广告点击人数或检测阳性人数。

#### 2. 几何分布：等待第一次成功

重复进行相互独立、成功概率恒为 $p$ 的试验。设 $X$ 为**第一次成功所需的试验次数，包括成功的那一次**，则：

$$  
P(X=k)=(1-p)^{k-1}p,  
\qquad k=1,2,\ldots,\quad 0<p\le1  
$$

它描述“前 $k-1$ 次都失败，第 $k$ 次首次成功”，例如等待第一次中奖。

> 几何分布也有“首次成功前的失败次数”这一记法。本笔记使用从 1 开始的试验次数定义。

### 五、期望与方差：平均水平与波动程度

#### 1. 期望

期望描述随机变量按概率加权后的平均水平。对离散随机变量：

$$  
E[X]=\sum_x xP(X=x)  
$$

期望不一定是某次试验能够实际取到的值。

#### 2. 方差

方差描述随机变量偏离期望的平方偏差的平均值：

$$  
\operatorname{Var}(X)  
=E\left[(X-E[X])^2\right]  
=E[X^2]-(E[X])^2  
$$

|分布|期望|方差|
|---|---|---|
|二项分布 $\operatorname{Bin}(n,p)$ | $np$ | $np(1-p)$ |
|几何分布（首次成功所需次数）| $\dfrac1p$ | $\dfrac{1-p}{p^2}$ |

### 六、贝叶斯推断：根据证据更新判断

这里讨论的是**贝叶斯推断**，并不存在一个统一称为“贝叶斯分布”的特定分布。

设 $H$ 表示假设，$D$ 表示观察到的数据，则：

$$  
\boxed{  
P(H\mid D)=\frac{P(H)P(D\mid H)}{P(D)}  
},  
\qquad P(D)>0  
$$

即：
$$
\frac{\text{先验概率}\times\text{似然}}{\text{证据概率}}  
$$

|名称|符号|含义|
|---|---|---|
|先验概率|$P(H)$|观察数据之前，对假设的判断|
|似然|$P(D\mid H)$|假设成立时，观察到这些数据的可能性|
|证据概率|$P(D)$|综合各种假设后，观察到这些数据的概率|
|后验概率|$P(H\mid D)$|观察数据之后，对假设的更新判断|

例如，令 $H$ 表示“患病”，$D$ 表示“检测阳性”。$P(D\mid H)$ 是患病者检测阳性的概率，$P(H\mid D)$ 是检测阳性者实际患病的概率，二者不能混淆。

若沿用 $A$ 表示假设、$B$ 表示证据，则先验为 $P(A)$，似然为 $P(B\mid A)$，后验为 $P(A\mid B)$。原稿中这几个符号的对应需要据此统一。

### 七、大数定律与中心极限定理

#### 1. 大数定律：平均值逐渐稳定

在一个常用版本中，若 $X_1,X_2,\ldots$ 独立同分布，且具有有限的期望 $\mu$ 和方差，则样本均值：

$$  
\overline X_n=\frac 1 n\sum_{i=1}^{n}X_i  
$$

依概率收敛于 $\mu$：

$$  
P\left(|\overline X_n-\mu|>\varepsilon\right)\to 0,  
\qquad \forall\varepsilon>0  
$$

对于独立重复、事件发生概率恒为 $p$ 的试验，若 $N_n$ 为前 $n$ 次中事件发生的次数，则：

$$  
\frac{N_n}{n}\xrightarrow{P}p  
$$
$\frac{1}{n}\sum_{i=1}^nX_i\to E[X]$
这就是“长期来看，频率趋近于概率”的数学表达。它不表示频率每一步都会更接近概率，也不表示前面连续失败后，下一次就更容易成功。


#### 2. 中心极限定理：描述平均值附近的波动

若 $X_i$ 独立同分布，期望为 $\mu$，方差为 $0<\sigma^2<\infty$，则：

$$
\frac{\sqrt n(\overline X_n-\mu)}{\sigma}  
\xrightarrow{d}\mathcal N(0,1)  
$$
$\frac{\sum X_i-n\mu}{\sigma\sqrt{n}}\to N(0,1)$
大数定律说明平均值趋向哪里；中心极限定理说明在大样本下，经过适当标准化的波动如何近似正态分布。它不要求原始随机变量本身服从正态分布。

#### 3. 赌场为什么能长期获利

关键在于游戏规则通常使赌场的**单局期望收益为正**。

在适当的重复试验条件下，大数定律说明，随着赌局增多，平均每局收益会趋近其正期望。因此，即使单局可能亏损，大量赌局的整体收益仍会表现出统计规律。

这不保证赌场每一天或每一段有限时间都盈利。若单局期望为零或为负，增加次数本身也不会创造正收益。

### 八、从个体的不确定性到群体的规律

排列组合与概率广泛用于随机算法、算法分析、密码学、机器学习、数据科学、网络传输、推荐系统和人工智能。

单个用户是否点击、下一次传输是否出错、语言模型下一步输出哪个词，都可能存在不确定性。在条件相对稳定、满足相应统计假设时，大量观察能够帮助我们估计概率分布，识别群体趋势。

> **概率不能替我们消灭不确定性，但能让我们把不确定性量化，从而在无法预测个体的地方，看清群体的趋势。**