组合数学

组合数学研究离散对象的计数、排列、选择与结构。其核心不只是套用公式，而是确定什么算同一个对象、是否允许重复、顺序是否重要，以及怎样保证每个对象恰好被计数一次。

加法与乘法原则

若对象被分成互不重叠的几类，总数等于各类数量之和。若一个构造过程有多个阶段，而且对前面每种选择，下一阶段总有固定数量的选择，则总数为各阶段选择数的乘积。

例如从 3 件上衣和 2 条裤子中各选一件，若任意搭配都允许，共有 $3 \times 2 = 6$ 种搭配。若某些搭配被禁止，应重新划分类别或扣除禁例，不能仍机械地相乘。

排列与组合的差别

从 $n$ 个不同对象中不重复地选取 $k$ 个并排序，有 $P (n, k) = n (n - 1) \dots (n - k + 1) = \frac{n!}{(n - k)!} .$ 若不关心顺序，每个选择被上述过程按 $k!$ 种次序重复计算，因此 $(\binom{n}{k}) = \frac{n!}{k! (n - k)!}, 0 \leq k \leq n .$ 这里约定 $0! = 1$ 。例如从 5 人中选主席和秘书，有 20 种结果；只选 2 名不分职务的代表，则有 10 种。是否区分职位直接决定答案。

格点路径把抽象选择画出来

从 $(0, 0)$ 走到 $(3, 2)$ ，每次只能向右或向上走一个单位。每条路径都含 3 次向右、2 次向上；在 5 个步位中选出 2 个放“向上”，路径便唯一确定。

三列两行格点网格，从原点到三二的一条右右上右上路径被标出 — 路径与含三个 R、两个 U 的长度 5 序列一一对应，数量为 C(5,2)=10。

因此路径总数为 $(\binom{5}{2}) = 10$ 。一般从 $(0, 0)$ 到 $(m, n)$ 的这类路径有 $(\binom{m + n}{n})$ 条。若设置障碍点，上述无障碍计数就需要调整。

同一个数量的两种计数

考虑从 $n$ 人中选 $k$ 人，固定其中一人为“指定人”。每个选择要么不包含此人，要么包含此人，所以 $(\binom{n}{k}) = (\binom{n - 1}{k}) + (\binom{n - 1}{k - 1}) .$ 上式取 $1 \leq k \leq n - 1$ ，两端边界值为 $(\binom{n}{0}) = (\binom{n}{n}) = 1$ 。这解释了帕斯卡三角形的递推规则。二项式定理也有类似解释：在 $(x + y)^{n}$ 的 $n$ 个因子中，选 $k$ 个提供 $y$ ，其余提供 $x$ ，于是 $(x + y)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{n - k} y^{k} .$ 系数来自选择次数，不必靠逐项展开猜测。

重复计数、容斥与抽屉原理

两个集合的并集满足 $| A \cup B | = | A | + | B | - | A \cap B |$ 。例如 1 到 30 中能被 2 或 3 整除的整数有 $15 + 10 - 5 = 20$ 个，减去的 5 个是能被 6 整除、此前被算了两次的数。

抽屉原理则说明：把 $N$ 个对象放进 $k$ 个盒子，至少一个盒子有 $⌈ N / k ⌉$ 个对象。例如 13 人中至少两人的出生月份相同，无需假设每个月等可能。它给出必然存在性，通常不告诉究竟是哪两人。

使用计数结果计算概率

只有基本结果等可能时，才能用“有利结果数除以总结果数”计算概率。从重复对象中选择、允许放回抽样或区分顺序，都会改变样本空间。先说清对象与规则，再选计数方法，是避免错用阶乘与组合数的关键。

延伸阅读

Oscar Levin，《Discrete Mathematics: An Open Introduction》第 1 章：加乘原则、二项式系数与组合证明。
概率 · 图论 · 逻辑