计数原理与概率公理 | 杨星宇

概率论处理随机现象。给每个合理结果配上一个数，用来反映它发生的可能性，这套框架就是概率测度。从赌博到物理、生物、经济，定量地说“有多可能”，都靠它。要度量一个事件，先得知道实验有多少种结果，其中又有多少种落在这个事件里。计数就是这块有限基础。

计数原理

基本计数原理

先看最简单的情形。一枚均匀硬币，正面反面各占一半，一共两种结果。掷两次，用 $T$ 记正面、 $F$ 记反面，四种排列是 $(T,T)$ 、 $(T,F)$ 、 $(F,T)$ 、 $(F,F)$ 。这引出乘法原理。

定理乘法原理

两个实验相继进行。第一个有 $m$ 种结果，固定第一种结果后，第二个有 $n$ 种结果。则两个实验合在一起有 $mn$ 种结果。

证明

按第一步结果把完整结果分组，得到 $m$ 个互不相交的组，每组恰有 $n$ 个结果。因此有限加法给出 $n+\cdots+n=mn$ 。各组第二步的结果不必具有相同标签，只需个数相同。这个计数命题不要求概率意义上的独立。

例年度母子

一个小社区有 $10$ 位母亲，每人有 $3$ 个孩子。要选一对“年度母子”，有多少种选法？

解年度母子

选母亲有 $m=10$ 种，再选她的一个孩子有 $n=3$ 种，共 $10\times 3=30$ 种。

掷硬币 $n$ 次，和 $n$ 个布尔变量的真值表是同一件事：每个位置两种取值，总共 $2^n$ 种。把两个实验推广到 $r$ 个，就是一般的乘法原理。

定理一般乘法原理

$r$ 个实验相继进行。第一个有 $n_1$ 种结果；对已经出现的前一种结果，第二个有 $n_2$ 种；对已经出现的前两种结果，第三个有 $n_3$ 种；依此类推。则总共有

\prod_{k=1}^r n_k = n_1 n_2 \cdots n_r

种结果。

证明

对阶段数 $r$ 归纳。 $r=1$ 时为 $n_1$ 。若前 $r$ 步有 $n_1\cdots n_r$ 个完整前缀，每个前缀又有 $n_{r+1}$ 种延续，由两阶段乘法原理得到 $n_1\cdots n_r n_{r+1}$ ，归纳完成。空序列有一种实现，对应空积为一。

这就是计数里的乘法法则，后面算概率还会再用。

定理加法原理

一件事可以走 $m$ 条路完成，也可以走另外 $n$ 条路完成，两类路互不重叠，则总共 $m+n$ 种做法。

证明

设 $A$ 、 $B$ 有限且 $A\cap B=\emptyset$ 。 $A$ 有 $n$ 个元素， $B$ 有 $m$ 个。并集把两边的元素都收进来，没有重复，所以 $|A\cup B|=n+m$ 。

例三份项目清单

学生从三份互不重复的项目清单里任选一个，三份分别有 $23$ 、 $15$ 、 $19$ 个项目。一共有多少种选法？

解三份项目清单

三类做法互斥，由加法原理： $23+15+19=57$ 。

例车牌

车牌由三个大写英文字母后接三个数字组成，字母组合不加限制。能做出多少种不同车牌？

解车牌

每个字母位置 $26$ 种，每个数字位置 $10$ 种。由乘法原理

26^3\times 10^3=17576\times 1000=17{,}576{,}000.

两类做法若有重叠，直接相加会把公共部分数两遍，必须减回来。这就是减法，也是两个集合的容斥。

全集 $U$ 里丢掉子集 $A$ ，剩下 $|U|-|A|$ 个元素。两个集合时，

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

定理容斥（两个做法）

一件事有 $n_1$ 种做法，也有 $n_2$ 种做法，则真正的种数是 $n_1+n_2$ 减去两种做法里重复的那些。

证明

把并集拆成互不相交的 $A\setminus B$ 、 $A\cap B$ 、 $B\setminus A$ 。在 $|A|+|B|$ 中，中间部分算了两次，其余各一次；减去 $|A\cap B|$ 后，每个元素恰算一次。

例非虚构书

图书馆有 $1000$ 本书，其中 $300$ 本是小说。非小说有多少本？

|U|-|A|=1000-300=700.

例茶与咖啡

“调查 $200$ 人，喜欢茶的 $120$ 人，喜欢咖啡的 $150$ 人，两者都喜欢的 $50$ 人”这组数据不可能成立：容斥给出 $120+150-50=220>200$ 。交集至少应为 $120+150-200=70$ 人。若把交集改成 $80$ 人，并集就是 $190$ 人，另有 $10$ 人两者都不喜欢。

除法原理则用来抹掉“不在乎的差别”，和等价类是同一件事。

定理除法原理

一件事有 $n$ 种做法，而且每种真正在乎的结果 $w$ 恰好对应其中 $d$ 种做法，则不同的结果有 $n/d$ 种。

证明

按最终结果把过程结果划分。若最终有 $k$ 种结果，每个原像恰好含 $d>0$ 个过程结果，互不相交的加法给出 $n=kd$ ，故 $k=n/d$ 。若各原像大小不同，就不能这样除。

例等大小的等价类

$n$ 元集被等价关系分成若干类，每类恰好 $m$ 个元素。不区分类内次序时，不同的块有 $n/m$ 个。

例图的边数

图的度数总和是 $58$ ，有多少条边？

解图的边数

每条边被度数数了两次，所以边数是 $58/2=29$ 。

鸽巢原理

$8$ 只鸽子进 $7$ 个巢，必有一巢至少两只。

定理鸽巢原理

把不少于 $k+1$ 个物体放进 $k$ 个盒子，至少有一个盒子装了两个或更多。

证明

用反证。若每个盒子最多一个物体，物体总数至多 $k$ ，与“至少 $k+1$ 个”矛盾。

定理一般鸽巢原理

把 $N$ 个物体放进 $k$ 个盒子，至少有一个盒子不少于 $\lceil N/k\rceil$ 个物体。

证明

仍用反证。若每个盒子都少于 $\lceil N/k\rceil$ 个，则每个至多 $\lceil N/k\rceil-1$ 个。总数至多

k\bigl(\lceil N/k\rceil-1\bigr).

注天花板函数

对任意实数 $x$ 有 $\lceil x\rceil\le x+1$ 。

代入 $x=N/k$ 得 $\lceil N/k\rceil\le N/k+1$ ，从而

k\bigl(\lceil N/k\rceil-1\bigr) < k\bigl(N/k+1-1\bigr) =N.

物体总数会严格小于 $N$ ，矛盾。

例生日与首字母

$367$ 人中必有两人生日相同，因为一年最多 $366$ 天。
$27$ 个英文单词中必有两个同一字母开头，因为字母只有 $26$ 个。

例同一分数至少六人

离散数学课有 $A,B,C,D,F$ 五种成绩。要保证至少六人分数相同，最少需要多少学生？

证明

要某个盒子至少 $m=6$ 个，盒子数 $k=5$ 。最坏情形是每种成绩恰好 $5$ 人，共 $25$ 人；再来一人就有一种成绩达到 $6$ 。所以最少 $26$ 人。写成不等式就是 $N>k(m-1)=25$ 。

习题

练习一般乘法原理

证明一般乘法原理。

证明

对实验个数 $r$ 归纳。 $r=1$ 时就是 $n_1$ 种。假设 $r=k$ 时有 $\prod_{i=1}^k n_i$ 种。再添第 $k+1$ 个实验，对每种已有结果又有 $n_{k+1}$ 种，于是总数再乘 $n_{k+1}$ ，得到 $\prod_{i=1}^{k+1} n_i$ 。

练习函数的个数

$m$ 元集到 $n$ 元集有多少个函数？

解函数的个数

定义域每个元素可独立选陪域里 $n$ 个象之一，共 $n^m$ 个函数。

练习单射的个数

$m$ 元集到 $n$ 元集有多少个单射？

解单射的个数

$m>n$ 时没有单射。 $m\le n$ 时，第一个原象有 $n$ 种象，第二个 $n-1$ 种，第 $k$ 个 $n-k+1$ 种，共 $n(n-1)\cdots(n-m+1)$ 个。

练习笛卡尔积的基数

证明：有限集 $A_1,\ldots,A_m$ 的笛卡尔积，其元素个数等于各集基数之积。

证明

构造一个 $m$ 元组，就是依次从 $A_i$ 里各取一个元素。由乘法原理，

|A_1\times\cdots\times A_m|=|A_1|\cdots|A_m|.

练习没有单射

$|A|=k+1$ ， $|B|=k$ 。证明不存在单射 $A\to B$ 。

解没有单射

$k+1$ 个原象进 $k$ 个象，鸽巢原理迫使某个象至少被两个原象用到，所以不可能单射。

练习扑克牌

一副 $52$ 张牌，要保证：

至少三张同花色，最少抽几张？
至少三张红心，最少抽几张？

解扑克牌

(a) 四个花色当四个盒子。抽 $8$ 张时可能每种两张；第 $9$ 张迫使某一花色达到三张。即 $\lceil N/4\rceil\ge 3$ 的最小 $N$ 是 $9$ 。

(b) 最坏情形先把另外三门各 $13$ 张共 $39$ 张抽完，再抽三张红心。要保证三张红心，最多需要 $42$ 张。

练习有限集上的关系计数

$X=\{a,b,c,d\}$ 。

$X$ 上有多少个关系？
其中多少个自反？
其中多少个既自反又对称？
其中多少个等价关系？
若 $|X|=n$ ，(1)(2)(3) 各是多少？

解有限集上的关系计数

(a) $X\times X$ 有 $16$ 个有序对，每个可在关系里或不在，共 $2^{16}$ 个关系。

(b) 对角线四个位置必须是 $1$ ，其余 $12$ 个自由，共 $2^{12}$ 。也就是 $2^{16}/2^4=2^{12}$ 。矩阵形如

R=\begin{bmatrix} 1 & a & b & c \\ d & 1 & e & f \\ g & h & 1 & i \\ j & k & l & 1 \end{bmatrix},

注矩阵里的字母

这里的 $a,\ldots,l$ 表示 $0$ 或 $1$ ，不是 $X$ 的元素。

(c) 自反且对称：对角线已定，上三角（不含对角）有 $6$ 个独立选择，共 $2^6$ 。

(d) 等价关系与划分一一对应。 $4$ 元集的划分数是 Bell 数 $B_4=15$ 。

(e) 一般 $n$ 元集：关系 $2^{n^2}$ 个，自反 $2^{n(n-1)}$ 个，自反且对称 $2^{n(n-1)/2}$ 个。

练习互素的一对

从 $1$ 到 $2n$ 中任取 $n+1$ 个互不相同的整数，证明其中必有两个互素。这个结论对只取 $n$ 个数还成立吗？

解互素的一对

把 $\{1,2\},\{3,4\},\ldots,\{2n-1,2n\}$ 看成 $n$ 个盒子。取 $n+1$ 个数，必有两个落在同一盒子，它们是相邻整数，最大公因数是 $1$ 。

取 $n$ 个数时结论不必成立：把 $2,4,\ldots,2n$ 全取来，任意两个的最大公因数至少是 $2$ 。

排列与组合

上一节的四条原理已经能算不少问题。排列、组合把“有没有次序、能不能重复”这两条再抽象一层。

计数：顺序与放回。先判断顺序是否重要、是否允许重复，再选择对应的计数规则。

先判断顺序是否重要、是否允许重复，再选择对应的计数规则。

排列

字符串 $abc$ 有 $6$ 种排法： $abc,acb,bac,bca,cab,cba$ 。每一种都叫这些字母的一个排列。 $n$ 个彼此可区分的对象，第一个位置 $n$ 种选法，第二个 $n-1$ 种，直到最后一个，总共

n(n-1)\cdots 2\cdot 1=n!.

定义全排列

$n$ 个对象的排列数为 $n!$ 。

记号阶乘

非负整数 $n$ 的阶乘是

n!=n\times(n-1)\times\cdots\times 2\times 1.

约定 $0!=1$ 。后面有一道习题专门问为什么不能是 $0$ 。

例成绩排名

概率课有 $6$ 名男生、 $4$ 名女生，考试分数两两不同。一共有多少种排名？若男生女生分开排名呢？

解成绩排名

全体一起排是 $(6+4)! = 3{,}628{,}800$ 。男女分开排，是 $6!\,4!=720\times 24=17{,}280$ 。

注阶乘的不等式

这个例子也说明：对正整数 $a$ 、 $b$ ，总有 $(a+b)!\ge a!\,b!$ 。

例PEPPER

用字母 $\mathrm{PEPPER}$ 能排出多少个不同的字符串？

解PEPPER

若三个 $\mathrm{P}$ 、两个 $\mathrm{E}$ 都加上标变成可区分的，有 $6!$ 种排法。任意一种，例如 $P_1P_2E_1P_3E_2R$ ，把三个 $\mathrm{P}$ 内部重排（ $3!$ 种）、两个 $\mathrm{E}$ 内部重排（ $2!$ 种），看起来仍是 $\mathrm{PPEPER}$ 。由除法原理，不同字符串有

\frac{6!}{3!\,2!}=60

种。

这就是有重复的排列。

定义有重复的排列

$n$ 个位置里，第 $i$ 种对象出现 $n_i$ 次（ $\sum n_i=n$ ）。不区分同种对象时，排列数为

\frac{n!}{n_1!\,n_2!\cdots n_k!}.

再看从一堆里取出若干个来排。

例可重复的三位数

用 $1,2,3,4$ 做三位数，数字用过仍可再用，能做出多少个？

解可重复的三位数

每个位置 $4$ 种，共 $4^3=64$ 。

例不可重复的三位数

同样四个数字，用过就不再用，能做出多少个三位数？

解不可重复的三位数

$4\times 3\times 2=24$ 。

第二种叫做 $r$ -排列。

定理

r

-排列

$n$ 元集的 $r$ -排列个数（ $1\le r\le n$ ）是

P(n,r)=n(n-1)\cdots(n-r+1).

也常写成 ${}^n P_r$ 。

证明

依次填有序位置。已选 $j$ 个元素后，恰剩 $n-j$ 个未用元素，与具体选了哪段互异前缀无关。把 $j=0,\ldots,r-1$ 的个数相乘，便得乘积。再从 $n!$ 中约去 $1,\ldots,n-r$ ，得到阶乘商。 $r=0$ 时恰有一个空排列，商式仍给出一。

写成闭形式：因为 $P(n,0)=1$ ，与 $n!/(n-0)!$ 一致，于是

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

推论

r

-排列的闭形式

对 $0\le r\le n$ ，

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

把开形式 $n(n-1)\cdots(n-r+1)$ 上下同乘 $(n-r)!$ 就是这个商。

组合

例无序取三个字母

从 $a,b,c,d,e$ 里不放回地取 $3$ 个字母，不讲究次序（ $ab$ 与 $ba$ 算同一种）。有多少种？

解无序取三个字母

有次序时是 $5\times 4\times 3=60$ 。每种无序组合对应 $3!$ 个有序串，除掉之后得

\frac{5\times 4\times 3}{3!}=10.

也就是 $P(5,3)/3!$ 。一般地

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

定理组合数

$n$ 个不同对象里取 $r$ 个的组合数记作 $C(n,r)$ 或 $\binom{n}{r}$ ，叫做二项式系数：

\binom{n}{r}=\frac{n!}{(n-r)!\,r!}\qquad(r\le n).

读作“ $n$ 选 $r$ ”。

证明

假设 $0\le r\le n$ 都为整数。每个无序 $r$ 元子集恰好产生 $r!$ 个不同的有序选择，所以“忘掉次序”映射的每个原像大小均为 $r!$ 。由除法原理， $\binom nr=P(n,r)/r!$ 。 $r=0$ 时使用空选择，结论仍成立。

例委员会

$5$ 名女性和 $7$ 名男性里，选 $2$ 女 $3$ 男组成委员会，有多少种？若其中两名男性不和，拒绝同席呢？

解委员会

\binom{5}{2}\binom{7}{3}=\frac{5\cdot 4}{2\cdot 1}\cdot\frac{7\cdot 6\cdot 5}{3\cdot 2\cdot 1}=350.

含那对不和男性的三人组有 $\binom{2}{2}\binom{5}{1}=5$ 种，所以不含他们的三人组有 $35-5=30$ 种，再配 $2$ 名女性：

30\times\binom{5}{2}=300.

推论对称性

$0\le r\le n$ 时， $C(n,r)=C(n,n-r)$ 。

证明

C(n,r)=\frac{n!}{r!\,(n-r)!}=C(n,n-r).

证明

组合证明：选 $r$ 个带上，等于选 $n-r$ 个留下。

例好香蕉与坏香蕉

店里 $20$ 根香蕉，其中 $19$ 根好的、 $1$ 根坏的。买 $6$ 根：要么避开那根坏的，要么带着它再配 $5$ 根好的。于是

\begin{aligned} \binom{20}{6} &= \binom{19}{6}+\binom{19}{5} \\ &= \frac{19!}{6!\,13!}+\frac{19!}{5!\,14!} = 27132+11628 = 38760. \end{aligned}

推论Pascal 恒等式

若 $0<k<n$ ，则

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

证明

\begin{aligned} \binom{n-1}{k}+\binom{n-1}{k-1} &= \frac{(n-1)!}{k!\,(n-k-1)!}+\frac{(n-1)!}{(k-1)!\,(n-k)!} \\ &= \frac{(n-k)(n-1)!}{k!\,(n-k)!}+\frac{k(n-1)!}{k!\,(n-k)!} \\ &= \frac{n!}{k!\,(n-k)!} = \binom{n}{k}. \end{aligned}

这是递归关系。组合解释：从 $n$ 个里选 $k$ 个，要么含某个指定元素（再从剩下 $n-1$ 个里选 $k-1$ 个），要么不含（从剩下 $n-1$ 个里选 $k$ 个）。

注Pascal 恒等式

这个恒等式叫做 Pascal 恒等式。链接里有组合证明。

用集合语言再看计数

四条原理、排列、组合，骨子里都是在操作集合。判断用哪一种，就看两件事：

要不要次序（排列还是组合）
能不能重复

$n$ 元集上的 $k$ -序列

定义

k

-序列

若序列 $S$ 的陪域是 $C$ ，称 $S$ 是 $C$ 上的序列。正整数 $k$ 、 $n$ 给定后， $n$ 元集上的 $k$ -序列是从 $\{1,\ldots,k\}$ 到某个 $n$ 元集 $X=\{x_1,\ldots,x_n\}$ 的函数，写成

S=(s_1,s_2,\ldots,s_k),\qquad s_j\in X.

允许重复的 $k$ -排列，就是 $n$ 元集上的 $k$ -序列，共 $n^k$ 个。例如 $\{1,2,3,4\}$ 上的 $3$ -序列有 $4^3$ 个。

不允许重复时，就是 $P(n,k)$ ：

n(n-1)\cdots(n-k+1).

例如 $6$ 元集上的 $4$ -排列有 $6\times 5\times 4\times 3=360$ 个。 $4$ 元集上的 $6$ -排列形式上会出现 $0$ 因子，个数是 $0$ ，因为取不够。

$n$ 元集的子集个数是 $2^n$ ：每个元素可以在或不在特征序列里，位置上填 $0$ 或 $1$ ，共 $2^n$ 条特征序列，也就是 $2^n$ 个子集。这是乘法原理的推论。

$n$ 元集的 $k$ -子集

不允许重复、不讲究次序，就是 $\binom{n}{k}$ 。

允许重复的组合对应多重集。从 $n$ 种里取 $k$ 个、同种可再取，种数是 $\binom{n+k-1}{k}$ 。

定义可重复组合

从 $X=\{x_1,\ldots,x_n\}$ 中取 $k$ 个、允许重复，种数为

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

证明

用星与杠。 $k$ 颗星表示取到的对象， $n-1$ 根杠把它们分成 $n$ 组。一共 $n+k-1$ 个位置，从中选 $k$ 个放星（其余放杠），正是 $\binom{n+k-1}{k}$ 。

例两种水果

水果集 $\{\text{苹果},\text{香蕉},\text{樱桃}\}$ ，可重复地取 $2$ 个：两苹果、苹果香蕉、苹果樱桃、两香蕉、香蕉樱桃、两樱桃，共

\binom{3+2-1}{2}=\binom{4}{2}=6

种。

例三色球

红、蓝、绿三色球，可重复取 $3$ 个： $\mathrm{RRR},\mathrm{RRB},\mathrm{RRG},\mathrm{RBB},\mathrm{RBG},\mathrm{RGG},\mathrm{BBB},\mathrm{BBG},\mathrm{BGG},\mathrm{GGG}$ ，共

\binom{3+3-1}{3}=\binom{5}{3}=10

种。

对照：

$n$ 元集的 $k$ -子集：不重复、无序， $\binom{n}{k}$ 。
$n$ 种的 $k$ -多重子集：可重复、无序， $\binom{n+k-1}{k}$ 。

例书与水果

$5$ 本不同的书选 $3$ 本上架（书不能重复）： $\binom{5}{3}=10$ 。 $5$ 种水果各不限量，篮子装 $3$ 个（可同种）： $\binom{5+3-1}{3}=\binom{7}{3}=35$ 。

二项式定理

Pascal 恒等式是二项式定理的根。中学里的 $(a\pm b)^2=a^2\pm 2ab+b^2$ 只是 $n=2$ 的特例。

定理二项式定理

对实数 $x$ 、 $y$ 和非负整数 $n$ ，

(x+y)^n=\sum_{k=0}^{n}\binom{n}{k}x^k y^{n-k}.

证明

对 $n$ 归纳。 $n=1$ 时两边都是 $x+y$ 。假设 $n-1$ 成立，则

(x+y)^n=(x+y)\sum_{k=0}^{n-1}\binom{n-1}{k}x^k y^{n-1-k}.

拆成两段求和，第一段令 $i=k+1$ ，第二段令 $i=k$ ，再用 Pascal 恒等式把中间系数合成 $\binom{n}{i}$ ，得到

(x+y)^n=\sum_{i=0}^{n}\binom{n}{i}x^i y^{n-i}.

更干净的组合证明见 AoPS：展开时每个因子贡献 $x$ 或 $y$ ，选 $k$ 个因子贡献 $x$ 的方式有 $\binom{n}{k}$ 种。

例低次展开

另一种常见写法是

(a+b)^n=\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k.

注两种写法

只是把 $x$ 、 $y$ 的角色对调，不是另一条定理。

\begin{aligned} (a+b)^3&=a^3+3a^2b+3ab^2+b^3, \\ (a+b)^4&=a^4+4a^3b+6a^2b^2+4ab^3+b^4, \\ (a+b)^5&=a^5+5a^4b+10a^3b^2+10a^2b^3+5ab^4+b^5. \end{aligned}

系数排成 Pascal 三角：每一位等于肩上两个之和。例如 $(a+b)^5$ 里 $a^3b^2$ 的系数 $10$ ，来自 $(a+b)^4$ 里 $a^4b$ 的 $4$ 加上 $a^3b^2$ 的 $6$ 。更多见 Pascal 三角。

子集个数也可以用二项式定理再解释一遍。

证明

大小为 $k$ 的子集有 $\binom{n}{k}$ 个，所以

\sum_{k=0}^{n}\binom{n}{k}=(1+1)^n=2^n.

多项式定理

三个以上的加项， $(a+b+c)^n$ 怎么展开？先看多项式系数。

例SUCCESS

单词 $\mathrm{SUCCESS}$ 有 $7$ 个字母： $3$ 个 $\mathrm{S}$ 、 $2$ 个 $\mathrm{C}$ ，其余各 $1$ 。不同排法

\binom{7}{3,2,1,1}=\frac{7!}{3!\,2!\,1!\,1!}=420.

例分组

$n$ 个不同对象分成 $r$ 个有标号的组，大小分别为 $n_1,\ldots,n_r$ （ $\sum n_i=n$ ），种数是

\binom{n}{n_1,\ldots,n_r} = \frac{n!}{n_1!\cdots n_r!} = \binom{n}{n_1}\binom{n-n_1}{n_2}\cdots\binom{n_r}{n_r}.

记号多项式系数

若 $n_1+\cdots+n_r=n$ ，定义

\binom{n}{n_1,\ldots,n_r}=\frac{n!}{n_1!\cdots n_r!}.

定义多项式定理

对正整数 $n$ 以及满足 $n_1+\cdots+n_k=n$ 的非负整数，

(a_1+\cdots+a_k)^n = \sum\binom{n}{n_1,\ldots,n_k}a_1^{n_1}\cdots a_k^{n_k},

求和跑遍所有这样的 $(n_1,\ldots,n_k)$ 。

归纳证明留给习题。这里只写组合证明。

证明

多项式系数 $\binom{n}{n_1,\ldots,n_k}$ 统计把 $n$ 个位置分成大小为 $n_i$ 的 $k$ 组的方法。展开 $(x_1+\cdots+x_k)^n$ 时，每个因子贡献一个 $x_i$ ，得到单项 $x_1^{n_1}\cdots x_k^{n_k}$ 的方式数正是这个系数。

这与有重复的排列是同一套数。

例

(a+b+c)^4

\begin{aligned} (a+b+c)^4 &= a^4+4a^3b+4a^3c+6a^2b^2+12a^2bc \\ &\quad+6a^2c^2+4ab^3+12ab^2c+12abc^2+4ac^3 \\ &\quad+b^4+4b^3c+6b^2c^2+4bc^3+c^4. \end{aligned}

Catalan 数

本节待撰写 / 占位标记

本小节关于 Catalan 数（ $C_n = \frac{1}{n+1}\binom{2n}{n}$ ）、Dyck 路径与合法括号序列计数的内容已列入后续撰写队列。

字符串计数

本节待撰写 / 占位标记

本小节关于字符串排列、字符重数与组合计数的内容已列入后续撰写队列。

习题

练习为什么

0!=1

课文把 $0!$ 规定成 $1$ 。为什么不能是 $0$ ？任选一种说得通的理由即可。

解为什么

0!=1

空排列只有一种：什么都不排。
递推 $n!=n(n-1)!$ 在 $n=1$ 时要求 $1=1\cdot 0!$ ，所以 $0!=1$ 。

练习一个奇怪的递推

定义 $f:\mathbb{N}_0\to\mathbb{N}_0$ 为

f(n)= \begin{cases} 1,&n=0,\\ n\cdot f\bigl(f(n-1)\bigr),&n>0. \end{cases}

$f(n)$ 是否恒等于 $n!$ ？证明或反驳。
若不是，写出 $f(n)$ 的显式，并举例说明它与 $n!$ 如何分道。

提示：对照阶乘自己的递推 $n!=n\cdot(n-1)!$ 。

解一个奇怪的递推

$f(0)=1$ ， $f(1)=1\cdot f(f(0))=f(1)$ 会自指；若约定 $f(1)=1$ ，则 $f(2)=2f(f(1))=2f(1)=2$ ， $f(3)=3f(f(2))=3f(2)=6$ ， $f(4)=4f(f(3))=4f(6)$ 。问题在于求 $f(4)$ 需要 $f(6)$ ，而 $f(6)$ 又依赖更大的值，递推并不能沿用阶乘那条链走下去。因此 $f$ 并没有被定义成处处等于阶乘的函数；阶乘的递推用的是 $f(n-1)$ ，这里却是 $f(f(n-1))$ 。

练习证明

r

-排列公式

证明：若 $1\le r\le n$ ，则 $P(n,r)=n(n-1)\cdots(n-r+1)$ 。

证明

第一位 $n$ 种，第二位 $n-1$ 种，第 $r$ 位 $n-r+1$ 种。由乘法原理即得。

练习单词重排

下列单词各有多少种字母排法？

Fluke
Propose
Mississippi
Arrange

解单词重排

用 $\dfrac{n!}{n_1!\cdots n_k!}$ 。

Fluke 无重复： $5!=120$ 。
Propose 中 $\mathrm{P}$ 两次： $\dfrac{7!}{2!}=2520$ 。
Mississippi 中 $\mathrm{S}$ 四次、 $\mathrm{I}$ 四次、 $\mathrm{P}$ 两次： $\dfrac{11!}{4!\,4!\,2!}=34650$ 。
Arrange 中 $\mathrm{A}$ 两次、 $\mathrm{R}$ 两次： $\dfrac{7!}{2!\,2!}=1260$ 。

练习辨认计数模型

回答下列问题。

$10$ 人里选主席、财务、秘书，有多少种？
$10$ 人里选一个三人小组，有多少种？
(1) 和 (2) 本质差别是什么？哪个更大？不做计算能看出来吗？
$10$ 种口味里选三勺冰淇淋（同口味可重复），有多少种？
五份不同奖品分给 Anastasia、Becky、Cadel（可以有人空手），有多少种？
六匹马跑完全程且没有并列，终点顺序有多少种？

解辨认计数模型

职位不同，用排列： $P(10,3)=10\times 9\times 8=720$ 。
无序组合： $\binom{10}{3}=120$ 。
差别就是要不要次序。排列比组合大，因为每种三人组对应 $3!$ 种职务分配。
若勺的次序也算，是 $10^3=1000$ 。若只关心口味组合，是可重复组合 $\binom{10+3-1}{3}=\binom{12}{3}=220$ 。
每份奖独立送给三人之一： $3^5=243$ 。
$6!=720$ 。

练习用二项式定理归纳证明多项式定理

用二项式定理，对加项个数作归纳，证明多项式定理。

解用二项式定理归纳证明多项式定理

$k=2$ 就是二项式定理。假设对 $k$ 成立。写

(x_1+\cdots+x_k+x_{k+1})^n = \bigl((x_1+\cdots+x_k)+x_{k+1}\bigr)^n = \sum_{i=0}^{n}\binom{n}{i}(x_1+\cdots+x_k)^{n-i}x_{k+1}^i.

内层用归纳假设展开成多项式系数，再与 $\binom{n}{i}$ 合成 $k+1$ 项的多项式系数。

概率公理

有了“有多少种结果”，就可以谈某个事件占多大份额。

样本空间与事件

掷一枚骰子，结果写成 $S=\{1,2,3,4,5,6\}$ ，掷出 $3$ 的可能性是 $1/|S|=1/6$ 。 $S$ 叫做样本空间，掷出 $3$ 是一个事件，事件是样本空间的子集。

定义样本空间

实验或随机试验的样本空间 $S$ 是全部可能结果的集合。这些结果互斥，并且合在一起穷尽所有可能性。

定义事件

事件是 $S$ 的任意子集，表示若干可能结果的汇集。可以空（空事件 $\emptyset$ ），也可以是整个 $S$ 。

例抽一张牌

标准 $52$ 张牌抽一张。样本空间有 $52$ 个元素。例如：

$D$ ：抽到 J、Q 或 K
$E$ ：抽到红心
$F$ ：抽到 A

例掷两次硬币

公平硬币掷两次。样本空间

S=\{HH,HT,TH,TT\}.

$G$ ：至少一次正面， $G=\{HH,HT,TH\}$
$H$ ：第二次是反面， $H=\{HT,TT\}$

事件也是集合，交、并照常做。上例里“至少一次正面，且第二次不是反面”就是

G\cap H=\{HT\}.

注交的简写

概率里常把 $G\cap H$ 写成 $GH$ 。

事件很多时，用 $\bigcup$ 、 $\bigcap$ 写一串运算。

记号可数并与交

事件列 $\{E_n\}_{n=1}^{\infty}$ 的并 $\bigcup_{n=1}^{\infty}E_n$ 由至少属于某个 $E_n$ 的结果组成；交 $\bigcap_{n=1}^{\infty}E_n$ 由属于每一个 $E_n$ 的结果组成。

补事件写 $H^c$ 。上例 $H^c=S\setminus H=\{HH,TH\}$ 。

例De Morgan

布尔代数和集合论里的 De Morgan 律，对任意多个事件仍成立：

\begin{aligned} \Bigl(\bigcup_{i=1}^n E_i\Bigr)^c &= \bigcap_{i=1}^n E_i^c, \\ \Bigl(\bigcap_{i=1}^n E_i\Bigr)^c &= \bigcup_{i=1}^n E_i^c. \end{aligned}

注补的几种写法

$S^c$ 、 $S'$ 、 $\overline{S}$ 表示同一件事。

概率公理

口语里“概率就是机会大小”，数学上要先给定义。两种常见说法如下。

定义频率极限

若事件 $E$ 在 $n$ 次试验里出现 $n_E$ 次，且极限存在，则

P(E)=\lim_{n\to\infty}\frac{n_E}{n}.

定义古典概型

若样本空间有限且每个结果等可能，则

P(E)=\frac{|E|}{|S|}.

Kolmogorov 在 $1933$ 年给出的三条公理，是现代概率的骨架。满足这些公理的系统都叫做概率空间。

公理非负性

对样本空间 $S$ 中任意事件 $E$ ，

0\le P(E)\le 1.

公理规范性

P(S)=1.

公理可数可加性

对两两不交的事件列 $\{E_i\}$ ，

P\Bigl(\bigcup_{i=1}^{\infty}E_i\Bigr)=\sum_{i=1}^{\infty}P(E_i).

由公理立刻得到若干命题。

命题补事件

P(E^c)=1-P(E).

证明

$S$ 剖成 $E$ 与 $E^c$ 两块，不相交，所以 $P(S)=P(E)+P(E^c)=1$ 。

命题单调性

若 $E\subseteq F$ ，则 $P(E)\le P(F)$ 。

证明

$F=E\cup(F\setminus E)$ ，两块不相交，所以 $P(F)=P(E)+P(F\setminus E)$ 。后一项非负，故 $P(E)\le P(F)$ 。

命题两个事件的容斥

P(E\cup F)=P(E)+P(F)-P(E\cap F).

证明

$E\cup F=E\cup(F\setminus E)$ ，两块不相交。而 $P(F\setminus E)=P(F)-P(E\cap F)$ 。

集合论里的容斥可以写成对所有非空下标子集交替求和。

定理一般容斥（基数）

对有限集 $A_1,\ldots,A_n$ ，

\left|\bigcup_{i=1}^{n}A_i\right| = \sum_{\emptyset\neq I\subseteq[n]}(-1)^{|I|+1}\left|\bigcap_{i\in I}A_i\right|.

证明

在全集 $X$ 上令 $f_i$ 为 $A_i$ 的特征函数，

F(x)=\prod_{i=1}^{n}(1-f_i(x)).

$F(x)=1$ 当且仅当 $x$ 不属于任何 $A_i$ 。展开乘积：

F(x)=\sum_{I\subseteq[n]}(-1)^{|I|}\prod_{i\in I}f_i(x).

对 $x\in X$ 求和，左边是 $|X\setminus\bigcup A_i|$ ，右边是各重交的交替和。整理后即得容斥。

概率版本不必另证。

定理一般容斥（概率）

P\Bigl(\bigcup_{i=1}^{n}A_i\Bigr) = \sum_{\emptyset\neq I\subseteq[n]}(-1)^{|I|+1}P\Bigl(\bigcap_{i\in I}A_i\Bigr).

证明

示性函数逐点满足

\mathbf1_{\cup_i A_i} =1-\prod_i(1-\mathbf1_{A_i}) =\sum_{\emptyset\ne I\subseteq[n]}(-1)^{|I|+1}\mathbf1_{\cap_{i\in I}A_i}.

两边取期望就是概率公式。这里只有有限项，不涉及交换无穷级数，单个样本点概率为零的空间也同样适用。

组合地看：某个结果若恰好落在 $m>0$ 个 $A_i$ 里，它对并的概率贡献一次。在容斥展开里它被加 $\binom{m}{1}$ 次、减 $\binom{m}{2}$ 次，如此交替。因为

\sum_{i=0}^{m}\binom{m}{i}(-1)^i=(1-1)^m=0,

所以从 $i=1$ 加到 $m$ 恰好等于 $1$ 。每个结果被正确地点了一次。

习题

练习Boole 不等式

证明 Boole 不等式：对有限样本空间中的事件 $E_1,\ldots,E_n$ ，

P\Bigl(\bigcup_{i=1}^n E_i\Bigr)\le\sum_{i=1}^n P(E_i).

定理Boole 不等式

P\Bigl(\bigcup_{i=1}^n E_i\Bigr)\le\sum_{i=1}^n P(E_i).

证明

对 $n$ 归纳。 $n=1$ 显然。假设对 $n$ 成立。则

P\Bigl(\bigcup_{i=1}^{n+1}E_i\Bigr) = P\Bigl(\bigl(\bigcup_{i=1}^{n}E_i\bigr)\cup E_{n+1}\Bigr) \le P\Bigl(\bigcup_{i=1}^{n}E_i\Bigr)+P(E_{n+1}),

再用归纳假设。

证明

两个事件时， $P(E_1\cup E_2)=P(E_1)+P(E_2)-P(E_1\cap E_2)\le P(E_1)+P(E_2)$ 。再对个数归纳，或者直接看一般容斥里后面那些交都带着符号，整体不会超过第一项之和。

注何时取等

当且仅当诸 $E_i$ 两两不交时等号成立，此时交的概率全是 $0$ ，可加性给出等式。

练习灌铅骰子

一枚六面骰，掷出 $3$ 的可能性是掷出其他某个指定点数的两倍。求各面概率。

解灌铅骰子

设 $p(3)=2p(1)$ ，且 $p(1)=p(2)=p(4)=p(5)=p(6)$ 。总和为 $1$ ：

5p(1)+2p(1)=1\implies p(1)=\frac17,\qquad p(3)=\frac27.

练习并与交的下界

$p(E)=0.8$ ， $p(F)=0.6$ 。证明 $p(E\cup F)\ge 0.8$ 且 $p(E\cap F)\ge 0.4$ 。

解并与交的下界

$p(E\cup F)=0.8+0.6-p(E\cap F)\le 1$ ，故 $p(E\cap F)\ge 0.4$ 。另一方面 $E\subseteq E\cup F$ ，所以 $p(E\cup F)\ge p(E)=0.8$ 。

练习Bonferroni 不等式

证明：对事件 $E$ 、 $F$ ，

p(E\cap F)\ge p(E)+p(F)-1.

定理Bonferroni 不等式

p(E\cap F)\ge p(E)+p(F)-1.

证明

$p(E\cup F)=p(E)+p(F)-p(E\cap F)\le 1$ ，移项即得。

练习一般 Bonferroni 不等式

用归纳把 Bonferroni 不等式推到 $n$ 个事件：

P\Bigl(\bigcap_{i=1}^n E_i\Bigr)\ge\sum_{i=1}^n P(E_i)-(n-1).

也可用容斥另证。

定理一般 Bonferroni 不等式

P\Bigl(\bigcap_{i=1}^n E_i\Bigr)\ge\sum_{i=1}^n P(E_i)-(n-1).

证明

弱归纳。 $n=2$ 就是 Bonferroni。假设对 $k$ 成立。把前 $k$ 个的交与 $E_{k+1}$ 再用二元 Bonferroni：

P\Bigl(\bigl(\bigcap_{i=1}^k E_i\bigr)\cap E_{k+1}\Bigr) \ge P\Bigl(\bigcap_{i=1}^k E_i\Bigr)+P(E_{k+1})-1,

代入归纳假设即得 $k+1$ 的情形。

证明

强归纳可以从 $n=1$ （此时右边是 $P(E_1)$ ）起，步骤相同。

注弱归纳与强归纳

弱归纳只假设 $n=k$ ，强归纳假设所有更小的情形。问题只依赖前一步时，弱归纳更干净；需要整段历史时，用强归纳。

证明

用容斥。

P\Bigl(\bigcap_{i=1}^n E_i\Bigr) = 1-P\Bigl(\bigcup_{i=1}^n E_i^c\Bigr) \ge 1-\sum_{i=1}^n P(E_i^c) = 1-\sum_{i=1}^n\bigl(1-P(E_i)\bigr) = \sum_{i=1}^n P(E_i)-(n-1).

练习可数可加性作为极限

设 $E_1,E_2,\ldots$ 两两不交。通过取极限证明

p\Bigl(\bigcup_{i=1}^\infty E_i\Bigr)=\sum_{i=1}^\infty p(E_i).

解可数可加性作为极限

有限可加性给出 $p(\bigcup_{i=1}^n E_i)=\sum_{i=1}^n p(E_i)$ 。并随着 $n$ 递增，由概率的下连续性，

p\Bigl(\bigcup_{i=1}^\infty E_i\Bigr) = \lim_{n\to\infty}p\Bigl(\bigcup_{i=1}^n E_i\Bigr) = \sum_{i=1}^\infty p(E_i).

练习两个骰子上的事件

掷两枚骰子。 $E$ 为点数之和为奇数， $F$ 为至少一枚是 $1$ ， $G$ 为和为 $5$ 。描述 $EF$ 、 $E\cup F$ 、 $FG$ 、 $EF^c$ 、 $EFG$ 。

解两个骰子上的事件

$EF$ ：和为奇数且至少一枚是 $1$ ，即 $\{(1,2),(1,4),(1,6),(2,1),(4,1),(6,1)\}$ 。
$E\cup F$ ：和为奇数，或至少一枚是 $1$ 。
$FG$ ：至少一枚是 $1$ 且和为 $5$ ，即 $\{(1,4),(4,1)\}$ 。
$EF^c$ ：和为奇数且没有一枚是 $1$ 。
$EFG$ ：与 $FG$ 相同，因为和为 $5$ 已经是奇数。

练习三家报纸

某镇 $100{,}000$ 人，三家报纸 I、II、III 的阅读比例为：I $10\%$ ，II $30\%$ ，III $5\%$ ；I 与 II $8\%$ ，I 与 III $2\%$ ，II 与 III $4\%$ ；三家都看 $1\%$ 。

只看一家的人数
至少看两家的人数
若 I、III 是早报，II 是晚报，至少看一份早报再加晚报的人数
谁也不看的人数
只看一份早报加一份晚报的人数

解三家报纸

\begin{aligned} |I|&=10{,}000,& |II|&=30{,}000,& |III|&=5{,}000, \\ |I\cap II|&=8{,}000,& |I\cap III|&=2{,}000,& |II\cap III|&=4{,}000, \\ |I\cap II\cap III|&=1{,}000. \end{aligned}

只看 I： $10{,}000-(8{,}000+2{,}000-1{,}000)=1{,}000$ 。只看 II： $19{,}000$ 。只看 III： $0$ 。

$1{,}000+19{,}000+0=20{,}000$ 。
$8{,}000+2{,}000+4{,}000-2\times 1{,}000=12{,}000$ 。
至少一份早报加晚报对应 $(I\cap II)\cup(III\cap II)$ 。三家都看的读者只能计一次，因此人数为 $8{,}000+4{,}000-1{,}000=11{,}000$ 。
看报总人数用容斥： $10{,}000+30{,}000+5{,}000-8{,}000-2{,}000-4{,}000+1{,}000=32{,}000$ ，谁也不看的人数为 $100{,}000-32{,}000=68{,}000$ 。
恰好一份早报加晚报必须排除三家都看的读者：只看 I、II 的有 $7{,}000$ 人，只看 III、II 的有 $3{,}000$ 人，合计 $10{,}000$ 。

第 3 问允许两份早报都看，第 5 问要求恰好一份早报；两问都统计人数，所以每位读者只能计一次。

练习队员的职业与党派

$15$ 名队员，每人 $2$ 种职业、 $3$ 种政治归属。

样本空间有多少个结果？
“至少一名蓝领”有多少个结果？
“没有人自认为独立人士”有多少个结果？

解队员的职业与党派

每人 $2\times 3=6$ 种组合，全体 $6^{15}$ 。

全是白领时每人只剩 $3$ 种党派，故至少一名蓝领： $6^{15}-3^{15}$ 。

没有独立人士时每人 $2$ 种职业 $\times$ $2$ 种党派，共 $4^{15}$ 。

练习两点数之和

掷两枚骰子，点数之和等于 $i$ 的概率， $i=2,3,\ldots,12$ 。

解两点数之和

总共 $36$ 种等可能结果。和为 $2$ 到 $12$ 的方式数依次是 $1,2,3,4,5,6,5,4,3,2,1$ 。例如和为 $7$ 有 $6$ 种，概率 $6/36=1/6$ 。

练习5 先于 7

反复掷一对骰子，直到出现和为 $5$ 或和为 $7$ 。求先出现 $5$ 的概率。

解5 先于 7

和为 $5$ 有 $4$ 种，和为 $7$ 有 $6$ 种，所以单次 $P(5)=4/36=1/9$ ， $P(7)=6/36=1/6$ 。

$E_n$ 的概率

记 $E_n$ 为：前 $n-1$ 次既没有 $5$ 也没有 $7$ ，第 $n$ 次出现 $5$ 。单次既不是 $5$ 也不是 $7$ 的概率是 $26/36=13/18$ ，于是

P(E_n)=\Bigl(\frac{26}{36}\Bigr)^{n-1}\cdot\frac{4}{36}.

对 $P(E_n)$ 求和

\sum_{n=1}^{\infty}P(E_n) = \frac{4/36}{1-26/36} = \frac{4}{10} = \frac{2}{5}.

练习Bell 数

集合 $S$ 的划分是一族互不相交的非空子集，并起来等于 $S$ 。记 $T_n$ 为 $\{1,\ldots,n\}$ 的划分个数。已知 $T_1=1$ ， $T_2=2$ 。

列出全部划分，验证 $T_3=5$ ， $T_4=15$ 。
证明 $T_{n+1}=1+\sum_{k=1}^{n}\binom{n}{k}T_k$ ，并由此算 $T_{10}$ 。

注Bell 数

$T_n$ 就是 Bell 数，清点 $n$ 元集的划分。

解Bell 数

(a) $T_3$ ：整块一块； $1$ 单独、另两个一起（三种）；三个都单独。共 $5$ 。

$T_4$ ：整块； $1+3$ 型四种； $2+2$ 型三种； $2+1+1$ 型六种；四个单点。共 $15$ 。

(b) 把 $n+1$ 当作特殊元素。它若独自成块，剩下 $T_n$ 种。它若与某 $k$ 个元素同块（ $1\le k\le n$ ），先从 $n$ 个里选这 $k$ 个，剩下 $n-k$ 个有 $T_{n-k}$ 种划分。约定 $T_0=1$ ，可改写成

T_{n+1}=1+\sum_{k=1}^{n}\binom{n}{k}T_k.

递推得 $T_5=52$ ， $T_6=203$ ， $T_7=877$ ， $T_8=4140$ ， $T_9=21147$ ， $T_{10}=115975$ 。

用计数求概率

许多问题假定样本空间里每个结果等可能。此时

P(E)=\frac{|E|}{|S|},

分子分母都可以用前面的计数方法来算。套公式之前仍要先想清楚：什么算不同的结果。

一些基本问题

例和为 7

掷两枚骰子，点数之和为 $7$ 的概率？

解和为 7

$36$ 种等可能结果，有利的是 $\{(1,6),(2,5),(3,4),(4,3),(5,2),(6,1)\}$ ，共 $6$ 种，概率 $6/36=1/6$ 。

例委员会里的男女

$6$ 男 $9$ 女，随机选 $5$ 人委员会。恰好 $3$ 男 $2$ 女的概率？

解委员会里的男女

\binom{6}{3}=20, \qquad \binom{9}{2}=36, \qquad \binom{15}{5}=3003,

所求

P=\frac{20\times 36}{3003}=\frac{720}{3003}=\frac{240}{1001}\approx 0.2398.

例特殊球

罐中 $n$ 个球，其中一个特别。不放回地取 $k$ 个，每次剩下的球等可能。特殊球被取到的概率？

解特殊球

P=\frac{\binom{n-1}{k-1}}{\binom{n}{k}}=\frac{k}{n}.

另一种算法：记 $A_i$ 为特殊球在第 $i$ 次被抽到， $P(A_i)=1/n$ ，诸 $A_i$ 不交，于是 $P(\bigcup_{i=1}^k A_i)=k/n$ 。

例三项运动

俱乐部里打网球 $36$ 人，壁球 $28$ 人，羽毛球 $18$ 人；网球且壁球 $22$ 人，网球且羽毛球 $12$ 人，壁球且羽毛球 $9$ 人，三项都会 $4$ 人。至少参加一项的有多少人？

解三项运动

随机抽一名会员，令 $P(C)$ 为抽到的人属于集合 $C$ 的概率。容斥给出

P(T\cup S\cup B) = \frac{36+28+18-22-12-9+4}{N} = \frac{43}{N},

所以有 $43$ 人至少参加一项。

再深入一些的问题

下面几题更绕，适合当作选做。

例桥牌

$52$ 张牌分给 $4$ 人。求：

有一人拿齐 $13$ 张黑桃的概率
每人恰好一张 A 的概率

解桥牌

(a) 记 $E_i$ 为第 $i$ 家拿齐黑桃。四家互斥，且

P(E_i)=\frac{1}{\binom{52}{13}}, \qquad P\Bigl(\bigcup_{i=1}^{4}E_i\Bigr)=\frac{4}{\binom{52}{13}}\approx 6.3\times 10^{-12}.

(b) 先把 $4$ 张 A 放在一边，其余 $48$ 张按每人 $12$ 张来分，有 $\binom{48}{12,12,12,12}$ 种；A 再按 $4!$ 种方式每人一张。总发牌方式 $\binom{52}{13,13,13,13}$ 。于是

\frac{4!\,\binom{48}{12,12,12,12}}{\binom{52}{13,13,13,13}}\approx 0.105.

例室友

球队 $20$ 名进攻队员、 $20$ 名防守队员，随机两两配对住。没有“进攻-防守”混合室友对的概率？

解室友

$40$ 人分成 $20$ 个无序对，种数是 $\dfrac{40!}{2^{20}\,20!}$ 。进攻内部互配、防守内部互配的种数是 $\bigl(\dfrac{20!}{2^{10}\,10!}\bigr)^2$ 。于是

P_0 = \frac{\bigl(20!/(2^{10}\,10!)\bigr)^2}{40!/(2^{20}\,20!)} = \frac{(20!)^3}{(10!)^2\,(40!)}.

例生日问题

房间里 $n$ 个人，没有两人生日相同的概率？ $n$ 要多大，这个概率才小于 $1/2$ ？

解生日问题

忽略闰日，总共 $365^n$ 种生日指派。没有重复的概率是

P=\frac{365\times 364\times\cdots\times(365-n+1)}{365^n}.

$n\ge 23$ 时 $P<1/2$ 。 $23$ 远小于 $365$ ，但一对对来看已有 $\binom{23}{2}=253$ 对。 $n=50$ 时至少两人同日的概率约 $0.970$ ； $n=100$ 时优势超过三百万比一。

例圆桌夫妇

$10$ 对夫妇随机坐圆桌，没有一对夫妇女邻座的概率？

解圆桌夫妇

记 $E_i$ 为第 $i$ 对邻座。所求是 $1-P(\bigcup_{i=1}^{10}E_i)$ 。圆桌 $20$ 人有 $19!$ 种排法。指定 $n$ 对必须邻座时，把每对捆成一块有 $2^n$ 种朝向，剩下 $20-n$ 块（把每对看成一人）绕圆排有 $(19-n)!$ 种，于是

P(E_{i_1}\cdots E_{i_n})=\frac{2^n(19-n)!}{19!}.

代入容斥，没有一对邻座的概率约 $0.3395$ 。

习题

练习

(i,j)

-可分等差数列

设 $m$ 为正整数， $a_1,\ldots,a_{4m+2}$ 是公差非零的等差数列。若任意去掉两项 $a_i,a_j$ （ $i<j$ ）后，剩下 $4m$ 项能分成 $m$ 组、每组四个数仍成等差，则称原数列为 $(i,j)$ -可分数列。

写出使 $a_1,\ldots,a_6$ 成为 $(i,j)$ -可分数列的全部 $(i,j)$ ， $1\le i<j\le 6$ 。
证明 $m\ge 3$ 时， $a_1,\ldots,a_{4m+2}$ 是 $(2,13)$ -可分数列。
从 $1,2,\ldots,4m+2$ 中随机取两个整数 $i<j$ ，记原数列为 $(i,j)$ -可分的概率为 $p_m$ 。证明 $p_m>1/8$ 。

解

(i,j)

-可分等差数列

(1) 去掉开头两项、末尾两项，或首尾各一项，剩下四个数仍成等差。于是 $(1,2)$ 、 $(5,6)$ 、 $(1,6)$ 。

(2) 公差为 $d$ 时 $a_n=a_1+(n-1)d$ 。 $m>3$ 时，下标 $15$ 以后的连续四项本身已成等差，只需检查前 $14$ 项。取公差 $3d$ 的三组

\{a_1,a_4,a_7,a_{10}\},\quad \{a_3,a_6,a_9,a_{12}\},\quad \{a_5,a_8,a_{11},a_{14}\}

覆盖去掉 $a_2$ 、 $a_{13}$ 之后的前 $12$ 项，后面按四项一组切即可。公差 $2d$ 组不起来，但 $3d$ 已经够用。

(3) 可分的 $(i,j)$ 由两组底样生成： $(1,2)$ 与 $(2,9)$ （后者在 $m=2$ 时出现），再沿下标平移 $4$ 的倍数。表中打勾的位置给出计数 $(m+1)^2-m$ 。总选法 $\binom{4m+2}{2}$ ，于是

p_m=\frac{m^2+m+1}{8m^2+6m+1}.

令 $g(m)=p_m-1/8$ ，则

g(m)=\frac{2m+7}{8(8m^2+6m+1)}>0

对一切正整数 $m$ 成立。

$m\le 3$ 与 $m\le 5$ 的 $(i,j)$ 表如下（列为较小下标 $1,5,9,\ldots$ ，行为 $2,6,10,\ldots$ ）。

$m\le 3$ ：

	1	5	9	13
2	✓		✓	✓
6	✓	✓		✓
10	✓	✓	✓
14	✓	✓	✓	✓

$m\le 5$ ：

	1	5	9	13	17	21
2	✓		✓	✓	✓	✓
6	✓	✓		✓	✓	✓
10	✓	✓	✓		✓	✓
14	✓	✓	✓	✓		✓
18	✓	✓	✓	✓	✓
22	✓	✓	✓	✓	✓	✓

	1	5	9	13	17	21
2	✓		✓	✓	✓	✓
6	✓	✓		✓	✓	✓
10	✓	✓	✓		✓	✓
14	✓	✓	✓	✓		✓
18	✓	✓	✓	✓	✓
22	✓	✓	✓	✓	✓	✓

	1	5	9	13	17	21
2	✓		✓	✓	✓	✓
6	✓	✓		✓	✓	✓
10	✓	✓	✓		✓	✓
14	✓	✓	✓	✓		✓
18	✓	✓	✓	✓	✓
22	✓	✓	✓	✓	✓	✓

计数原理

基本计数原理

鸽巢原理

习题

排列与组合

排列

组合

用集合语言再看计数

nnn 元集上的 kkk-序列

nnn 元集的 kkk-子集

二项式定理

多项式定理

Catalan 数

字符串计数

习题

概率公理

样本空间与事件

概率公理

习题

EnE_nEn​ 的概率

对 P(En)P(E_n)P(En​) 求和

用计数求概率

一些基本问题

再深入一些的问题

习题

评论

$n$ 元集上的 $k$ -序列

$n$ 元集的 $k$ -子集

$E_n$ 的概率

对 $P(E_n)$ 求和

	1	5	9	13	17	21
2	✓		✓	✓	✓	✓
6	✓	✓		✓	✓	✓
10	✓	✓	✓		✓	✓
14	✓	✓	✓	✓		✓
18	✓	✓	✓	✓	✓
22	✓	✓	✓	✓	✓	✓