离散数学与证明 I：逻辑、集合、归纳、计数与图论入门｜第 12 章：计数原理、排列组合与二项式系数 | 自在学

计数原理、排列组合与二项式系数

上一章讨论递推时，我们已经碰到过“长度为 $n$ 的对象有多少个”这类问题。递推可以告诉我们第 $n$ 个数量怎样由前面的数量得到；这一章换一个角度，直接研究怎样把结果分解、编码和计数。

计数题表面上问“有多少种”，真正的第一步却不是找公式，而是先确定在数什么对象。同样从 10 名同学中挑出 3 人，“选一个三人小组”和“选出组长、副组长、记录员”显然不是同一批结果。前者只看成员集合，后者还要记录角色。对象一变，答案就变。

所以我们会反复追问两句话：一个合法结果究竟包含哪些信息？我们的记录方式会让每个结果出现几次？加法、乘法、除法、排列、组合和二项式系数，其实都在回答这两个问题。

一个完整的计数论证，不只要写出数值，还要说明为什么所有合法结果都被数到，以及为什么每个结果恰好被数一次。若故意重复计数，则必须说明每个结果被重复了相同的多少次。

先把“结果”说清楚

设所有合法结果组成有限集合 $\Omega$ 。计数问题要找的就是 $|\Omega|$ 。这句记号本身没有解决问题，但它逼着我们先说清楚集合中的一个元素长什么样。

例如，长度为 4 的数字密码可以写成一个有序四元组：

(d_1,d_2,d_3,d_4),\qquad d_i\in\{0,1,\ldots,9\}

这里 $(1,2,3,4)$ 和 $(4,3,2,1)$ 是两个结果，因为位置属于结果的一部分。相反，从甲、乙、丙、丁中选两人组队时，一个结果是集合 $\{\text{甲},\text{乙}\}$ ；把它写成“乙、甲”没有产生新小组。

这也是计数中最有用的思路之一：把不好数的对象，改写成更容易数的序列、集合或位置标记。只要改写前后是一一对应，就可以数后者来得到前者。

一一对应为什么可靠

若每个原对象都能得到唯一编码，每个合法编码也能还原出唯一原对象，那么两边对象数相同。比如，一个 $n$ 元集合的每个子集都可以编码为长度为 $n$ 的二进制串：第 $i$ 位为 $1$ 表示第 $i$ 个元素被选中，为 $0$ 表示没选中。

这个编码既不会把两个不同子集写成同一个串，也不会产生无法还原的合法串。因此

\text{子集}\longleftrightarrow\text{长度为 }n\text{ 的二进制串}

是一一对应。每一位有 $0$ 、 $1$ 两种选择，所以子集总数是 $2^n$ 。

“每个结果都能写成某种记录”还不够。你还要检查同一个结果会不会有多种记录，以及某些记录会不会根本不对应合法结果。排列转组合时要除以 $k!$ ，正是因为同一个无序小组有 $k!$ 种有序记录。

开始计数前的四项核对

面对一道新题，可以按这个顺序检查：

一个结果由一个选择完成，还是由若干步共同完成？
不同情况是否互斥，还是会有对象同时落入多个情况？
交换选择顺序、位置或角色后，是否仍算同一个结果？
同一个对象或同一类别能否再次出现？

前两个问题决定怎样使用加法与乘法，后两个问题决定使用哪一种排列组合模型。这个顺序比看到关键词就套公式可靠得多。

加法原理：把对象分成互不重叠的类

如果 $\Omega$ 被分成互不重叠的几类 $A_1,A_2,\ldots,A_r$ ，每个结果恰好属于其中一类，那么

|\Omega|=|A_1|+|A_2|+\cdots+|A_r|

这里“互不重叠”和“全部覆盖”缺一不可。互不重叠保证不会重复数，全部覆盖保证不会漏数。

例如，一个编号要么由 2 位数字组成，要么由 3 位数字组成，并且允许前导零。长度为 2 和长度为 3 不可能同时发生，所以两类互斥。两位编号有 $10^2$ 个，三位编号有 $10^3$ 个，总数是

10^2+10^3=1100

加法原理常被口语化成“出现‘或’就相加”，但这句话容易误导。“会英语或会日语的人”可能两种语言都会，两个集合有重叠，不能直接相加。真正的判断标准是：我们划出的类别是否互斥。

怎样主动制造互斥分类

有时题目没有现成分类，我们可以选一个特征来分情况。数“不含重复数字的 3 位偶数”时，末位为 $0$ 与末位为 $2,4,6,8$ 是互斥的两类。前一类的首位有 9 种选择，后一类的首位还要避开已经用过的非零末位，只剩 8 种；分开以后，每一类内部就容易使用乘法原理。

分类是否好用，可以用一个具体结果检查：它应该能落入某一类，而且只能落入一类。若一个结果能落入两类，下一章的容斥原理就要登场；若一个结果无处可放，说明分类漏掉了情况。

乘法原理：一个结果由多步选择共同决定

如果一个结果必须依次完成 $r$ 步，第一步有 $n_1$ 种选择；每种第一步之后，第二步都有 $n_2$ 种选择；继续下去，每个合法前缀之后第 $i$ 步都有 $n_i$ 种选择，那么

|\Omega|=n_1n_2\cdots n_r

例如，一份套餐必须包含 3 种主食中的一种和 2 种饮品中的一种。每个结果是有序信息对

(\text{主食},\text{饮品})

所以共有 $3\cdot2=6$ 份不同套餐。这里不是在“主食”和“饮品”中二选一，而是每份套餐都必须把两步完成。

后一步可以依赖前一步

乘法原理并不要求各步独立。关键是：对每个已经形成的合法前缀，下一步的可选数相同。

从 8 名同学中依次选出 3 名担任三个不同职务时，第一步有 8 种；无论第一步选了谁，第二步都剩 7 种；无论前两步具体是谁，第三步都剩 6 种。因此总数是

8\cdot7\cdot6=336

后一步当然依赖前一步，因为已经选过的人不能再选。但“剩余选择数”始终分别是 7 和 6，所以仍能直接相乘。

若不同前缀后面的可选数不一样，就先按前缀类型分类。在每一类中使用乘法，再用加法汇总。很多实际题目正是这样把两条原理嵌在一起。

树状图是在画乘法原理

把每一步选择画成一层分支，从根到叶的一条完整路径就是一个最终结果。均匀分支时，叶子数等于各层分支数相乘；非均匀分支时，可以按大分支分别数叶子，再把各分支的叶子数相加。

加法与乘法一起使用

某系统的账号名长度可以是 4 或 5。第一位必须是 26 个英文字母之一，其余各位是数字，数字允许重复。长度为 4 与长度为 5 是互斥类别，所以外层用加法；固定长度后，每个位置都要完成，所以类内用乘法：

26\cdot10^3+26\cdot10^4=286000

这类题的思路可以概括为：先用加法把不同形状的结果分开，再用乘法填满每一种形状的位置。

除法原理：先允许重复记录，再把重数消掉

有些对象直接数很难，但给它临时加上编号或顺序后就容易数。代价是同一个原对象可能被记录多次。如果每个原对象都恰好对应 $q$ 条记录，那么

\text{原对象数}=\frac{\text{记录数}}{q}

这就是除法原理。分母不是凭感觉写的“去重系数”，而是必须对每个目标对象都相同的对应记录数。

例如，要在 $n$ 个位置中放两枚完全相同的棋子，且不能放在同一位置。若暂时把两枚棋子标成甲、乙，就有 $n(n-1)$ 种放法。去掉标签以后，每个最终布局都被数了两次：甲在位置 $i$ 、乙在位置 $j$ ，以及甲在位置 $j$ 、乙在位置 $i$ 。因此布局数是

\frac{n(n-1)}{2}

除以前必须检查“重数恒定”

假设某些结果有 2 种记录，另一些结果有 3 种记录，就不能把总记录数统一除以一个常数。可靠的做法是任选一个目标结果，问它能由多少条记录产生；再确认这个数量不依赖目标结果的具体内容。

“看起来重复了”并不能自动推出“除以 2”。只有当每个目标结果都恰好被数 2 次时，除以 2 才成立。若重复次数不一致，需要重新编码，或把不同重数的结果分开计数。

这个原则马上会解释组合公式中的 $k!$ 。先按顺序选择容易，忘掉顺序以后，每个小组恰好留下相同数量的有序记录，于是可以统一相除。

顺序和重复决定四种基本模型

“抽取时有先后”不等于“最终结果有顺序”。从盒子里一张张抽出三张卡，动作有先后；如果题目只问最后拿到了哪三张，结果仍然是无序集合。判断顺序时，要比较两个最终记录，而不是回忆操作过程。

另一个问题是能否重复。数字密码通常允许某个数字出现在多个位置，从学生中选代表则通常不允许同一个人占两个名额。把顺序与重复放在一起，就得到四种常见模型。

最终结果	不允许重复	允许重复
顺序重要	从 $n$ 个不同对象中依次取 $k$ 个： $P(n,k)$	$k$ 个位置各有 $n$ 种： $n^k$

“允许重复且顺序不重要”和“有相同对象的排列”是两类不同问题。前者问从若干类别中取多少个；后者已经给定每一类出现的次数，问这些对象能排成多少个序列。后面会分别处理。

排列：给有区分的位置放不同对象

从 $n$ 个不同对象中选出 $k$ 个，依次放进 $k$ 个有区分的位置，并且每个对象最多使用一次。第一位有 $n$ 种，第二位有 $n-1$ 种，直到第 $k$ 位有 $n-k+1$ 种，因此

P(n,k)=n(n-1)\cdots(n-k+1)

用阶乘把连续乘积缩写，得到

P(n,k)=\frac{n!}{(n-k)!}

公式要求 $0\le k\le n$ 。当 $k=n$ 时，所有对象都被排入序列：

P(n,n)=n!

当 $k=0$ 时，结果是空序列。空序列虽然没有位置，却有且只有一个，所以约定

0!=1

这个约定不是为了补公式漏洞；它准确表达了“什么都不选”的唯一方式。

先看位置有没有名字

“从 8 人中选 3 人发言”和“安排第一、第二、第三位发言者”听起来相近，结果对象却不同。若只选 3 人，交换名单顺序不产生新结果；若三个时段不同，谁在哪个时段属于结果的一部分，使用排列：

P(8,3)=8\cdot7\cdot6=336

职位、座位、跑道、日期、密码位都可以让位置产生区分。与其问“题目有没有‘排列’两个字”，不如直接问：把两个人的位置互换后，结果是否改变？

顺序重要且允许重复

若 $k$ 个位置都有 $n$ 种选择，而且同一个对象可以再次使用，那么每一步的可选数不会减少：

n\cdot n\cdots n=n^k

例如长度为 6 的二进制串有

2^6=64

个。 $001101$ 和 $101100$ 是不同序列，且 $0$ 、 $1$ 可以反复出现。这一模型直接来自乘法原理，不需要阶乘。

组合：忘掉内部顺序

从 $n$ 个不同对象中选出 $k$ 个，只关心选中了谁，不关心以什么先后次序选中。这样的结果是 $k$ 元子集，数量记作

\binom{n}{k}

读作“ $n$ 选 $k$ ”。

为什么一定要除以 $k!$

从 10 人中选 4 人组队。我们先故意把队员排成“第一个选中、第二个选中、第三个选中、第四个选中”，就有

P(10,4)=10\cdot9\cdot8\cdot7

条有序记录。

现在盯住某一个具体小组 $\{\text{甲},\text{乙},\text{丙},\text{丁}\}$ 。这 4 人内部可以按任意顺序出现在记录里：甲乙丙丁、甲乙丁丙，等等。第一位有 4 种，第二位有 3 种，第三位有 2 种，最后一位有 1 种，所以这个同一小组一共对应

4!=24

条有序记录。别的小组也完全一样，每组都恰好对应 $4!$ 条记录。于是有序记录到无序小组是一个固定的 $4!$ 对 $1$ 映射，可以使用除法原理：

\binom{10}{4}=\frac{10\cdot9\cdot8\cdot7}{4!}=210

一般地，每个 $k$ 元小组都有 $k!$ 种内部排列，因此

\binom{n}{k}=\frac{P(n,k)}{k!} =\frac{n!}{k!(n-k)!}

这里 $n\in\mathbb{N}$ 且 $0\le k\le n$ ；若 $k>n$ ，在不允许重复选择时没有合法小组，计数为 $0$ 。

组合公式中的 $k!$ 不是“因为顺序不重要，所以习惯性除一下”。它数的是每个无序小组在有序选择中被重复记录的准确次数。先数有序记录，再除掉固定重数，公式就不会显得凭空出现。

也可以从完整排列理解分母

把 $n$ 个对象全部排好，再把前 $k$ 个标为“选中”、后 $n-k$ 个标为“未选中”。一个固定的 $k$ 元子集对应多少个完整排列？选中的 $k$ 个对象内部可以排列 $k!$ 次，未选中的 $n-k$ 个对象内部可以排列次，所以每个子集对应

k!(n-k)!

个完整排列。用 $n!$ 除以这个重数，仍然得到同一个公式。

组合数的边界与对称性

从 $n$ 个对象中一个也不选，只有空集这一种；把所有对象全选，也只有一种：

\binom{n}{0}=\binom{n}{n}=1

从 $n$ 个对象中选出 $k$ 个，选中的集合一旦确定，未选中的 $n-k$ 个也随之确定。因此“选 $k$ 个留下”和“选 $n-k$ 个舍去”一一对应：

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

这是一个计数解释，而不只是阶乘式约分后的巧合。

重复选择：结果是一个多重集

现在从 $n$ 类物品中一共选 $k$ 个，同一类可以选多次，最终只记录每类选了几个。这样的结果不再是普通集合，因为同一类可以出现多次；它叫多重集。

例如，从 5 种口味中选 3 球冰淇淋，不区分三球的上下顺序。结果可以记作计数向量

(x_1,x_2,x_3,x_4,x_5)

其中 $x_i$ 是第 $i$ 种口味选了几球，满足

x_1+x_2+x_3+x_4+x_5=3,\qquad x_i\ge0

所以问题等价于数非负整数解。

星号与隔板怎样形成一一对应

用 $k$ 个星号表示选出的 $k$ 个物品，用 $n-1$ 块隔板把星号分成 $n$ 段。第 $i$ 段的星号数就是 $x_i$ 。

例如，4 类物品中选 7 个，记录

\star\star\mid\star\star\star\star\mid\mid\star

表示计数向量

(2,4,0,1)

相邻隔板表示某一类选了 0 个，开头或结尾出现隔板也同样允许 0。反过来，任何满足总和为 $k$ 的非负整数向量，都能唯一写成这种星号与隔板序列。因此两边是一一对应。

序列一共有 $k+n-1$ 个位置，只要决定其中哪 $k$ 个位置放星号，剩余位置自然放隔板：

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

也可以选择 $n-1$ 个隔板的位置，得到等价写法

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

于是，当 $n\ge1$ 、 $k\ge0$ 且二者都是整数时，从 $n$ 类对象中无序地重复选 $k$ 个的方案数是

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

冰淇淋例子中 $n=5,k=3$ ，所以共有

\binom{7}{3}=35

种口味多重集。

“至少一个”先做变量平移

如果要求每一类至少选一个，方程变成

x_1+x_2+\cdots+x_n=k,\qquad x_i\ge1

先给每一类放一个，令 $y_i=x_i-1$ 。那么

y_1+y_2+\cdots+y_n=k-n,\qquad y_i\ge0

只要 $k\ge n\ge1$ ，正整数解的数量就是

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

这里不是另背一个公式，而是先满足下界，再对剩余数量使用同一套星号与隔板编码。

星号与隔板数的是“每类取多少个”，不记录先取哪一个。若三球冰淇淋从上到下的位置也属于结果，那么草莓、巧克力、草莓与草莓、草莓、巧克力不同，应使用 $5^3$ ，而不是可重复组合。

相同对象的排列与多项式系数

还有一类问题也出现“重复”，但已知每一类对象出现的次数，问题是把它们排成一个序列。

假设总共有 $N$ 个位置，其中第 1 类对象出现 $k_1$ 次，第 2 类出现 $k_2$ 次，直到第 $m$ 类出现 $k_m$ 次，并且

k_1+k_2+\cdots+k_m=N

若先给所有对象加上临时编号，就有 $N!$ 个排列。去掉编号后，第 $i$ 类内部的 $k_i!$ 种交换都不会改变最终序列。每个序列因此被重复记录

k_1!k_2!\cdots k_m!

次，所以不同序列数是

\binom{N}{k_1,k_2,\ldots,k_m} =\frac{N!}{k_1!k_2!\cdots k_m!}

这个数叫多项式系数。

例题：重复字母重排

单词 BANANA 有 6 个字母，其中 A 出现 3 次，N 出现 2 次，B 出现 1 次。不同重排数为

\frac{6!}{3!2!1!}=60

分母中的 $3!$ 消去三个 A 的内部交换， $2!$ 消去两个 N 的内部交换。交换两个相同字母并不会产生新字符串，所以这些记录必须合并。

同一个公式也在数分组

把 $N$ 个不同对象分入 $m$ 个有名字的小组，第 $i$ 组恰好放 $k_i$ 个。可以先从 $N$ 个对象中选 $k_1$ 个放第一组，再从剩余对象中选个放第二组，继续下去：

\binom{N}{k_1} \binom{N-k_1}{k_2} \cdots \binom{k_m}{k_m} =\frac{N!}{k_1!k_2!\cdots k_m!}

左边是连续选组员，右边是统一的多项式系数。两种写法数的是同一批有序分组，所以必然相等。

二项式系数：同一个数字的多种身份

$\binom{n}{k}$ 叫组合数，也叫二项式系数。它频繁出现，不是因为许多题目碰巧套用同一个公式，而是因为许多对象都能编码成“从 $n$ 个位置中选 $k$ 个”。

下面几种对象彼此一一对应：

从 $n$ 个不同对象中选出的 $k$ 元子集；
长度为 $n$ 、恰好有 $k$ 个 $1$ 的二进制串；
由 $n$ 步组成、其中恰好有 $k$ 步向上、其余步向右的网格路径；
在 $(a + b^{}$ 的展开中，选择其中个因子贡献的方式。

因此这些对象的数量都是

\binom{n}{k}

二项式定理的系数从哪里来

把

(a+b)^n

看成 $n$ 个因子的乘积。展开时，每个因子必须选一次：要么选 $a$ ，要么选 $b$ 。想得到 $a^{n-k}b^k$ ，必须从 $n$ 个因子中选出恰好个贡献，其余贡献。这样的因子选择有种，所以

(a+b)^n=\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k

这也解释了“二项式系数”这个名字： $\binom{n}{k}$ 正是二项式展开中 $a^{n-k}b^k$ 的系数。

例题：找指定幂的系数

求 $(2x-3)^6$ 中 $x^4$ 的系数。

展开中的一般项来自选择 $k$ 个因子贡献 $-3$ ，其余 $6-k$ 个因子贡献 $2x$ ：

(\binom{6}{k}) (

Pascal 递推承接上一章

设 $B(n,k)=\binom{n}{k}$ 。从 $n$ 个对象中选 $k$ 个，固定观察其中一个特殊对象甲。每个小组恰好落入两类：包含甲，或不包含甲。

包含甲时，还要从其余 $n-1$ 个对象中选 $k-1$ 个；不包含甲时，要从其余 $n-1$ 个对象中选 $k$ 个。因此，当 $1\le k\le n-1$ 时，

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

配合边界条件

B(n,0)=B(n,n)=1

这就成为一条完整递推关系。上一章讲过的“初始值加递推规则”在这里生成 Pascal 三角：内部每个数等于左上与右上两个数之和。

组合证明：用两种方法数同一批对象

有些恒等式用阶乘化简当然能证明，但计数解释常常更能说明它为什么成立。基本做法很固定：

明确定义一批对象 $S$ ；
用一种方法得到 $|S|$ 的第一个表达式；
用另一种方法得到 $|S|$ 的第二个表达式；
因为两边数的是同一个集合，所以两个表达式相等。

困难不在最后一步，而在于选对 $S$ 。通常可以从等式中较简单的一边猜测对象：看到 $\binom{n}{k}$ ，先想“某个 $n$ 元集合的 $k$ 元子集”。

所有组合数之和

一个 $n$ 元集合共有 $2^n$ 个子集。另一方面，可以按子集大小分类：大小为 $0$ 的有 $\binom{n}{0}$ 个，大小为 $1$ 的有个，直到大小为的有个。这些类别互斥并覆盖所有子集，所以

\sum_{k=0}^{n}\binom{n}{k}=2^n

左边按大小分类，右边按每个元素“选或不选”来编码。两边数的是同一批子集。

一条卷积恒等式

设一共有两组不同对象，第一组有 $m$ 个，第二组有 $n$ 个。要从全部 $m+n$ 个对象中选 $k$ 个，直接数有

\binom{m+n}{k}

也可以按“从第一组选了多少个”分类。若从第一组选 $r$ 个，就必须从第二组选 $k-r$ 个，这一类有

\binom{m}{r}\binom{n}{k-r}

种。把所有可能的 $r$ 相加，得到

\sum_{r=0}^{k}\binom{m}{r}\binom{n}{k-r} =\binom{m+n}{k}

当下标超出可选范围时，相应组合数视为 $0$ 。这样统一写成从 $0$ 到 $k$ ，不会改变实际计数。

检查组合证明时，不要只看两边公式是否熟悉。要核对三件事：两种方法数的是不是同一批对象；分类是否互斥且完整；每个对象在每种方法中是否恰好出现一次。

综合例题：先定义对象，再选择工具

例题：恰有两个数字相同的四位码

用数字 $0$ 到 $9$ 组成长度为 4 的代码，允许首位为 $0$ 。要求恰好有一个数字出现两次，另外两个数字各出现一次。问有多少个代码？

先确认对象。结果是长度为 4 的有序序列，所以位置重要。“恰好一个数字出现两次”还排除了三次重复、四次重复和两对重复。

选择重复的数字，有 $10$ 种。再从剩余 9 个数字中选出两个只出现一次的数字，只有集合重要，有

\binom{9}{2}

这个例子同时用了组合、多重集排列和乘法原理。公式多并不意味着思路杂乱：先选“用哪些数字”，再确定“它们放在哪些位置”，每一步都在补全结果所需的信息。

例题：给每位同学至少一道题

把 12 道同类型练习分给 5 名有名字的同学，每人至少 1 道，只关心每人得到几道。问有多少种分法？

练习同类型，所以不区分具体哪一道；同学有名字，所以五个接收类别有区分。结果可记作正整数解

x_1+x_2+x_3+x_4+x_5=12,\qquad x_i\ge1

若 12 道题彼此不同，问题会完全改变。那时每道题都要选择一名同学，且还要保证每人至少一道；简单星号与隔板不再适用。这个差别再次说明，先确定对象比先找公式更重要。

计数解答的自检方法

写完一道题后，可以做下面几项检查。

检查对象

用一句话说出一个结果的完整记录。若你的记录遗漏了位置、角色或类别，答案通常会偏小；若记录了题目不关心的先后顺序，答案通常会偏大。

检查覆盖与重复

任选一个合法结果，确认它能由你的步骤产生。再问它能产生几次：恰好一次，还是固定的 $q$ 次？如果是后者，是否已经除以 $q$ ？

检查极端值

把参数换成小数。比如 $\binom{n}{0}$ 应为 1， $P(n,1)$ 应为 $n$ ，从 1 类物品中重复选 $k$ 个只能有 1 种多重集。小规模结果若与直觉冲突，通常是模型判断出了问题。

尝试第二种计数方式

组合数恒等式、复杂分情况和固定重数问题，常能用另一种编码复核。两个不同推理得到同一答案，会比单纯重算一遍乘法更有检查价值。

计数题最后应能回答：我数的对象是什么？我怎样把它分解或编码？为什么没有遗漏？每个对象究竟被数了几次？这四句都说得清楚，公式通常只是最后的简写。

小练习

从 12 名同学中选 3 名参加辩论队，不设职务，有多少种？

从 12 名同学中选队长、副队长、记录员各 1 名，同一人不能兼任，有多少种？

长度为 5 的数字验证码允许重复，每一位都可以是 $0$ 到 $9$ ，有多少个？

有 6 种糖果，要买 4 颗，可以重复买同一种，只关心每种买了几颗，有多少种买法？

求 $(x+2)^7$ 中 $x^3$ 的系数。

用 A、A、A、B、B、C 排成长度为 6 的字符串，有多少种？

下一步：当“恰好一次”开始失效

这一章的大多数方法都在努力建立“每个结果恰好一次”的计数：互斥分类让加法不重复，完整步骤让乘法不遗漏，固定重数让除法可以纠正重复，一一对应则把陌生对象换成已知对象。

但还有两种情况没有处理。第一，类别天然重叠，一个对象可能同时满足多个条件，这时简单相加会重复计数；第二，对象比可用类别更多，即使不知道具体分布，也能断定至少两个对象落入同一类。

下一章会分别用容斥原理和鸽巢原理处理这两件事。它们仍然从同一个问题出发：先确定在数什么对象，再追踪每个对象究竟出现了几次。

)

n

(a+b)^n

k

2

x

)^{6 - k}

(

-

3

)^{k}

\binom{6}{k}(2x)^{6-k}(-3)^k