本节对应原书 PDF 第 201–202 页。定义、定理、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。
组合学主要研究满足某种条件下的配置问题，例如，这种配置是否存在？如果存在，能够有多少种不同的配置方案？这些具体的方案是什么？在给定优化函数的情况下，最优的配置是什么？这些分别属于组合存在性问题、计数问题、枚举问题和优化问题. 限于篇幅，本书主要讨论组合计数问题和组合优化问题. 前面章节已经涉及组合优化问题，例如，图论中的最小生成树就是一棵满足某种条件的最优生成树，Huffman 树对应的前缀码是最优前缀码等. 第 8 章到第 10 章将集中讨论组合计数问题. 组合计数在许多学科中都会用到，特别是在计算机的算法设计与分析中用于估计算法的复杂度函数. 本章将引入基本的组合计数规则和公式.
下面介绍解决组合问题的一些常用的技巧.
1. 一一对应的思想
先看两个例子.
例 8.1 如图 8.1 所示，有一个 3\times 3\times 3 的立方体，问至少需要切多少次才能切成 27 个边长为 1 的小立方体？在切割时允许将切下的若干方块任意放置，并一起切割.
一种可能的方法就是沿着图中的直线进行切割，总共切 6 次，就可以得到所有的小立方体. 有没有更好的切割方法？我们不可能枚举所有的切割方法，但是可以使用一一对应的技术证明不可能存在少于 6 次的切法. 考虑处在原来的大正方体中心位置的小立方体，它由 6 个面构成，每个面都不是原来立方体的面，而是由切割产生的新面. 在这个小立方体的面与切割次数之间存在一一对应，因为每切割 1 次，能够产生并且至多只能产生 1 个这样的面. 因此 6 个面至少需要切割 6 次.
图 8.1
例 8.2 50 个选手进行淘汰赛，要决出冠军，至少需要多少次比赛？
解 答案是 49 次. 一种可行的比赛方法是分组. 第一轮 25 场比赛；进入第二轮，25 个人可以分成 12 组，1 人轮空. 类似地，第三轮 13 个人分成 6 组，1 人轮空；第四轮 7 人需要分成 3 组，1 人轮空；第五轮 4 个人分成 2 组，第六轮，2 个人分成 1 组. 总的比赛次数为
使用一一对应的技巧可以证明 49 是最少的比赛次数. 因为只有 1 个冠军是优胜者，其他的人都要通过比赛被淘汰掉. 1 场比赛至多只能淘汰 1 个人，因此，为了淘汰 49 个人，至少需要 49 场比赛.
有许多典型的组合计数问题，如选取问题、非降路径问题、棋盘布棋问题、不定方程的非负整数解问题、整数拆分问题、放球问题等，对于这些问题已经得到相应的公式或者求解的方法，换句话说，已经建立了相应的组合计数模型. 当遇到其他组合计数问题的时候，如果可以与这些典型的计数模型建立一一对应，那么就可以直接应用有关的结果来求解. 这是一种非常有用的方法.
2. 数学归纳法
本书第 1 章已经介绍了数学归纳法. 这是证明有关自然数命题的一种有力工具. 组合数学中涉及的问题，很多都是自然数，因此常常会用到数学归纳法.
3. 上下界逼近的思想
为了确定一个计数的结果，有时需要分别证明这个数的上界和下界. 当上界与下界的值相等时，这个数就被唯一确定下来了. 例 8.1 就使用了这种思想. 首先给出一种切割 6 次的方法，这样就证明了 6 是最少切割次数的一个上界. 然后证明了无论用什么切割方法都至少需要 6 次才能完成切割任务，这样就证明了 6 也是问题的下界. 上界与下界都等于 6，因此最少的切割次数就是 6.
解读：例 8.1 和例 8.2 演示了「一一对应」最典型的两种用法——把「切几次」翻译成「有多少个切割面」，把「比多少场」翻译成「淘汰多少人」。计数难的题目一旦找到这种对应，往往退化成一句加减法。
组合学有两个基本的计数规则——加法法则与乘法法则.
8.1.1 加法法则
加法法则：事件 A 有 m 种产生方式，事件 B 有 n 种产生方式，当 A 与 B 产生的方式不重叠时，“事件 A 或 B”有 m+n 种产生方式.
加法法则使用的条件是事件 A 与 B 产生的方式不能重叠. 也就是说，每一种产生的方式不能同时属于两种事件. 例如从一个班上选择社团的成员，有 6 个同学参加爱心社，5 个同学参加登山社，那么当这两个社团的成员不重叠时，参加爱心社或者登山社的学生有 6+5=11 人. 这里使用了加法法则.
加法法则可以推广到 n 个事件的情况. 设 A_1,A_2,\cdots,A_n 是 n 个事件，它们的产生方式分别有 p_1,p_2,\cdots,p_n 种，当其中任何两个事件产生的方式都不重叠时，事件“A_1 或 A_2 或 \cdots 或 A_n”有 p_1+p_2+\cdots+p_n 种产生的方式.
8.1.2 乘法法则
乘法法则：事件 A 有 m 种产生方式，事件 B 有 n 种产生方式，当 A 与 B 产生的方式彼此独立时，“事件 A 与 B”有 mn 种产生方式.
乘法法则使用的条件是事件 A 与 B 产生的方式彼此独立. 换句话说，事件 A 对产生方式的选择不影响事件 B 对产生方式的选择，反之也对. 例如从 a,b,c,d 中选择 2 个字母构成有序对，如果每个字母至多出现 1 次，问有多少种选法？有序对的第一元素可以有 4 种选法，第二元素也可以从 a,b,c,d 中选择. 但是当第一元素确定以后，它只能从剩下的 3 个字母中独立进行选取，因此总的选法数不是 4\times 4=16，而是 4\times 3=12.
乘法法则也可以推广到 n 个事件的情况. 设 A_1,A_2,\cdots,A_n 是 n 个事件，它们的产生方式分别有 p_1,p_2,\cdots,p_n 种，当其中任何两个事件产生的方式都彼此独立时，事件“A_1 与 A_2 与 \cdots 与 A_n”有 p_1p_2\cdots p_n 种产生的方式.
解读：两条法则的分工只有一句话——「或」用加法，前提是两类方式不重叠；「与」用乘法，前提是两步选择彼此独立。上面那个 4\times 3 的例子正说明：一旦第二步的可选数被第一步改变了，就不能照搬「每步都有 4 种」再相乘。
8.1.3 分类处理与分步处理
加法法则与乘法法则经常结合起来使用. 在组合计数时，往往需要将被计数的个体分成若干个不同的类，先分类计数，然后使用加法法则计数总数. 这种方法就是分类处理. 有时被计数的方法需要分几步才能构成，那么需要分别计数每一步独立的方法，然后使用乘法法则计数总数. 这种方法就是分步处理. 分类处理与分步处理可能会嵌套使用. 比如，先分类，在计数每类元素时再分步处理；也可能先分步，在计数每步的方式时又需要分类处理.
例 8.3 设 A,B,C 是 3 个城市，从 A 到 B 有 3 条道路，从 B 到 C 有 2 条道路，从 A 直接到 C 有 4 条道路，问从 A 到 C 有多少种不同的方式？
解 将从 A 到 C 的方式分成两类：经过 B，不经过 B. 这两类方法数加起来等于总方法数. 再考虑其中经过 B 的方式，这需要分步处理，即从 A 到 B 的方式数乘以从 B 到 C 的方式数. 因此从 A 到 C 的方法数是 N=3\times 2+4=10.
例 8.4 求 1400 的不同的正因子个数.
解 1400 的素因子分解式为
因此，1400 的正因子形式都是 2^i\cdot 5^j\cdot 7^k，其中，0\leqslant i\leqslant 3,0\leqslant j\leqslant 2,0\leqslant k\leqslant 1. 由于 i,j,k 的选择是独立的，这是一个分步处理的问题. i 的选法有 4 种，j 的选法有 3 种，k 的选法有 2 种，根据乘法法则，1400 有 N=4\times 3\times 2=24 个正因子.
解读：例 8.3 是「先分类、类内分步」的模板——两类相加，其中一类内部相乘。例 8.4 则把「枚举因子」变成「给三个指数各选一个值」，这是把具体对象换成参数选择的常见手法。