组合计数与等可能模型 | 概率论 I | 自在学

组合计数与等可能模型

上一章把概率的基本规则写清楚了：事件可以取并集、交集和补集，互斥事件的概率能够相加。不过，规则本身并不会告诉我们，一组人恰好有两人同生日的概率是多少，或者抽查一批产品时为什么有时用排列、有时用组合。我们还需要把这些问题翻译成一个能够计算的样本空间。

你可能已经很熟悉“有利情况数除以全部情况数”这句话。这一章要追问的是：这里的一种“情况”，到底是什么？为什么每一种情况可以占一样大的分量？ 很多计数题算到最后才发现分母不对，问题其实早在第一行就发生了：把顺序不同的结果合在了一起，却忘了合并之后的结果可能不再等可能。

我们会从这个最容易忽略的地方出发，再逐步得到排列、组合、不放回抽样和生日问题。这样做以后，公式就有了来处：分母是在数哪些结果，分子是在挑哪些结果，为什么要乘，为什么能除，每一步都能说清楚。

有利情况数除以全部情况数，前提藏在哪里

先把熟悉的公式从公理推出来。假设有限样本空间 $\Omega$ 一共有 $M$ 个样本点，而且每个点的概率都是同一个数 $c$ 。全部样本点互不重叠，合起来正是 $\Omega$ ，所以有限可加性给出

1=P(\Omega)=\underbrace{c+c+\cdots+c}_{M\text{ 项}}=Mc.

于是 $c=1/M$ 。如果事件 $A$ 包含 $r$ 个样本点，它的概率就是 $r$ 个 $1/M$ 相加：

P(A)=\frac{r}{M}=\frac{|A|}{|\Omega|}.

这不是一条适用于所有概率问题的定义，而是有限样本空间里，每个样本点等可能时，由概率公理推出的计算公式。如果有的点概率大、有的点概率小，数点就不能代替加概率。

为什么骰子点数和不能直接按十一种情况平分

把两枚骰子分别叫作甲骰和乙骰，记录有序对 $(i,j)$ 。在两枚骰子公平、投掷结果独立的模型里， $36$ 个有序点数对各占 $1/36$ 。这里“独立”暂时理解为知道甲骰的结果不改变乙骰的各点数概率；后面会给出正式定义。

现在求点数和为 $8$ 的概率。符合要求的完整记录是

(2,6),\ (3,5),\ (4,4),\ (5,3),\ (6,2).

一共五个，所以概率为 $5/36$ 。如果我们只写下“点数和是 $2,3,\ldots,12$ ”，虽然同样能描述所关心的结果，却不能把这十一个数按 $1/11$ 平分。和为 $2$ 只接收了 $(1,1)$ 这一个原始结果；和为 $7$ 接收了六个，得到的概率自然不同。

这件事也解释了一个看似矛盾的问题：样本空间是不是必须记录所有细节？不必。只记录点数和也完全可以建立概率模型，但必须给各个和分配正确的概率。把结果记录得更粗，不会自动把概率变得更均匀。 后面研究随机变量时，我们还会反复遇到这种“把很多原始结果归到同一个数”的操作。

公平的单个部件，还不够保证整个记录等可能

有两枚公平硬币，是否一定能把“正正、正反、反正、反反”各赋予 $1/4$ ？还不能。设第二枚硬币总是跟第一枚同面，那么单看每枚，正反仍然各占一半，但实际只会出现正正和反反，各占 $1/2$ 。

因此，计算多次试验的等可能序列时，通常需要“每次均匀，并且各次独立”这样的机制说明。题目中一个含糊的“随机”，也不等于“在我们刚选定的样本空间上均匀”。概率模型的假设要落到具体操作上，例如“每次都从剩下的球中等概率选一个”。

计数只能告诉我们结果有多少种，不能替我们决定每种结果有多大概率。先说明随机选择的机制，再检查正在计数的对象是否等可能；这一步省掉了，后面的阶乘即使全部算对，也可能得到错误的概率。

一件事分几步完成，就沿着选择过程数下去

现在暂时不谈概率，只解决“有多少种结果”。一个四位验证码允许用 $0$ 到 $9$ ，可以以 $0$ 开头，也可以重复。第一个位置十种，第二个位置仍然十种，接下来一样，因此共有 $10^4$ 个验证码。

为什么能够相乘？你可以把前两位画成一棵树：第一层十条分支，每条分支下面又长出十条，共有一百条走到第二层末端的路径。再增加一个位置，每条已有路径又各接十种可能。乘法原理数的是这种完整路径：如果第一步有 $a_1$ 种选择，而且无论之前怎么选，第 $j$ 步都恰有 $a_j$ 种选择，那么总数为

a_1a_2\cdots a_k.

这里不要求“后一步可选的是同一批对象”，只要求同一阶段的可选数量一致。若验证码要求数字互不相同，选完 $2$ 后和选完 $8$ 后，剩下的数字集合不一样，但都剩九个，所以仍然可以得到

10\cdot9\cdot8\cdot7=5040.

再加一条“首位不能是零”，第一位就只剩九种。第二位还是九种，因为零虽然不能出现在第一位，却能出现在第二位。答案因此是

9\cdot9\cdot8\cdot7=4536.

如果写成 $9\cdot8\cdot7\cdot6$ ，就把零从所有位置里都删掉了。这种错误很常见：把只属于某个位置的限制，误用到所有位置。

不同分支长度不一样，就先分类再相加

从数字 $0,1,2,3$ 中组成一个两位整数，要求没有重复且能被 $5$ 整除。个位只能是 $0$ ，十位可选 $1,2,3$ ，所以是三种。这个例子很简单，但它提醒我们：先安排限制最强的位置，通常比从左到右硬套公式更省事。

再看一个真正需要分支的例子：用 $0,1,2,3$ 组成没有重复数字的两位偶数。若个位为 $0$ ，十位有三种；若个位为 $2$ ，十位不能是 $0$ 或 $2$ ，只有两种。两类不会重叠，全部答案为 $3+2=5$ ，即。

加法原理的条件就在这里：分类必须互斥，并且没有漏掉结果。对互斥的有限集合 $A_1,\ldots,A_s$ ，

|A_1\cup\cdots\cup A_s|=|A_1|+\cdots+|A_s|.

如果分类重叠，就要减掉重复计数的部分。例如两类结果满足

|A\cup B|=|A|+|B|-|A\cap B|.

这正是上一章事件加法公式在“数点”上的对应版本。

乘法原理也不要求各阶段的随机选择独立。它首先是一条关于数量的结论。比如不放回抽球，各次结果之间有关联，但完整序列仍然可以用“第一次数量乘以第二次数量”来数。把计数乘法和独立事件的概率乘法分清楚，后面学习条件概率会轻松许多。

排列与组合：除以阶乘到底除掉了什么

假设有八名同学，要选出组长、记录员和汇报人，每人最多担任一个职位。选组长有八种，选定组长以后记录员有七种，再选汇报人有六种，因此共有 $8\cdot7\cdot6=336$ 种安排。

这类结果是一串有角色、有位置的记录。从 $n$ 个不同对象中选 $k$ 个，不重复且保留顺序，排列数记为 $P(n,k)$ ：

P(n,k)=n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!},\qquad 0\le k\le n.

当 $k=n$ 时，这就是把所有对象排一遍，得到 $n!$ 。我们约定 $0!=1$ ，也约定空乘积等于 $1$ ：什么都不选，仍然有且只有一种空记录。于是 $P(n,0)=1$ ，边界情形不用额外改公式。

同一小组为什么恰好被数了六次

如果题目改成“只选三名同学组成小组，不分角色”，甲乙丙、甲丙乙、乙甲丙等六种记录实际上指向同一小组。对任意一个三人小组，内部都恰好有 $3!=6$ 种排列，所以把 $336$ 除以 $6$ ，得到 $56$ 个小组。

一般地，把每个有序的 $k$ 人记录变成无序集合，每一个集合都恰好对应 $k!$ 个有序记录。因此组合数为

\binom{n}{k}=\frac{P(n,k)}{k!}=\frac{n!}{k!(n-k)!}.

读作“从 $n$ 个中选 $k$ 个”。这里的除法依赖于一个很具体的事实：每一类的重复次数相同。它不是“题目不看顺序，所以随手除一个阶乘”。

三个不同对象的六种有序排列合并成同一个无序小组 — 不同对象不重复入选时，每个大小为 $k$ 的集合恰好对应 $k!$ 个排列，因此可以统一除重。

出现重复对象以后，除重次数要重新计算

用字母 A、A、B 组成长度为三的字符串，一共有 AAB、ABA、BAA 三种。若先把两张 A 临时标成 $A_1,A_2$ ，三个不同标签有 $3!$ 种排列；但交换两个 A 的标签并不会改变最终字符串，所以每个字符串被算了 $2!$ 次。结果为 $3!/2!=3$ 。

更一般地，总长度为 $k$ ，其中第 $i$ 类对象出现 $k_i$ 次，且 $k_1+\cdots+k_r=k$ ，不同字符串数是

\frac{k!}{k_1!k_2!\cdots k_r!}.

这个公式以后还会用于计算“某类结果出现几次”的概率。眼下先记住它的理由：同类对象互换不产生新记录，不同类对象互换通常会。

两个组合恒等式，其实都在数同一批东西

从 $n$ 人中选 $k$ 人，等价于决定哪 $n-k$ 人不入选，因此

\binom{n}{k}=\binom{n}{n-k}.

再固定一个人，叫作小林。所有 $k$ 人小组可分成“不含小林”和“含小林”两类。前者从其他 $n-1$ 人中选 $k$ 人，后者只需再选 $k-1$ 人，所以

\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}.

这就是组合数相邻两项相加得到下一行对应项的原因。你当然可以用阶乘通分验证，但分类计数直接解释了等号为什么成立。我们通常还约定：整数 $k<0$ 或 $k>n$ 时， $\binom{n}{k}=0$ ，因为这种选法根本不存在；而。

四种抽样方式中，最容易误用的是哪一种

排列和组合的差别来自“是否记录顺序”；另一个独立的问题是“能否重复选到同一个对象”。把这两个问题合在一起，就得到下面四种计数。

记录方式	是否允许重复	一个结果记录什么	结果数量
有序	允许	长度为 $k$ 的序列	$n^k$
有序	不允许	$k$ 个不同对象的有序记录	$P(n,k)$
无序	不允许	大小为 $k$ 的子集

这里 $n\ge1$ 、 $k\ge0$ 均为整数；不允许重复时还需要 $k\le n$ ，否则方案数为零。表里说的是结果数量。它没有保证四行里的结果，在某个具体随机机制下都等可能。

无序且允许重复：把数量记录变成一道隔板题

从三种水果中买五个，只关心苹果、梨、桃分别买多少。设数量为 $x_1,x_2,x_3$ ，则

x_1+x_2+x_3=5,\qquad x_1,x_2,x_3\in\{0,1,2,\ldots\}.

把五个名额写成五颗星，再用两根隔板切成三段。比如“星星、隔板、隔板、星星星”表示 $(2,0,3)$ ；两根隔板相邻，表示中间一种水果买了零个。隔板出现在开头或结尾，也分别对应第一种或最后一种数量为零。

任何一个数量向量都恰好对应这样一串星与隔板；反过来，每串记录也能唯一读出三个数量。这种一一对应保证既不漏数也不重数。总共七个位置，只需选择哪两个放隔板，所以有 $\binom72=21$ 种买法。

一般地， $k$ 颗星加上 $n-1$ 根隔板，总位置数为 $k+n-1$ ，因此非负整数解的个数为

\#\{(x_1,\ldots,x_n):x_1+\cdots+x_n=k\} =\binom{k+n-1}{n-1}=\binom{k+n-1}{k}.

如果要求每种至少买一个，就先给每种留出一个，令 $y_i=x_i-1$ 。剩下的数量满足 $y_1+\cdots+y_n=k-n$ ，所以当时有

\binom{k-1}{n-1}

种方案；当 $k<n$ 时则没有方案。若某种水果还有“最多两个”的限制，普通隔板公式就不再直接适用，需要扣掉违反上限的解，或者按该种数量分类。

为什么连续均匀抽取，再忽略顺序，不会得到均匀的数量向量

盒中只有标着 A、B 的两张卡。独立抽两次，每次等概率抽一张并放回。完整序列有 AA、AB、BA、BB 四种，各占 $1/4$ 。

忽略顺序后只剩三种数量结果：两个 A、一 A 一 B、两个 B。三种结果的概率依次为 $1/4,1/2,1/4$ ，不是各占 $1/3$ 。中间那类接收了 AB、BA 两个序列，两端各只接收一个。

这也直接解释了为什么“有序有放回的 $n^k$ 除以 $k!$ ”通常不是无序有放回的数量：AA 的排列只有一个，AB 的排列有两个，各类被重复的次数不一样，不能统一除重。

若每次独立、均匀地从 $n$ 种对象中抽取一个，一共抽 $k$ 次，那么给定数量向量 $(x_1,\ldots,x_n)$ 的概率实际为

\frac{k!}{x_1!\cdots x_n!}\frac{1}{n^k},\qquad x_1+\cdots+x_n=k.

分母 $n^k$ 是所有等可能序列数，分子是该数量向量对应的序列数。不同向量的分子不同，所以概率也不同。如果另外设计一个机制，在所有数量向量中均匀选一个，那么它们才各占 $1/\binom{n+k-1}{k}$ ；这是另一种随机机制。

“无序、有放回”的组合公式能回答有多少种多重集合，不能直接回答连续均匀抽取时每个多重集合有多大概率。记录方式相同，不代表产生记录的机制相同。

计数器适合用小参数核对四个公式。先取 $n=3,k=2$ ：四种计数应分别是 $9,6,3,6$ 。然后回到三个对象独立抽两次的过程，想一想为什么六个无序可重复结果没有相同概率。能解释清楚这个区别，比只记住四个答案更有用。

再用两个字母把这个陷阱看清楚：每次独立、等概率地抽到 A 或 B，抽完放回，共抽两次。若最后只记录 A 出现几次，四条等可能的有序记录就被合并成三类，中间那一类会接住两条记录。

两个独立公平 A/B 试验的四个等可能顺序结果，按 A 出现次数合并后概率分别为四分之一、二分之一和四分之一。 — AA、AB、BA、BB 各占四分之一；AB 和 BA 都使 A 出现一次，因此合并后的这一类概率为二分之一。

不放回抽样为什么可以直接数无序子集

刚才忽略顺序导致了不等可能，那么扑克牌为什么又能按无序手牌来数？区别就在于每个粗记录对应的细记录数量是否一样。

设总体中有 $N$ 个可区分对象，每次从剩下的对象中等概率取一个，共取 $n$ 个，不放回。一个指定有序序列的概率为

\frac1N\cdot\frac1{N-1}\cdots\frac1{N-n+1} =\frac1{P(N,n)}.

每个大小为 $n$ 的子集都恰好有 $n!$ 个抽取顺序，因此这个子集的概率为

\frac{n!}{P(N,n)}=\frac1{\binom Nn}.

所以无序子集确实等可能。不放回使每个样本都由 $n$ 个不同对象构成，所有样本内部的顺序数都一样。 这正是无序计数在这里合法、在前面的有放回反例里不合法的原因。

“球可区分”也需要稍作解释。八个红球和十二个白球即使外观相同，仍是二十个物理对象，可以在脑中给它们编号。均匀抽球先作用在这二十个对象上，然后我们只读取颜色。不能因为只关心颜色，就把“零个红球、一个红球、两个红球……”当成等可能结果。

同一件事，分子和分母必须按同一尺度记录

从十人中等概率选三人，求指定的小林入选的概率。用无序小组计数，小林已经占一个名额，另外两人从其余九人中选：

P(\text{小林入选})=\frac{\binom92}{\binom{10}3}=\frac3{10}.

用有序的三人记录也可以。小林可在三个位置中的任意一个，其余两个位置从剩余九人中依次选，所以

P(\text{小林入选})=\frac{3\cdot9\cdot8}{10\cdot9\cdot8}=\frac3{10}.

两种方法都对，因为各自的分子分母保持了一致。若分子写 $\binom92$ ，分母却写 $10\cdot9\cdot8$ ，就把一个按无序计数的事件除以一个按有序计数的总体，少算了每组对应的六个顺序。

先分清“恰好”和“至少”，再决定从哪一面数

设一副标准扑克牌有 $52$ 张，其中 $4$ 张是 A。充分随机洗牌后抽五张，所有五张手牌等可能。若问“恰好两张 A”，必须同时满足两件事：四张 A 中选两张，另外三张全部来自 $48$ 张非 A。于是

P(\text{恰好两张 A}) =\frac{\binom42\binom{48}3}{\binom{52}5}.

这里分子不能写成 $\binom42\binom{50}3$ 。因为选出的两张 A 之外还剩两张 A，若允许其余三张从剩余五十张随便选，就可能抽到第三张、第四张 A，违背“恰好”。而且含三张或四张 A 的手牌会随着“先指定哪两张 A”被重复数入。

如果改问“至少一张 A”，正面当然可以分成恰好一张、两张、三张、四张。四类互斥，概率可以相加：

P(\text{至少一张 A}) =\frac{\displaystyle\sum_{j=1}^{4}\binom4j\binom{48}{5-j}}{\binom{52}5}.

但补集只有一种描述：“五张全不是 A”。所以更短的写法是

P(\text{至少一张 A}) =1-\frac{\binom{48}5}{\binom{52}5}.

补集不是另一个神秘技巧，它只是利用上一章已经证明的 $P(A)=1-P(A^c)$ ，把不好数的集合换成好数的集合。

条件重叠时，不能把每个“坏情形”直接相加

从十人中等概率选五人，其中包括甲和乙。求至少选中甲乙之一的概率。“选中甲”和“选中乙”会在“两人都选中”时重叠，所以直接算 $\binom94+\binom94$ 会多算。

用容斥，符合条件的小组数为

2\binom94-\binom83.

用补集，则是全部小组减去“甲乙都没入选”的小组数：

\binom{10}5-\binom85.

两者都是 $196$ ，除以总数 $252$ 得到 $7/9$ 。把同一题用两种方法算通，是检查计数是否重叠的一个好办法。

超几何模型：把抽样里某一类对象的数量单独记录下来

前面的扑克牌例子可以换成质检、问卷抽样或班级组队。它们的结构相同：有限总体分成两类，均匀不放回抽取固定数量，关心其中一类抽到了几个。

设总体有 $N$ 个对象，其中 $K$ 个带有我们关心的特征，另有 $N-K$ 个没有。均匀选出大小为 $n$ 的子集。用 $X$ 表示样本中带特征的对象数。我们以后会正式定义“随机变量”；现在可以先把 $X$ 看作一个记录规则：输入一个抽样结果，输出其中的特征数量。

通常把带特征的一类叫作“成功”，但这个词只是分类名称。质检时把次品叫成功，并不是说次品是一件好事。

一个概率公式里的三个组合数，各自在数什么

总共有 $\binom Nn$ 个等可能样本。要让 $X=x$ ，先从 $K$ 个成功对象里选 $x$ 个，再从 $N-K$ 个其他对象里选个。这两组选法合起来唯一确定一个样本，因此

P(X=x)=\frac{\binom Kx\binom{N-K}{n-x}}{\binom Nn}.

这就是超几何概率公式。参数 $N,K,n$ 均为整数，满足 $0\le K\le N$ 、 $0\le n\le N$ 。 $x$ 的范围要由实际能抽出的数量决定：成功对象不能多于，不能多于样本量；非成功对象只有个，因此至少有个名额必须由成功对象补足。综合得到

\max\{0,n-(N-K)\}\le x\le\min\{K,n\},\qquad x\text{ 为整数}.

比如总体十个，其中八个属于目标类，抽五个。最多只有两个非目标对象，所以至少抽到三个目标对象。此时 $X$ 只可能是 $3,4,5$ ，绝不是从 $0$ 到 $5$ 都可能。支持范围也是公式的一部分，不能等计算完才补一句。

一次质检，把完整分布核对出来

设十二个零件中有三个次品，均匀不放回抽取四个。抽到的次品数 $X$ 可以是 $0,1,2,3$ 。总样本数为 $\binom{12}4=495$ ，逐项计数得到：

次品数 $x$	相应样本数	概率
$0$	$\binom30\binom94=126$

四行样本数之和是 $495$ ，因此概率总和为 $1$ 。至少查出一个次品的概率为 $1-126/495=41/55$ ，约为 $0.7455$ 。这里的“至少”可以直接把后三行加起来，也可以用补集，结果一致。

这还给了我们一个组合恒等式。所有大小为 $n$ 的样本，按成功对象数 $x$ 分成互斥且完整的各类，因此

\sum_x\binom Kx\binom{N-K}{n-x}=\binom Nn.

求和只遍历可能的整数 $x$ ，或者用超范围组合数为零的约定。超几何公式的各项相加为一，并非巧合；它来自对同一个样本空间的完整分类。

探索器里的彩色小球用于表示总体比例，显示数量可能经过缩放，不必逐个数小球；精确数量以 $N$ 和 $K$ 为准。把参数设为 $N=12,K=3,n=4$ ，核对上表四个概率。再把 $n$ 增加到 $N$ ：既然已经把总体全部抽出来，目标数量只能等于，图中就应只剩这一处有概率。这是检查模型边界最直接的方法。

和二项模型的区别，不在于题目有没有写“成功”

同样从十二个零件中抽四次，如果每次检查后放回并重新均匀抽取，各次是否抽到次品独立，每次成功概率都是 $p=3/12$ 。一个指定的“次品、合格品、合格品、合格品”序列概率为 $p(1-p)^3$ ；唯一的次品可以出现在四个位置，因此恰好一次成功的概率是 $4p(1-p)^3$ 。

推广到 $n$ 次独立试验，每次成功概率同为 $p$ ，恰好 $x$ 次成功就有

P(X=x)=\binom nx p^x(1-p)^{n-x}.

组合数选择成功出现的位置，后面的幂给出其中每个指定序列的概率。这就是以后要系统讨论的二项模型。这里先做比较：不放回抽样时，若第一次已拿走一个次品，剩余次品比例会变成 $2/11$ ；若第一次拿走合格品，剩余比例则是 $3/11$ 。后续概率会随已知结果改变，不能继续按独立的 $p=1/4$ 连乘。

每个抽取位置单独看，抽到次品的概率仍然可以相同；问题在于各位置并不独立。因此，“每次成功概率相同”本身不足以得到二项公式。

当样本量 $n$ 固定，而总体越来越大，成功比例 $K/N$ 趋近某个 $p$ ，取走少量对象对总体比例的影响越来越小，超几何概率会趋近相应二项概率。有限总体下它们通常仍不相等；尤其抽走总体的一大部分时，不能只因为“总体看起来很大”就忽略不放回的影响。

生日问题：为什么二十三个人就已经值得担心重复

现在回到一个常常让直觉吃惊的问题：一屋子人中，至少有两个人生日相同的概率多大？为了把结构讲清楚，先明确简化模型：一年按 $365$ 天计算，忽略闰日；每个人生日在这 $365$ 天上均匀分布，而且人与人之间独立。

把屋里 $m$ 个人编号，一个样本点就是按编号写出的 $m$ 个生日组成的序列。完整样本空间有 $365^m$ 个等可能点。这里顺序是“这个生日属于哪一个人”，即使不在意进屋顺序，仍不能把不同人的生日分配混为一谈。

正面重叠太多，反面却是一条清楚的选择链

“至少两人同生日”可以是只有一对，可以是两对，还可以是三人一起同生日。如果对每一对同生日分别计数后直接相加，某些样本会被算很多次。

补集“所有人的生日都不同”更容易。第一人任意，第二人要避开一天，第三人要避开已占的两天。只要前面生日都不同，第 $j$ 人就还有 $365-j+1$ 天可选。因此当 $0\le m\le365$ 时，

P(\text{生日全不同}) =\frac{365\cdot364\cdots(365-m+1)}{365^m} =\prod_{j=0}^{m-1}\left(1-\frac j{365}\right).

于是

P(\text{至少两人同生日}) =1-\prod_{j=0}^{m-1}\left(1-\frac j{365}\right).

$m=0$ 时用空乘积等于 $1$ 的约定，碰撞概率为零； $m=1$ 时同样为零。当 $m>365$ 时，由于人数超过可用日期数，至少有两人同生日，概率直接是 $1$ 。不能继续把乘积硬写到负因子。

代入 $m=22$ ，至少两人同生日的概率约为 $0.4757$ ；代入 $m=23$ ，约为 $0.5073$ 。跨过一半的门槛，只需要二十三人。这个结论完全来自我们刚才写出的模型和有限计数，不需要用大量实验才能成立。

“有两个人相同”和“有人跟我相同”是不同事件

在二十三人中，任意两人都可以碰上，共有 $\binom{23}2=253$ 对。而如果指定其中的你，问“其余二十二人有没有人与你同生日”，只有二十二个人可以与你匹配，其概率是

1-\left(\frac{364}{365}\right)^{22}\approx0.0586.

这两个概率差很多，因为前一个事件也包括与你无关的其他人彼此同生日。我们常把“至少某一对”误听成“至少有一个人和我匹配”，直觉于是低估了重复的机会。

不过， $253$ 对也不能理解成 $253$ 次相互独立的比较。若甲乙同生日、乙丙同生日，那么甲丙必然同生日。把每一对的碰撞概率 $1/365$ 直接加起来，会重复计算具有多次碰撞的结果。 $\binom m2/365$ 可以给出并事件的上界，但通常不是精确概率。

碰撞门槛为什么与日期数量的平方根有关

把一年天数推广为 $d$ 个等可能位置。无碰撞概率仍然是 $\prod_{j=0}^{m-1}(1-j/d)$ 。当每个 $j/d$ 都较小时，利用在附近约等于，可得到

\log P(\text{无碰撞}) =\sum_{j=0}^{m-1}\log\left(1-\frac jd\right) \approx-\sum_{j=0}^{m-1}\frac jd =-\frac{m(m-1)}{2d}.

指数变换后，

P(\text{至少一次碰撞}) \approx1-\exp\left(-\frac{m(m-1)}{2d}\right).

若让近似概率等于一半，就得到 $m(m-1)\approx2d\log2$ 。这说明门槛大致在 $\sqrt d$ 的量级，而不是的量级。这个近似来自对数展开，累计遗漏项的量级约为；当这个量不小时，就应回到精确乘积，不能只看某一个因子似乎接近一。

模拟器左上角的日期格是示意装饰，不是某一组人实际抽取的生日记录；模拟结果应读取“模拟估计”和命中组数。先把人数设在二十二和二十三附近，比较理论概率与模拟频率。一次模拟里有没有同生日只会给出“有”或“没有”；重复很多组人以后，发生碰撞的组数占比才是频率。有限次频率可能高于或低于理论值，增加模拟次数也不会让误差每一步都下降。后面的大数定律会解释这种频率为什么具有长期稳定性。

现实生日可能不均匀，家庭成员等人群也可能存在相关性。我们得到的数值对应的是明确的独立均匀模型。随机编号和散列碰撞可以使用相同的数学结构，但同样要先检查“均匀”和“独立”是否适用。

把一次完整的建模过程写出来

现在做一个稍微综合的题：某班十二人，其中五人会使用统计软件。在所有四人小组中均匀选一个，求组内至少一人会使用软件的概率。

先别急着搜索哪个公式带着 $12,5,4$ 。一次结果是一个四人集合，学生可区分，不重复选人，不记录角色。题目还明确了所有四人小组等可能，因此分母是 $\binom{12}4$ ，数量比可以使用。

目标事件是“至少一人会使用”。它的补集是“四人都不会使用”；不会使用的人有七个，所以补集有 $\binom74$ 个。于是

P(\text{至少一人会使用}) =1-\frac{\binom74}{\binom{12}4} =1-\frac{35}{495} =\frac{92}{99}.

这个结果较大也有直觉依据：会使用软件的人接近全班一半，而我们要选四个人，“全部避开这五人”才是较苛刻的情况。若算出了大于一或负数，模型或计算必然有问题；即使结果在零和一之间，也仍然需要核对分子分母是否数同一类对象。

如果题目改成“先随机选一个宿舍，再从该宿舍随机选四人”，那么全班所有四人小组就不再等可能，甚至有些小组根本不会出现。表面上仍然是“随机选四人”，分母却不能照旧写 $\binom{12}4$ 。决定概率的是具体的随机过程，不是句子里有没有“随机”两个字。

用练习检查自己是否真的数对了对象

验证码里的限制属于哪个位置

用 $0$ 到 $9$ 组成四位验证码，允许以零开头。求全部验证码数，以及四位互不相同的验证码数。若改成四位正整数且四位互不相同，数量又是多少？

指定对象入选，要不要再乘一个位置数

从十本不同的书中选四本带走，必须包含指定的一本。共有多少种选法？如果还要给选出的四本书排一个阅读顺序，共有多少种安排？

只选书时，指定书已经占一个名额，另外三本从剩余九本中选，所以有 $\binom93=84$ 种。指定书不需要再占据某个“选书位置”，因为一个无序集合没有位置。

有阅读顺序时，每组四本书都可以排列成 $4!=24$ 种顺序，因此有 $\binom93\cdot4!=2016$ 种安排。也可以先给指定书选四个阅读位置之一，再排列其余三个位置：。

同一个数量结果，有多少个有序记录

从 A、B、C 三张卡中独立、有放回地等概率抽三次。若只记录每张卡出现的次数，有多少种数量向量？“每张恰好出现一次”和“三次都是 A”的概率分别是多少？

超几何里的两个类别，都要够抽

盒中有八个红球、十二个白球，每次均匀抽一个，不放回，直到抽出五个。恰有两个红球的概率怎样写？如果改为抽出十八个，红球数的可能范围是什么？

“至少”什么时候该用补集

从十二名学生中均匀选四人，其中五人会使用统计软件。求恰好两人会使用软件和至少一人会使用软件的概率，并说明为什么“至少一人”的计数不能写成 $5\binom{11}3$ 。

生日问题里的两个不同目标

十个人的生日独立且均匀分布在三百六十五天。写出至少两人同生日的概率，再写出“至少有一人的生日与指定的第一个人相同”的概率。

只看点数和，为什么仍要回到完整记录

独立投掷两枚公平骰子，求点数和至少为十的概率。

隔板允许空段，才能表示某种数量为零

从六种口味中买四个冰淇淋球，只关心每种口味买了几个，允许重复。共有多少种买法？如果要求每种口味至少一个，是否还能沿用同一个公式？

做完这些题，计数公式应该已经能连成一个过程：先确定完整结果怎样产生，再决定保留什么记录；检查这些记录是否等可能，然后把事件拆成互斥的类，或者转去数补集。

但还有一种变化，我们这章一直没有正式处理：结果产生的规则没有变，只是你提前知道了一部分信息。 例如已知抽到的四人中至少一人会使用软件，再问恰好两人会使用的概率；或者已知两枚骰子的点数和至少为十，再问有没有一枚掷出了六。原来的计数仍然有用，但我们比较的范围变了。下一章的条件概率，就是把这种“知道以后，应该在哪一批结果里重新算比例”写成严格的规则。

d/2

\binom{5}{2}

)

=

10

\binom52=10

1-\left(\frac{364}{365}\right)^9.