组合枚举法
概述
组合枚举法是费马在1654年解决点数问题时使用的方法。他通过列举所有可能的未来情景，计算"有利情景"的比例，从而得到概率。虽然这个方法在概念上更直观，但对于较大的数字会很繁琐。然而，这个思想奠定了现代概率论中"样本空间"和"古典概率"的基础。
关键内容
费马的基本思想
关键洞察：不管实际赌局是否会提前结束，我们可以想象一个假设的实验——双方总共再进行 (a + b - 1) 局（这一定足够决出胜负）。
步骤
- 确定样本空间大小：(a+b-1)局，每局2种结果，共 2^(a+b-1) 种等可能的情景
- 列举有利情景：A最终获胜的情景 = 其中至少有a个回合A赢的所有序列
- 计算有利情景数：用组合数学计算这个数量
- 计算概率：P(A获胜) = 有利情景数 / 总情景数
具体例子
A还差2局，B还差3局（a=2, b=3）。假设再进行4局（2+3-1=4）。
列举所有16种情景
| 情景序列 | A赢数 | B赢数 | A最终赢？ |
|---|---|---|---|
| AAAA | 4 | 0 | ✓ |
| AAAB | 3 | 1 | ✓ |
| AABA | 3 | 1 | ✓ |
| AABB | 2 | 2 | ✓ |
| ABAA | 3 | 1 | ✓ |
| ABAB | 2 | 2 | ✓ |
| ABBA | 2 | 2 | ✓ |
| ABBB | 1 | 3 | ✗ |
| BAAA | 3 | 1 | ✓ |
| BAAB | 2 | 2 | ✓ |
| BABA | 2 | 2 | ✓ |
| BABB | 1 | 3 | ✗ |
| BBAA | 2 | 2 | ✓ |
| BBAB | 1 | 3 | ✗ |
| BBBA | 1 | 3 | ✗ |
| BBBB | 0 | 4 | ✗ |
计算结果
- 总情景数：16
- A赢的情景数：11
- B赢的情景数：5
- A应得赌注：11/16
用组合数学简化
A最终获胜 = 4局中至少有2局A赢 = C(4,2) + C(4,3) + C(4,4) = 6 + 4 + 1 = 11
所以：$$P(A\text{获胜}) = \frac{\sum_{k=a}^{a+b-1} C(a+b-1, k)}{2^{a+b-1}} = \frac{11}{16}$$
与帕斯卡三角形的联系
帕斯卡注意到，费马方法中的组合数C(n, k)正是帕斯卡三角形中的元素。这表明组合数学与概率论的深刻联系。
与帕斯卡方法的比较
| 方面 | 费马的组合枚举法 | 帕斯卡的递推方法 | |------|------|------| | 思路 | 列举所有情景 | 分解问题，递推求解 | | 复杂度 | 需要枚举2^(a+b-1)种情景 | O(a × b)的递推计算 | | 优点 | 概念直观、易于理解 | 高效、优雅 | | 缺点 | 对大数字繁琐、易出错 | 需要建立递推关系 | | 理论贡献 | 样本空间、古典概率 | 期望值、后向归纳 |
现代含义
古典概率的基础
费马的组合枚举法直接导出了古典概率的定义：
在有限的等可能情形下，概率 = 有利结果数 / 总结果数
样本空间思想
- 明确定义所有可能结果的集合
- 基于这个集合计算事件的概率
- 这正是Kolmogorov公理化体系的基础
计数原理的应用
费马的方法展示了在概率计算中应用组合数学的强大力量——通过计数有利情景，而不是逐一列举。
意义
为什么组合枚举法重要
- 概念清晰：直接展示了概率的含义——所有等可能情景中有利情景的比例
- 理论基础：奠定了古典概率理论的基础
- 计数思想：在概率计算中引入组合数学，两个学科得到深刻联系
- 广泛应用：许多概率问题本质上都是计数问题