组合计数与等可能模型

很多概率题看起来是在考公式，其实先考的是建模。你要先说清楚一次试验的样本点是什么，再判断这些样本点是否等可能。只有这一步成立，后面的排列、组合、超几何和生日问题才是“数有多少种”的工作。

等可能模型概念导图，从现实问题到样本空间、等可能检查、组合计数和概率结果 — 等可能模型的关键不是套公式，而是先确认样本点是否同权重，再用有利样本点数除以全部样本点数。

等可能模型先看样本点

有限样本空间记为 $\Omega$ 。如果 $\Omega$ 中每个样本点发生的概率都相同，就可以用等可能模型：

P(A)=\frac{|A|}{|\Omega|}

这里的 $|\Omega|$ 是全部样本点个数， $|A|$ 是事件 $A$ 包含的样本点个数。这个公式本身很短，难点在于：什么才算一个样本点。

掷两个公平骰子时，把结果写成有序对 $(i,j)$ ，其中 $i$ 是第一个骰子的点数， $j$ 是第二个骰子的点数。这样共有 $6\cdot 6=36$ 个样本点，而且等可能。事件“点数和为 8”对应

\{(2,6),(3,5),(4,4),(5,3),(6,2)\}

所以概率是

P(\text{点数和为 }8)=\frac{5}{36}

如果把样本点粗略写成“点数和是 $2,3,\dots,12$ ”，就会出错，因为这些和并不等可能。和为 7 的方式有 6 种，和为 2 的方式只有 1 种。

等可能不是“结果名称看起来差不多”，而是每个样本点在模型中有相同概率。遇到计数题时，先问自己：我正在数的对象，真的彼此等可能吗？

乘法原理与加法原理

计数的第一层工具是乘法原理和加法原理。乘法原理用于分阶段完成一件事：第一步有 $a$ 种选择，第二步在每个第一步之后都有 $b$ 种选择，那么总数是 $ab$ 。如果有 $k$ 个阶段，就把每个阶段的选择数相乘。

加法原理用于互不重叠的分类：一件事可以由若干种互斥情形完成，第一类有 $a$ 种，第二类有 $b$ 种，那么总数是 $a+b$ 。如果分类会重叠，就要用容斥或改用不重叠的分块。

例如一个四位验证码，每一位可以是 $0$ 到 $9$ 的数字，允许重复。若验证码可以以 $0$ 开头，样本点就是长度为 4 的数字序列。四个位置各有 10 种选择，所以总数是

10^4

如果要求四位数字互不相同，第一位有 10 种，第二位剩 9 种，第三位剩 8 种，第四位剩 7 种，总数变成

10\cdot 9\cdot 8\cdot 7

如果再要求不能以 $0$ 开头，就不能直接套上一个现成公式。第一位有 9 种选择，后面三位从剩下的 9 个数字中依次选，所以总数是

9\cdot 9\cdot 8\cdot 7

这类例子说明，乘法原理不是机械相乘，而是每一步都要把题目限制带进去。

排列、组合与除重

从 $n$ 个不同对象中取出 $k$ 个，并且顺序有意义，得到的是排列。若不允许重复，排列数是

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

如果顺序没有意义，得到的是组合。每一个 $k$ 元集合可以被排成 $k!$ 个不同顺序，所以组合数是

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

排列与组合除重示意图：甲乙丙三张卡片在编号座位中顺序不同算不同，在无序小组中顺序不同仍是同一组，并说明组合数要除以 k! — 同一小组会被排列 $k!$ 次，因此组合数等于排列数除以 $k!$ 。

看一个小题。8 名同学中选 3 人参加讨论小组，组内不分角色。因为只关心“哪 3 人入选”，不关心写出的顺序，所以有

\binom{8}{3}=56

如果选出 3 人后还要指定组长、记录员、汇报人三个不同角色，那么顺序或角色有意义。可以先选人再分配角色：

\binom{8}{3}\cdot 3!=56\cdot 6=336

也可以直接看成从 8 人中依次选组长、记录员、汇报人：

8\cdot 7\cdot 6=336

两种做法得到同一个数。前一种更能看清“先组合、再排列”的结构；后一种更适合角色已经天然有顺序的题。

判断排列还是组合时，不要只看题目里有没有“排列”“组合”这几个字。更可靠的问题是：同样的一批对象换一个顺序，题目是否把它当成新的结果？

四种抽样模型

组合计数中最常见的混淆来自两个开关：是否看顺序，是否允许重复。把这两个开关放在一起，许多题会自动落到四种模型之一。

模型	样本点形态	计数公式	常见场景
有序、有放回	长度为 $k$ 的序列，对象可重复	$n^k$	密码、连续掷骰子
有序、无放回	长度为 $k$ 的序列，对象不重复	$P(n,k)$	排名、不同岗位分配
无序、无放回	$k$ 元子集

有序、有放回最直接。每次选择都有 $n$ 种，做 $k$ 次，所以是 $n^k$ 。例如 6 次投掷公平硬币，完整样本点是一个长度为 6 的正反序列，共有 $2^6$ 种。

有序、无放回会随着选择进行减少可选对象。第一次有 $n$ 种，第二次有 $n-1$ 种，一直到第 $k$ 次有 $n-k+1$ 种。

无序、无放回是普通组合。5 张扑克牌手牌通常不区分拿到的先后顺序，所以总手牌数是 $\binom{52}{5}$ ，不是 $52\cdot 51\cdot 50\cdot 49\cdot 48$ 。后者把同一手牌的 $5!$ 个拿牌顺序都算了进去。

无序、有放回稍微不直观。比如从苹果、梨、桃 3 种水果中买 5 个，只关心每种买了几个。令三个数量分别是 $x_1,x_2,x_3$ ，就有

x_1+x_2+x_3=5,\quad x_1,x_2,x_3\ge 0

把 5 个“水果名额”和 2 个分隔符排在一起，就得到

\binom{5+3-1}{3-1}=\binom{7}{2}

一般地，从 $n$ 种对象中无序、可重复地取 $k$ 个，方案数是

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

等可能模型里的分块与补集

计数不一定要正面硬数。有时事件由多个互斥情形组成，适合分块；有时事件的补集更简单，适合先数反面。

例如从 52 张扑克牌中抽 5 张，求“恰有 2 张 A”的概率。样本空间是所有 5 张手牌：

|\Omega|=\binom{52}{5}

事件中要从 4 张 A 里选 2 张，再从 48 张非 A 里选 3 张，所以

|A|=\binom{4}{2}\binom{48}{3}

概率为

P(A)=\frac{\binom{4}{2}\binom{48}{3}}{\binom{52}{5}}

如果题目问“至少 1 张 A”，直接分成恰有 1 张、2 张、3 张、4 张也可以，但补集更短。补集是“没有 A”，所以

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

遇到“至少一个”“没有重复”“没有坏件”“没有同生日”这类说法时，先看看补集是否更容易数。很多看起来复杂的概率，反过来只是一条乘法链或一个组合数。

超几何：不放回抽样中的成功个数

超几何模型描述的是有限总体中的无放回抽样。总体有 $N$ 个对象，其中 $K$ 个带有某种特征，通常叫“成功”。从总体中不放回地抽 $n$ 个，令 $X$ 表示抽到的成功个数。

超几何分布示意图：从含有K个成功蓝球和N-K个其他灰球的有限总体中不放回抽取n个，样本中有x个成功 — 超几何分布描述有限总体中不放回抽样时成功个数的概率。

要得到 $X=x$ ，需要从 $K$ 个成功对象中选 $x$ 个，再从 $N-K$ 个非成功对象中选 $n-x$ 个。样本空间是从 $N$ 个对象中选个，所以

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

这里的 $x$ 不能随便取。它至少要满足抽到的成功个数不为负，也不能超过 $K$ 或 $n$ ；同时非成功对象也要够抽。支持集是

\max(0,n-(N-K))\le x\le \min(K,n)

看一个质检例子。一批 30 件产品中有 4 件次品，随机不放回抽查 5 件。问恰好抽到 1 件次品的概率。这里 $N=30$ ， $K=4$ ， $n=5$ ， $x=1$ ，因此

P(X=1)=\frac{\binom{4}{1}\binom{26}{4}}{\binom{30}{5}}

这个式子的结构比小数更重要：分子先选出 1 件次品，再选出 4 件合格品；分母是所有可能的 5 件抽样。

超几何和二项模型经常被混在一起。二项模型对应有放回或每次成功概率保持不变的重复试验；超几何模型对应无放回抽样，抽过一个对象后总体构成变了，下一次成功概率也跟着变。

生日问题：从不重复更容易数起

生日问题问的是：在 $m$ 个人中，至少两人生日相同的概率是多少？常见简化假设是忽略闰日，把一年看成 365 天，并且每个人生日独立且均匀分布在这 365 天上。

正面数“至少一对同生日”会牵涉一对、两对、三人同生日等重叠情形。补集“所有生日都不同”更简单。第 1 个人可以是任意一天，第 2 个人要避开第 1 个人，第 3 个人要避开前两个人，以此类推。

生日问题互补计数信息图：365个日期格子、多人避开已占日期，并标出23人时至少两人同生日概率约0.507 — 生日问题：先数“没有同生日”的安排，再取互补，概率为 $1 - 365\cdot 364\cdot \cdots \cdot (365-m+1)/365^m$ 。

所以当 $m\le 365$ 时，

P(\text{所有生日不同}) =\frac{365\cdot 364\cdot 363\cdots(365-m+1)}{365^m}

目标概率是

P(\text{至少两人同生日}) =1-\frac{365\cdot 364\cdot 363\cdots(365-m+1)}{365^m}

当 $m=23$ 时，这个概率约为 $0.507$ 。直觉上 23 比 365 小很多，但真正参与比较的是人和人之间的配对数：

\binom{23}{2}=253

253 次潜在比较已经不少，所以碰撞比初看时更容易发生。

生日问题也提醒我们，等可能模型要写清楚假设。现实中的生日并不完全均匀，出生日期也可能有季节性差异；不过在入门模型里，均匀独立假设能把“碰撞”这个结构讲清楚。以后遇到哈希冲突、随机分桶、编号重复等问题，也会看到同一类思路。

套公式前的检查清单

计数题套公式前的中文检查清单，依次检查样本点、等可能、顺序、重复、限制条件以及补集或分块 — 套公式前先判断样本点、等可能性、顺序、重复与限制条件，再选择合适的计数方法。

很多计数错误不是算错，而是在第一步选错了样本空间。做题前可以按下面的顺序检查。

样本点是什么？是一串有顺序的记录，还是一个无序集合，还是一个数量向量？
样本点是否等可能？如果不等可能，不能只用“数量比数量”。
是否看顺序？换一个顺序是否算新的结果？
是否允许重复？抽过的对象会不会放回，或者同一类对象能否多次出现？
限制条件是什么？题目说的是恰好、至少、至多，还是不能相邻、必须包含某对象？
能否用补集或分块？反面事件是否更短，分类是否互斥？

“从盒中抽 3 个球”这句话本身还不够完整。要继续确认：是一次抽出还是依次抽出？记录顺序吗？抽后放回吗？球是否可区分？这些选择会改变样本空间，也会改变公式。

下面用一个小例子把检查过程写完整。

题目：某班 12 人中有 5 人会使用统计软件。随机选 4 人组成小组，求小组中至少 1 人会使用统计软件的概率。

样本点是 4 人小组，顺序没有意义，也没有重复选人的可能。全部样本点数是 $\binom{12}{4}$ 。

题目中的“至少 1 人会使用”可以正面分成 1 人、2 人、3 人、4 人，但补集“没有人会使用”更短。

练习

练习时先写出样本空间，再决定用哪种计数模型。下面每题都可以直接用本章的方法完成。

从 26 个英文字母中依次选 5 个，允许重复。共有多少种序列？

每个位置都有 26 种选择，并且顺序有意义、允许重复，所以共有 $26^5$ 种。

从 10 本不同的书中选 4 本带走，其中必须包含指定的一本书。共有多少种选法？

指定书已经选定，还需要从剩下 9 本中选 3 本。共有 $\binom{9}{3}$ 种。

盒中有 8 个红球和 12 个白球，一次随机取出 5 个球。恰有 2 个红球的概率是多少？

样本空间是从 20 个球中选 5 个。事件是从 8 个红球中选 2 个，同时从 12 个白球中选 3 个，所以概率是

\frac{\binom{8}{2}\binom{12}{3}}{\binom{20}{5}}

10 个人的生日独立且均匀分布在 365 天上。至少两人同生日的概率应怎样写？

先数补集“所有生日都不同”：

\frac{365\cdot 364\cdot 363\cdots 356}{365^{10}}

所以至少两人同生日的概率是

1-\frac{365\cdot 364\cdot 363\cdots 356}{365^{10}}

掷两个公平骰子，求点数和至少为 10 的概率。

样本空间是 36 个有序点数对。和至少为 10 的情形包括和为 10、11、12，分别有 3、2、1 种，所以事件个数是 6。概率为

\frac{6}{36}=\frac{1}{6}

从 6 种口味中买 4 个冰淇淋球，只关心每种口味买了几个，允许重复。共有多少种买法？

这是无序、有放回模型。设 6 种口味数量为 $x_1,\dots,x_6$ ，满足 $x_1+\cdots+x_6=4$ 且每个。方案数是

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