手册 · 第 3 章

计数与概率

阶乘、排列与组合、计数策略、隔板法、二项式恒等式、概率、期望值与容斥原理。

原书第 46–59 页 · 54 个条目

3.1 基本定义

定义 3.1.1

一个正整数的阶乘，是所有小于或等于它的正整数的乘积。也就是说，

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

去学习:定义 1.1.1 · 阶乘第 1.1 节阶乘

原书第 46 页

定理 3.1.2 · 计数中的阶乘

把 $n$ 个物体排成一排，方法数是 $n!$ 。

把 $n$ 个物体排成一圈，如果同一种排法旋转后不算不同，方法数是 $(n-1)!$ 。

把 $n$ 个物体排成一圈，如果同一种排法的旋转和镜像都不算不同，方法数是

\frac{(n-1)!}{2} \quad (n \ge 3).

去学习:定理 1.2.2 · 物体的排序数注 1.2.3

原书第 46 页已数值验证

定义 3.1.3

组合是从一组物体中选出一些的一种方式，其中选取的顺序没有区别。

去学习:定义 1.5.1 · 组合第 1.5 节组合

原书第 47 页

定理 3.1.4 · 组合公式

从总共 $n$ 个物体中选出 $k$ 个，方法数是

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

去学习:定理 1.5.3 · 组合公式

原书第 47 页已数值验证

注 3.1.5

计算组合数的第二种方法 $\frac{n(n-1)\cdots(n-k+1)}{k!}$ ，在数学竞赛中更快。

去学习:定理 1.5.3 · 组合公式

原书第 47 页

注 3.1.6

注意：

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

这是因为选出要拿走的 $k$ 个物体（左边），等同于选出不被选中的 $n-k$ 个物体（右边）。

去学习:注 1.5.4 定理 6.1.1 · 对称性

原书第 47 页已数值验证

定义 3.1.7

排列是把一个集合中的物体排好的一种方式，其中物体的顺序是有区别的。

去学习:定义 1.2.1 · 排列第 1.2 节排列基础

原书第 47 页

定理 3.1.8 · 排列公式

从总共 $n$ 个物体中取出 $k$ 个排好，方法数是

{}^{n}P_{k} = \frac{n!}{(n-k)!}.

去学习:定理 1.2.4 · 排列公式

原书第 47 页已数值验证

注 3.1.9

通常，“排列”“顺序有关”等说法表示排列，而“选”“挑选”“不计顺序”等说法表示组合。

去学习:注 1.5.2

原书第 48 页

定理 3.1.10

一个有 $n$ 个元素的集合，子集个数是 $2^n$ 。

去学习:定理 1.6.1 · 子集的个数第 1.6 节子集

原书第 48 页已数值验证

注 3.1.11

集合的每个元素都有 2 种选择：放进子集，或者不放。这意味着其中一个子集是空集，也就是每个元素都不放。如果题目让你数子集，一定要看清空集该不该算。

去学习:注 1.6.2

原书第 48 页

3.2 计数策略

在 YouTube 上打开

注 3.2.1

**补集计数：**数出我们不想要的情况（对立面），再从总数里减掉。关键词“至少”往往提示补集计数可能有用。
**重复计数：**先多数一些，再有条理地减去不该算的部分。
**分类讨论：**把问题拆成几种情况，分别数出每种情况的方法数（或求出概率），再加起来。

分类讨论是解组合题非常有用的策略，尤其是在没有其他明显思路的时候。

去学习:概念 3.1.1 · 让情况尽量少注 3.1.2 第 3.1 节分类讨论

原书第 49 页

注 3.2.2

很多时候，分类讨论要和补集计数等其他方法一起用。

去学习:注 4.0.5 第 3.1 节分类讨论

原书第 49 页

3.3 进阶概念

在 YouTube 上打开

定理 3.3.1 · 字母重排

一个单词的字母重排方法数是

\frac{n!}{d_1! \times d_2! \times d_3! \times \cdots}

其中 $n$ 是字母个数， $d_1, d_2, d_3, \ldots$ 是单词中每个出现不止一次的字母各自出现的次数。

去学习:定理 1.4.1 · 字母重排第 1.4 节字母重排

原书第 49 页已数值验证

注 3.3.2

这不只适用于单词！排列有重复的物体（或任何东西）时，方法数也由同一个公式给出。

去学习:注 1.4.2

原书第 50 页

定理 3.3.3

在 $m \times n$ 的长方形方格中，各种大小的长方形的个数是

\binom{m+1}{2} \times \binom{n+1}{2}.

去学习:定理 7.2.1 · 方格中的长方形第 7.2 节长方形计数

原书第 50 页已数值验证

注 3.3.4

每一种“两条横线加两条竖线”的组合都围成一个唯一的长方形。 $m \times n$ 的方格一个方向有 $m+1$ 条线，另一个方向有 $n+1$ 条线，所以选两条横线有 $\binom{m+1}{2}$ 种方法，选两条竖线有 $\binom{n+1}{2}$ 种方法。

去学习:注 7.2.2

原书第 50 页已数值验证

注 3.3.5

组合计数的一个类似应用是经典问题：（凸） $n$ 边形的对角线有多少个交点（假设没有三条对角线交于同一个内部点）？一个交点由 2 条对角线产生，每条对角线由 2 个顶点确定，所以每个交点恰好对应 4 个顶点。因此交点个数就是从 $n$ 个点中选 4 个的方法数：

\binom{n}{4}.

去学习:第 7.1 节三角形计数

原书第 51 页已数值验证

定理 3.3.6 · 隔板法

把 $n$ 个相同的物品放进 $k$ 个可区分的盒子里，方法数是

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

去学习:定理 5.1.1 · 隔板法第 5.1 节隔板法基础

原书第 51 页已数值验证

注 3.3.7

之所以成立，是因为可以把它看成在 $n$ 个物品（球）之间放 $k-1$ 块隔板，排法共有

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

种。理解这一点很重要，因为题目可能会把隔板法稍加变化。

去学习:第 5.1 节隔板法基础

原书第 51 页已数值验证

注 3.3.8

隔板法非常有用，而且常常可以根据情况灵活变通。例如，如果每个盒子里至少要有 1 个物品，就先给每个盒子放 1 个，再对 $n-k$ 个物品和 $k$ 个可区分的盒子使用公式。

去学习:注 5.1.2 概念 5.2.1 · 先给够最少数第 5.2 节带限制条件的隔板法

原书第 51 页已数值验证

定理 3.3.9 · 二项式定理

对非负整数 $n$ ，

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

去学习:定理 24.0.10 · 二项式定理第 12.1 节二项式展开第 6.1 节基本恒等式

原书第 52 页已数值验证

注 3.3.10

二项式定理有很多强大的应用。它可以用来展开这样的式子：

(x+y)^n.

另外，如果要求像

(x+y)^n \pmod{x^k}

这样的式子的值（ $x$ 和 $y$ 为整数），只需展开二项式展开式的最后 $k$ 项：其余每一项都含有 $x^k$ 或 $x$ 的更高次幂。

更正

原书把模数印成了 $n^k$ ；它必须是 $x^k$ （两项之一的幂）。模 $x^k$ 时，含 $x^k, x^{k+1}, \ldots$ 的项都变成 0，只剩最后 $k$ 项。模 $n^k$ 则不成立：取 $x = 2$ ， $y = 1$ ， $n = 3$ ， $k = 1$ ， $(2+1)^3 = 27 \equiv 0 \pmod 3$ ，但最后一项是 $1$ 。