6.4 二项式定理与容斥原理

本节汇集本章的主要思想：

• 乘法原理计算跨阶段选择；

• 组合计算哪些位置采用某类选择；

• 加法原理合并互斥情况；

• 重叠必须修正，避免重复计数。

我们先用这些思想展开幂，再计算重叠集合的并集。

二项式系数为什么出现在幂中

含两个项的表达式称为二项式，例如 $x+y$。考虑

要生成展开式中的一项，需要从每个因子中选择 $x$ 或 $y$。

三个因子各有 $2$ 种选择，乘法原理给出

个原始选择。

例如：

三个不同选择都产生 $x^2y$，因为可以选择三个因子中的哪一个提供 $y$：

同理，三个选择产生 $xy^2$：

所以

二项式定理

在

中，假设恰好 $k$ 个因子选择 $y$，其余 $n-k$ 个选择 $x$，会产生

选择提供 $y$ 的 $k$ 个位置有

种方法。对所有可能 $k$ 求和，得到二项式定理：

中国大陆教材常把同一个二项式系数写成 $C_n^k$，而英文教材更常用 $\binom nk$。两种记号对应完全相同的定理：

展开写成

示例：展开 $(a+b)^4$

系数为

因此

检查每一项：

• 指数和为 $4$；

• $b$ 的指数从 $0$ 增加到 $4$；

• 系数计算哪些位置提供了 $b$。

帕斯卡恒等式

二项式系数满足

证明时，从 $n$ 人中选一个 $k$ 人委员会，并关注一个指定人物 Ada。

每个委员会恰好属于一个互斥情况：

1. Ada 被选中。再从其他 $n-1$ 人中选 $k-1$ 人：

2. Ada 没被选中。全部 $k$ 人从其他 $n-1$ 人中选择：

两种情况相加，就证明恒等式。

把系数按行排列，得到帕斯卡三角形：

每个内部元素等于上方两个元素之和。

系数和的重要公式

在二项式定理中令 $x=1,y=1$：

因此

这也可以按子集大小计算一个 $n$ 元集合的全部子集。左边把每个可能大小 $k$ 的子集数相加，右边是第 6.1 节的幂集计数。

从 $(x+y)^n$ 的各因子中做选择，观察原始选择字符串融合成同类项。系数锻造炉会用上方父项之和动态生长帕斯卡各行；选择任意格子还能看到委员会分类与对应单项式。

两集合容斥原理

回到第 6.1 节的重叠问题。对有限集合 $A,B$，直接相加

会把 $A\cap B$ 中每个元素计算两次：一次作为 $A$ 的成员，一次作为 $B$ 的成员。

把交集减去一次：

这就是两集合容斥原理。

示例：参加两个社团的学生

一组学生中：

人参加音乐社，

人参加戏剧社，并且

人同时参加。

至少参加一个社团的人数为

只参加音乐社的人数为

只参加戏剧社的人数为

可以用互斥区域检查并集：

用补集计算“两者都不”

假设全集 $U$ 含 $50$ 名学生。如果 $40$ 人至少参加一个社团，那么两个都不参加的人数为

这里使用补集规则

需要仔细翻译文字：

• “至少一个”表示并集；

• “两者都”表示交集；

• “只属于 $A$”表示 $A\setminus B$；

• “两者都不”表示并集的补集；

• “恰好一个”表示两个仅属于区域的并集。

三集合容斥原理

对有限集合 $A,B,C$，先相加三个集合大小：

两两交集中的元素被计算两次，所以减去三个两两交集：

但 $A\cap B\cap C$ 中的元素：

• 被加入 $3$ 次；

• 又被减去 $3$ 次；

目前计数为 $0$。因此还要把三重交集加回一次：

交替正负号会修正重复计数。

三集合示例

对 $100$ 人的调查中：

并且

于是

因此

人不属于任何一个集合。

用区域检查避免解释错误

数量 $|A\cap B|$ 通常包含也属于 $C$ 的元素。除非题目明确说明，否则它不是“只属于 $A$ 和 $B$”的区域。

只属于 $A\cap B$ 的区域大小为

在示例中，这个值为

题目给出多个重叠数量时，应先填最深的交集，再向外计算。这样能避免前后不一致地减去三重交集。

通过涂写区域人数来建立三集合调查，而不只调节集合总数。扫描器会重建每个边际量与交集，可视化每一轮容斥怎样改变元素的计数次数，并在计算并集前标记不可能的数据。

本章衔接

第 6 章建立了计数工具箱：互斥情况相加、连续阶段相乘、用双射翻译、区分排列与组合、证明强制碰撞、展开二项式并修正重叠。

第 7 章将递归地定义对象并研究递推关系。计数会再次出现，因为许多递归结构由更小规模的选择构成，其数量会满足从一个规模连接到下一个规模的方程。