组合数学

组合数学（combinatorics）研究离散对象怎样选择、排列、分配和组织，以及满足条件的结果共有多少种。一次计数既要说明所数的对象，也要说明什么时候把两种描述看成同一个结果。

例如，从 5 人中选主席和秘书，与从 5 人中选两名不分职务的代表，答案就不同。甲任主席、乙任秘书，与乙任主席、甲任秘书是两套任职方案；作为两名代表，却是同一个二人组。

从分步选择到排列

先选主席，有 5 种选择；对每种主席选择，秘书都可从余下 4 人中选。因此共有 $5 \cdot 4 = 20$ 套方案。这里每套方案由前后两步唯一确定，这就是乘法原理。

同样，从 n 个不同对象中依次选 k 个，不重复使用对象，第一步有 n 种，第二步有 n−1 种，直到第 k 步有 n−k+1 种。带顺序的选取称为排列，数量为 $P (n, k) = n (n - 1) \dots (n - k + 1) = \frac{n!}{(n - k)!} .$ 这里 n、k 是整数， $0 \leq k \leq n$ ； $n! = n (n - 1) \dots 1$ 叫阶乘，约定 $0! = 1$ 。

乘法原理所要求的是每个阶段有确定的分支数。例如 3 件上衣与 2 条裤子，任意搭配都可用时有 6 套；若有一件上衣只能配其中一条裤子，就应分开计算为 $1 + 2 + 2 = 5$ 套。这里按上衣分成互不重叠的三类，再相加，是加法原理。

不计顺序时，为什么要除

仍从 5 人中选 2 人。前面的 20 套任职方案里，每个二人组都出现两次：两人交换职位得到另一种排列。因此不分职务的代表组只有 $20 / 2 = 10$ 个。

一般选出 k 人后，这 k 人可以排成 $k!$ 种次序。所有有序选取按“选中了哪些人”分成等大的组，每组恰有 k! 个结果。忽略顺序的选取称为组合，数量记为 $(\binom{n}{k}) = \frac{n!}{k! (n - k)!}, 0 \leq k \leq n .$ 例如 $(\binom{5}{2}) = 10$ 。选 0 个对象时只得到空集一种结果，选全部 n 个时也只有一种，故 $(\binom{n}{0}) = (\binom{n}{n}) = 1$ 。

取补集还给出一个对应：每种选 k 个的方案，恰好留下 n−k 个未选对象。因此 $(\binom{n}{k}) = (\binom{n}{n - k}) .$ 这条等式来自同一选择的两种描述。

委员会有条件时，怎样避免漏计和重计

现有 4 名甲组成员、3 名乙组成员，7 人各不相同。要选 3 人，且至少有一名乙组成员。

可以先数全部三人组，再去掉全部来自甲组的情况： $(\binom{7}{3}) - (\binom{4}{3}) = 35 - 4 = 31.$ 也可以按乙组人数分类。恰有 1 名乙组时，选法为 $(\binom{3}{1}) (\binom{4}{2}) = 18$ ；恰有 2 名时为 $(\binom{3}{2}) (\binom{4}{1}) = 12$ ；恰有 3 名时只有 1 种。三类不会重叠，总数为 $18 + 12 + 1 = 31$ 。

为什么不先选一名乙组成员，再从剩下 6 人选 2 人？这会算出 $3 (\binom{6}{2}) = 45$ 。含两名乙组的委员会，其中任何一位都能被当作“先选的人”，所以被算了两次；含三名乙组的被算了三次。重复次数不一样，便不能通过统一除以一个数恢复答案。

若题目还要求指定一位主席，每个合法委员会都恰有 3 种选择，结果为 $31 \cdot 3 = 93$ 。若主席必须来自乙组，则前面的三类分别有 1、2、3 种主席选择，总数变为 $18 \cdot 1 + 12 \cdot 2 + 1 \cdot 3 = 45.$ 这次 45 数的是“委员会加乙组主席”，每个结果确实包含一个被特别指定的乙组成员。

把选择画成格点路径

从 $(0, 0)$ 到 $(3, 2)$ ，每次只能向右或向上走一个单位。图中金色路线先右、右，再上、右、上，记录成 $R R U R U$ ；R 表示右移，U 表示上移。

三列两行网格，金色箭头从原点依次右右上右上，到达三二 — 每条路径由五个步位组成，选择其中两个作为向上步，便确定整条路线。

到达终点总共需要 3 次右移、2 次上移。只要在 5 个位置中选出两个放 U，其余放 R，就唯一确定一条路径；任何允许的路径也都产生这样一组位置。因此路径数为 $(\binom{5}{2}) = 10.$ 一般从 $(0, 0)$ 到 $(m, n)$ 的同类路径，需要 m+n 步，其中选 n 步向上，故有 $(\binom{m + n}{n})$ 条。

这个对应还能处理障碍。若本例禁止经过 $(1, 1)$ ，先数经过该点的路线：到它需要一右一上，有 $(\binom{2}{1}) = 2$ 种；从它到终点需要两右一上，有 $(\binom{3}{1}) = 3$ 种。每条经过它的路线唯一分成这两段，故共有 6 条应被排除，留下 $10 - 6 = 4$ 条。

组合数之间为什么相加

从 n 人中选 k 人，固定某一人。每个组合要么不选此人，要么选此人。前一类从剩下 n−1 人选 k 人；后一类已选一人，还需从剩下的人选 k−1 人。因此 $(\binom{n}{k}) = (\binom{n - 1}{k}) + (\binom{n - 1}{k - 1}), 1 \leq k \leq n - 1.$ 加上两端的 1，就得到杨辉三角中“一个数等于上方相邻两数之和”的规则。

组合数也出现在二项式展开中。例如 $(x + y)^{3}$ 的每一项，都是从三个因子中各取 x 或 y 后相乘。要得到 $x^{2} y$ ，需选出一个因子提供 y，有 $(\binom{3}{1}) = 3$ 种，因此它的系数为 3。

一般在 n 个因子中选 k 个提供 y，其余提供 x，便有 $(x + y)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{n - k} y^{k} .$ 这里的系数记录同一种乘积由多少次选择产生，称为二项式定理。

相同物品分到不同盒子

把 6 个相同球分到 3 个有标号的盒子，允许空盒。若三个盒子中的球数分别为 $x_{1}, x_{2}, x_{3}$ ，问题就是数出所有非负整数解 $x_{1} + x_{2} + x_{3} = 6.$ 用 6 个星号表示球、2 条隔板区分盒子。例如“★★｜｜★★★★”表示 $(2, 0, 4)$ 。隔板可以相邻，也可以位于两端，分别表示中间或端部的盒子为空。

每个分配恰对应一个由 6 个星号和 2 条隔板组成的串，反之亦然。只需从 8 个位置中选出 2 个放隔板，所以有 $(\binom{8}{2}) = 28$ 种分法。这叫隔板法。一般 n 个相同物品分到 $k \geq 1$ 个不同盒子，需要 n 个星号和 k−1 条隔板，结果为 $(\binom{n + k - 1}{k - 1})$ 。

如果球彼此可区分，每个球有 3 个盒子可选，结果是 $3^{6}$ ，不是 28。若盒子没有标号， $(2, 0, 4)$ 的不同排列又可能表示同一种分配；各类分配的重复次数不一致，也不能把 28 直接除以 $3!$ 。

加上下界和上界

若每盒至少一个，先给每盒放一个，剩下 3 个球自由分配。令 $y_{i} = x_{i} - 1$ ，就有 $y_{1} + y_{2} + y_{3} = 3$ ，各项非负，故分法为 $(\binom{5}{2}) = 10$ 。

下图上排展示 (2,0,4) 的编码，中间相邻的两条隔板表示第二个盒子为空。下排展示每盒先放一个球的做法：金色球是固定分配，剩余青色球才需要重新计数；(1,2,3) 因而对应剩余量 (0,1,2)。

上排六个球与两条相邻隔板表示二零四，下排三个金色预放球与三个剩余球表示一二三减下界后为零一二 — 隔板位置记录分配；扣除下界把至少一个转为允许空盒。

若允许空盒，但每盒至多 3 个，就从原来的 28 种中排除某盒至少 4 个的情况。固定这一个盒子先放 4 个，剩下 2 个任意分，有 $(\binom{4}{2}) = 6$ 种。共有 3 个盒子可以超限，而且 6 个球不可能同时使两盒各至少 4 个，所以这些坏情况不重叠。答案为 $28 - 3 \cdot 6 = 10$ 。

若同时要求每盒至少 1 个、至多 3 个，先减去下界后，各 $y_{i}$ 在 0 到 2 之间，总和为 3。不设上界时有 10 种；超限只能是某项为 3、其余为 0，共 3 种。因此答案为 $10 - 3 = 7$ 。可以直接列出检查： $(2, 2, 2)$ 一种，加上 $(1, 2, 3)$ 的六种排列。

一般下界不必相同。若第 i 盒至少放 $ℓ_{i}$ 个，先扣去这些固定份额，再对剩余量使用隔板法；若还有限定上界，也须一并减去同样的份额。

用多项式记下每个盒子的选择

单盒允许放 1、2、3 个球，可以记成 $z + z^{2} + z^{3}$ 。z 的指数记录球数。三个不同盒子逐个选择，对应乘积 $(z + z^{2} + z^{3})^{3} .$ 相乘时指数相加，因此六次项的系数就是总共放 6 个球的分法数。只有指数 $(1, 2, 3)$ 的六种排列与 $(2, 2, 2)$ 能凑成 6，所以系数为 7。

这种把“大小”记在指数、“数量”记在系数中的方法叫生成函数。这里它只是一个有限多项式，乘法的每一次取项都对应一个实际分配，不涉及无穷级数的收敛问题。

有重叠的类别怎样相加：容斥

在 1 到 30 中，2 的倍数有 15 个，3 的倍数有 10 个。若直接相加，6 的倍数会被数两次；这样的数有 5 个。因此能被 2 或 3 整除的数共有 $15 + 10 - 5 = 20.$ 用集合记为 $| A \cup B | = | A | + | B | - | A \cap B | .$

三个集合时，先加各自大小，再减三组两两交集。属于三重交集的对象先被数三次，又被减三次，变成零次，因此要补回来： $\begin{matrix} | A \cup B \cup C | = & | A | + | B | + | C | \\ - | A \cap B | - | A \cap C | - | B \cap C | \\ + | A \cap B \cap C | . \end{matrix}$ 逐个检查属于一个、两个、三个集合的元素，都恰好保留一次。这就是容斥原理。

例如将三个不同字母重新放进三个有标号的位置，要求没有字母留在原位。全部排列有 6 个。令 A、B、C 分别表示各字母仍在原位的坏情况，每类有 2 个排列；固定任意两个字母会使第三个也固定，因此各两两交集及三重交集都只含原排列一个。坏排列共有 $6 - 3 + 1 = 4$ 个，合法排列便为 $6 - 4 = 2$ 个，恰是两种循环移位。

把大问题拆成较小问题

用长度为 1 或 2 的小砖铺满一行长度为 n 的木板，砖沿木板方向放置，不留空隙。记铺法数为 $a_{n}$ 。

观察最后一块砖：若长 1，前面剩下长度 n−1 的木板，有 $a_{n - 1}$ 种铺法；若长 2，前面剩下 n−2，有 $a_{n - 2}$ 种。两类互不重叠又覆盖全部铺法，因此 $a_{n} = a_{n - 1} + a_{n - 2} (n \geq 2) .$ 空木板有“不放砖”一种铺法，故 $a_{0} = 1$ ；长度 1 只有一块短砖，故 $a_{1} = 1$ 。依次得到 $a_{2} = 2$ 、 $a_{3} = 3$ 、 $a_{4} = 5$ 。初值和递推式合在一起，才确定整列答案。

限制位置也可以转成已经解决的分配问题。八位二进制串恰含三个 1，有 $(\binom{8}{3}) = 56$ 个。若 1 不能相邻，先在相邻两个 1 之间各放一个必需的 0；五个 0 已用掉两个，剩下三个可分到两端与两个内部间隙，共四个有标号的空隙。隔板法给出 $(\binom{6}{3}) = 20$ 种。把这些零重新放回各空隙，就唯一恢复原串。

只问必然存在，不必逐一数出

13 人分到 12 个出生月份，若每个月至多一人，总人数最多为 12，与 13 矛盾。因此至少有两人的出生月份相同。这个结论与月份是否等可能无关，称为抽屉原理。

一般把 N 个对象放入正整数 k 个盒子，至少一盒的数量不小于 $⌈ N / k ⌉$ ，其中符号表示向上取整。若每盒数量都少于这个整数，总和便小于 N。

计数用于概率时则要多一个条件：只有基本结果等可能，才能直接用“有利结果数除以全部结果数”。例如选委员会时，若所有三人组等可能，上面至少含一名乙组的概率才是 $31 / 35$ 。指定某人必选，会改变选择机制和样本空间。

历史

二项式系数表在不同数学传统中出现过。杨辉 1261 年《详解九章算法》记述了相关数表，并引用贾宪的方法；贾宪的相关原著已经散佚，部分内容由杨辉的记述保存。MacTutor：杨辉介绍了这些文献关系。

今天常用“杨辉三角”或“Pascal 三角”称呼这一数表。它把多项式展开、组合选择和格点路径联系到一起：同样的数字可以来自不同问题，而一一对应或分类计数解释了它们为何相同。

参考资料

Oscar Levin：二项式系数。
Oscar Levin，Discrete Mathematics: An Open Introduction：计数、递推关系及生成函数。
MacTutor：杨辉。
相关条目：集合、概率、图论、逻辑。