第 2 章 · 组合分析：计数的功夫

离散概率的一半工作量是数对。这一章把计数武器配齐：乘法原理、排列组合、二项式系数、容斥——每件工具配 Feller 式的具体场景。

基本计数三件套

• 乘法原理：独立步骤相乘；
• 排列 $A_n^k = \frac{n!}{(n-k)!}$（有序取）、组合 $C_n^k = \binom{n}{k}$（无序取）；
• 多重集与重复：$n$ 个元素分 $k$ 组的组合数 $\binom{n}{n_1,\dots,n_k} = \frac{n!}{n_1!\cdots n_k!}$——多项式系数。

二项式定理与恒等式工具库

代入特殊值产出恒等式流水线：$x=y=1$ 给 $\sum\binom{n}{k} = 2^n$；交错和给 $\sum(-1)^k\binom{n}{k} = 0$。Vandermonde 恒等式 $\binom{m+n}{r} = \sum\binom{m}{k}\binom{n}{r-k}$ 的"双重计数证明"（两种视角数同一批对象）是组合证明方法的样板。

概率场景的组装

• 抽样模型：放回/不放回 × 有序/无序，四象限各配公式（超几何分布来自"不放回无序"）；
• 生日悖论：$n$ 人全不同生日的概率 $= \frac{365\cdot364\cdots(365-n+1)}{365^n}$——$n=23$ 时"有人同生日"概率已过半，反直觉来自对数尺度的线性错觉（独立事件存活概率连乘衰减极快）。

老师的提醒

• 计数前先答两问：有没有顺序？放不放回？ 两问答完公式自动落位——90% 的计数错误是没答这两问。
• 生日悖论的一般教训：$\prod(1 - k/N) \approx e^{-k(k-1)/2N}$，"碰撞"在 $\sqrt{N}$ 量级就开始——密码学生日攻击、哈希冲突同源。

自检

• 写出放回/不放回抽 $k$ 个的所有计数公式。
• 双重计数证明 Vandermonde 恒等式。
• 23 人两两同生日概率过半的估算思路？

更深一层：双重计数是"组合证明"的通用语法

组合分析最有生命力的方法不是公式而是双重计数：同一个集合用两种方式数，数出来必然相等，于是恒等式成立。Vandermonde $\binom{m+n}{r} = \sum_k\binom{m}{k}\binom{n}{r-k}$ 的证明标本：从 $m$ 男 $n$ 女中选 $r$ 人——左边直接选，右边按"男性选几人"分类求和。Pascal 三角的格路解释（$\binom{a+b}{a}$ = 从原点走 $a$ 右 $b$ 上的路径数，路径必经过某条对角线）是同法的几何版。掌握"构造一个两边都能数的集合"，组合恒等式的证明就从背诵变成生产。

占位模型（球入盒）是计数公式的统一发货仓库：$n$ 个可别球入 $k$ 个可空盒 = $k^n$（函数的个数）；不可别球入可空盒 = $\binom{n+k-1}{k-1}$（隔板法，多元组合）；不可别球入不可空盒 = $\binom{n-1}{k-1}$。球的可别性 × 盒的空许性，四象限查表——任何"分配方案数"问题先定位象限。

推导细读：生日悖论的"对数尺度"真相

30 人至少两人生日相同概率约 70%——反直觉的机理值得算透。全不相同的概率是连乘 $\prod_{k=0}^{n-1}(1 - k/365)$，取对数用 $\ln(1-x) \approx -x - x^2/2$：

一次方项按 $n^2$ 累积——这就是"碰撞"的本质：比较的对数 $\binom{n}{2}$ 以平方增长，而每对的碰撞概率只有 $1/365$。$n \approx \sqrt{365\times2\ln2} \approx 22.5$ 时过半。这个 $\sqrt N$ 碰撞标度的现代应用：密码学的生日攻击（$2^{64}$ 哈希只需 $\sim2^{32}$ 次尝试碰撞）、负载均衡的哈希冲突预估。

在真实世界里：计数建模的"象限陷阱"实战

计数错误的三大陷阱与解毒剂：顺序陷阱（要不要顺序？——抽奖问题里"第几个中奖"决定用排列还是组合）、重复陷阱（元素可重复选取时 $\binom{n+k-1}{k}$ 而非 $\binom{n}{k}$——"10 个糖果分 3 个小孩"是隔板不是组合）、可别性陷阱（球是否可区分改变公式——量子统计的玻色/费米计数正是"不可别球"的两款）。解毒剂的共同口诀：先描述一个具体样本点的"完整身份证"，再数身份证的张数——身份证描述清楚了，公式自动对号。

专题深入：双重计数是"组合证明"的通用语法完整版

组合分析最有生命力的方法不是公式而是双重计数：同一个集合用两种方式数，数出来必然相等，于是恒等式成立。Vandermonde $\binom{m+n}{r} = \sum_k\binom{m}{k}\binom{n}{r-k}$ 的证明标本：从 $m$ 男 $n$ 女中选 $r$ 人——左边直接选，右边按"男性选几人"分类求和。Pascal 三角的格路解释（$\binom{a+b}{a}$ = 从原点走 $a$ 右 $b$ 上的路径数，路径必经过某条对角线）是同法的几何版。掌握"构造一个两边都能数的集合"，组合恒等式的证明就从背诵变成生产。

占位模型（球入盒）是计数公式的统一发货仓库：$n$ 个可别球入 $k$ 个可空盒 = $k^n$（函数的个数）；不可别球入可空盒 = $\binom{n+k-1}{k-1}$（隔板法，多元组合）；不可别球入不可空盒 = $\binom{n-1}{k-1}$。球的可别性 × 盒的空许性，四象限查表——任何"分配方案数"问题先定位象限。

数学细节展开：生日悖论的"对数尺度"真相完整版

30 人至少两人生日相同概率约 70%——反直觉的机理值得算透。全不相同的概率是连乘 $\prod_{k=0}^{n-1}(1 - k/365)$，取对数用 $\ln(1-x) \approx -x - x^2/2$：

一次方项按 $n^2$ 累积——这就是"碰撞"的本质：比较的对数 $\binom{n}{2}$ 以平方增长，而每对的碰撞概率只有 $1/365$。$n \approx \sqrt{365\times2\ln2} \approx 22.5$ 时过半。这个 $\sqrt N$ 碰撞标度的现代应用：密码学的生日攻击（$2^{64}$ 哈希只需 $\sim2^{32}$ 次尝试碰撞）、负载均衡的哈希冲突预估。

工程案例细节：计数建模的"象限陷阱"实战（工程版）

计数错误的三大陷阱与解毒剂：顺序陷阱（要不要顺序？——抽奖问题里"第几个中奖"决定用排列还是组合）、重复陷阱（元素可重复选取时 $\binom{n+k-1}{k}$ 而非 $\binom{n}{k}$——"10 个糖果分 3 个小孩"是隔板不是组合）、可别性陷阱（球是否可区分改变公式——量子统计的玻色/费米计数正是"不可别球"的两款）。解毒剂的共同口诀：先描述一个具体样本点的"完整身份证"，再数身份证的张数——身份证描述清楚了，公式自动对号。