组合数学

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

英文名称：Combinatorics。

English overview

Combinatorics studies discrete arrangements, selections, and structures. A counting problem is not solved merely by recognizing a familiar formula: one must specify the objects, decide whether order and repetition matter, and explain why each valid outcome is counted exactly once. Addition and multiplication provide basic constructions; bijections and double counting explain identities by comparing descriptions of the same collection.

This article develops permutations, combinations, the binomial theorem, inclusion–exclusion, and the pigeonhole principle through complete examples. It derives the formula for choosing a subset by counting ordered selections and then removing the repeated descriptions. Further examples cover distributing identical objects into distinct boxes, counting selections with restrictions, and building recurrences. Generating functions encode counts as coefficients, but the variables in such expressions may be formal bookkeeping devices rather than measured quantities. Historical discussion distinguishes the broad development of counting methods from the naming of particular arrays and formulas. In applications, combinatorial counts can support probability calculations only when the underlying sample outcomes and their weights are specified. Large counts also do not by themselves establish computational difficulty; an algorithm may reason about an entire family without enumerating every member.

加法与乘法原则

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

例如从 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 人中至少两人的出生月份相同，无需假设每个月等可能。它给出必然存在性，通常不告诉究竟是哪两人。

使用计数结果计算概率

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

先判断究竟在数什么

“从五本书中取三本”还不是完整问题。若五本书可区分，只问选出哪三本，那么结果是三元素子集；若还要排在书架上，结果是长度三的有序序列；若每种书可以无限量采购，允许重复又会得到第三种计数。公式里的阶乘只负责执行已经确定的模型，不会自动替人补齐题意。

最稳妥的检查方法是先用很小的规模手工列举。例如从 A、B、C 中选两本，不计顺序只有 AB、AC、BC 三种；计顺序则有 AB、BA、AC、CA、BC、CB 六种。这个差二倍的结果来自每个无序选择有两种排列。一般情况下必须证明每个对象恰好被重复计了同样次数，才能统一除以某个数。若重复次数不一样，简单相除就是错的。

组合数公式为什么要除以阶乘

从 n 个不同对象中依次选 k 个、不允许重复，第一步有 n 种，第二步有 n−1 种，直到第 k 步有 n−k+1 种，得到 $n (n - 1) \dots (n - k + 1) = \frac{n!}{(n - k)!} .$ 对任意固定的 k 元子集，将其中元素排列都有恰好 k! 种有序结果。所有有序选取按其底层子集分成等大的组，因此 $(\binom{n}{k}) = \frac{n!}{k! (n - k)!}, 0 \leq k \leq n .$ 端点 k=0 对应只选出空集这一种结果，所以约定 0!=1 与组合解释一致。k 大于 n 时通常把组合数定义为零，以方便统一写递推式；这不是对原来阶乘公式直接代入负整数。

取补集给出一个双射：每个 k 元子集对应唯一的 n−k 元未选集合，所以 $(\binom{n}{k}) = (\binom{n}{n - k})$ 。固定其中某一个对象，按“选它”与“不选它”把 k 元子集分成两类，则 $(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k}) .$ 两个证明都不需要繁琐约分，原因是等式两端本就在数同一批对象。理解这种分类方式后，三角形里相邻数相加的规则才不只是一张需要背诵的图表。

完整算例：带限制的委员会

现有四名甲组成员、三名乙组成员，七人均不同，要选三人且至少包含一名乙组成员。第一种方法先数所有三人组，再减去全来自甲组的情况，得到 $(\binom{7}{3}) - (\binom{4}{3}) = 35 - 4 = 31$ 。第二种方法按乙组人数分类：一名乙组有 $(\binom{3}{1}) (\binom{4}{2}) = 18$ 种，两名乙组有 $(\binom{3}{2}) (\binom{4}{1}) = 12$ 种，三名乙组有 $(\binom{3}{3}) (\binom{4}{0}) = 1$ 种，总数同为 31。

这两种解法提供相互核对，还暴露一种常见错误：先选一名乙组成员，再从剩下六人选两人，会得到 $3 (\binom{6}{2}) = 45$ 。其中含两名乙组成员的委员会被算两次，含三名乙组成员的被算三次，不能靠统一除以二或三修复。错误不在乘法原理，而在构造步骤给同一个最终对象提供了不同数量的描述。

若还要从三名委员中指定一位主席，最后才乘以三，结果是 93，因为每个合法委员会恰有三种主席选择。若主席必须来自乙组，则应按前面的三类分别乘以一、二、三，结果为 $18 + 24 + 3 = 45$ 。这次数字 45 是正确答案，但回答的是另一个问题；数值巧合不能代替对象定义。

隔板法及其限制

把六个相同球放入三个有标号的盒子，允许空盒，等价于求非负整数解 $x_{1} + x_{2} + x_{3} = 6$ 。用六个星号与两个分隔符表示，例如“★★｜｜★★★★”对应 (2,0,4)。每个分配都对应唯一这样的字符串，反之亦然，故结果为 $(\binom{8}{2}) = 28$ 。两个隔板可以相邻，也可以放在两端，恰好表示空盒。

若每盒至少一个球，先给每盒一个，把 $y_{i} = x_{i} - 1 \geq 0$ 代入，得到和为三的非负整数解，计数为 $(\binom{5}{2}) = 10$ 。另回到允许空盒的情形，只限制每盒至多三个，则在原来的 28 个分配中，减去某盒至少四个的情形：固定某盒先放四个，剩下两个分到三盒有 $(\binom{4}{2}) = 6$ 种；三个盒子合计 18，且不可能同时有两盒至少四个，所以最后为 10。

“盒子无标号”会让若干排列代表同一个分配，但含重复份额与不含重复份额的重复次数不同，不能把 28 直接除以 3!。同样，若球可区分，问题变成每个球选择盒子，有 $3^{6}$ 种。隔板法的前提必须同时包括：物品相同、盒子不同、总量固定以及相应的上下界。

从递推关系到生成函数

用长度一和长度二的小砖铺满长度 n 的单行木板，砖方向固定，不留空隙。记铺法数为 $a_{n}$ 。最后一块若长一，前面有 $a_{n - 1}$ 种；若长二，前面有 $a_{n - 2}$ 种。两类互斥且覆盖全部情况，因而 $a_{n} = a_{n - 1} + a_{n - 2}$ ，初值 $a_{0} = 1, a_{1} = 1$ 。空木板的一种铺法是“不放任何砖”，这个初值使长度二得到两种，长度三得到三种，长度四得到五种。

形式幂级数 $A (z) = \sum_{n \geq 0} a_{n} z^{n}$ 把全部计数包装在一个对象中。按递推式逐项相减得到 $(1 - z - z^{2}) A (z) = 1$ ，故 $A (z) = 1 / (1 - z - z^{2})$ 。此处可以把 z 看作记录长度的记号，只讨论各次幂系数，不必先主张一个数值无穷级数在所有 z 上收敛。若要把它当作实际函数求值，才需要补充收敛半径。

递推关系是把复杂对象拆成较小对象，生成函数则把组合拆分翻译成代数运算。它们与函数和线性代数相连，但最重要的仍是先证明拆分没有遗漏与重叠。如果末块允许多种颜色，就要在递推系数中记录颜色选择，而不能机械套用同一数列。

三个集合的容斥如何修正过度扣除

若对三个有限集合先相加，再减去三组两两交集，那么同时属于三个集合的对象最初被数三次，随后又被减三次，变成零次。因此还必须把三重交集加回来： $| A \cup B \cup C | = | A | + | B | + | C | - | A \cap B | - | A \cap C | - | B \cap C | + | A \cap B \cap C | .$ 属于一组、两组、三组的对象分别被保留一次，覆盖了全部成员情形。这是逐对象核验公式的方法，比仅背“加减交替”更能说明为什么要补回最后一项。

把三个不同字母重新放入三个有标号的位置，并要求没有字母留在原位，可以用容斥完整计算。全部排列有六个；固定某个字母不动，其余两个可交换，有两种，所以三项共减去六次。固定任意两个字母会迫使第三个也不动，三组两两交集各有一个，故加三；三者都固定只有一个，再减一。结果为 $6 - 6 + 3 - 1 = 2$ ，恰好是两种循环移位。

这个算例同时解释了为何不能只减去“有一个字母固定”的三类数量：这些类别彼此重叠，而不是互斥分类。计数策略应先分清使用的是互斥拆分、双射，还是有重叠的覆盖。它们都可以得出正确数字，却有不同的正确性理由。

一般上下界与生成函数的交叉检查

把 $n$ 个相同物品分进 $k \geq 1$ 个不同盒子，允许空盒，隔板法给出 $(\binom{n + k - 1}{k - 1})$ 。若每盒至少 $ℓ_{i}$ 个，先扣除所有下界；剩余量为负时无解，非负时再用原公式。下界彼此不必相同，预分配方法仍然成立，因为它给原分配与新非负解之间一个双射。

同时存在上界时，扣除下界以后必须同步调整上界，不能只减总数。例如六个球分三盒、每盒一至三个，令 $y_{i} = x_{i} - 1$ ，得到总和为三且各项至多二。无上界时有十种；某项至少三只可能是该项为三、其余为零，共有三种，故实际为七种。与“允许空盒、每盒至多三个”的十种是不同问题。

也可用生成函数独立检查：单盒可放一至三个球，贡献 $z + z^{2} + z^{3}$ ，三个不同盒子相乘，所求是 $(z + z^{2} + z^{3})^{3}$ 中六次项系数。它由一、二、三的六种排列以及二、二、二这一种选择产生，共七。这里相乘是逐盒选择，指数相加记录总球数，系数统计产生同一总数的不同分配，正好对应计数对象。

历史、用途与概念边界

计数问题长期存在于不同文化的历法、算术和游戏之中，组合数学没有一个单独的“发现者”。今天常称杨辉三角或 Pascal 三角的数表也具有多条历史线索。MacTutor 的杨辉传记介绍了杨辉 1261 年《详解九章算法》及其所引贾宪材料；贾宪的相关原著已不存，部分信息由杨辉记述保存；不同名称反映传播和记述传统，不宜据名称断言全世界最早的发现归属。

现代组合数学不仅算排列数，还研究结构何时存在、怎样构造、最极端能达到什么规模。抽屉原理就说明：把 n+1 个对象放进 n 个盒子，至少一盒有两个对象。它给出存在性，但不一定告诉我们在大型数据中怎样快速找到目标。另一方面，可能对象数量巨大，也不意味着每个问题都必须枚举；递推、对称性和代数方法常可大幅压缩计算。

在概率中，只有等可能的基本结果才可以直接用“有利数量除以总数量”。在计算机程序中，计数可用于估计搜索空间、验证边界输入和分析算法，但应注意大整数溢出，分步计算组合数时也不要先算巨大阶乘再用浮点数相除。数学上的精确整数与机器里的有限精度是两个层次。

二进制串的间隔核验

八位二进制串中恰有三个 1，有 $(\binom{8}{3}) = 56$ 个，因为只需选择三个位置；若不能有相邻的 1，可先把三个 1 排定，在相邻之间预留两个 0，再将剩下三个 0 放入四个空隙，得到 $(\binom{6}{3}) = 20$ 个。两端空隙允许为空，内部空隙是在强制零之外继续添加，故这个对应是一一的。

编者评注（AI 辅助）

组合题最有价值的一步常发生在公式出现之前：给每个结果规定一种唯一的编码。遇到难题时，先列出三四个小例子，观察是否有重复描述，再决定用补集、分类、双射还是递推。建议保留两种能相互验证的计数方法；它们比单纯得到一个整数更能说明对象结构，也有助于发现题目中隐藏的顺序与重复条件。

参考来源与延伸阅读

Oscar Levin：二项式系数；另见同书计数与生成函数章节。
MacTutor：杨辉，用于数表的历史背景。
Oscar Levin，《Discrete Mathematics: An Open Introduction》第 1 章：加乘原则、二项式系数与组合证明。
概率 · 图论 · 逻辑