---
tags:
- 组合数学
- 容斥原理
下一篇: '[[数学系/离散数学/容斥原理与口味序列计数/02 六种口味排成十位序列]]'
返回目录: '[[数学系/离散数学/容斥原理与口味序列计数/学习指南]]'
abstract: '将三个集合的容斥公式逐项对应到一般求和形式，再通过取补集解释符号变化。'
creation: 2026-10-13
---

# 从奇加偶减到补集容斥

前置知识：有限集合、并集、交集、补集、组合数与求和符号。以下集合均为有限全集 $S$ 的子集，补集均相对于 $S$。

## 1. 从熟悉的三个集合开始

$$
\begin{aligned}
|A\cup B\cup C|
={}&|A|+|B|+|C|\\
&-|A\cap B|-|A\cap C|-|B\cap C|\\
&+|A\cap B\cap C|.
\end{aligned}
$$

这就是“奇加偶减”：单个集合的大小相加，两两交集的大小相减，三个集合交集的大小再加回来。这里的“奇偶”指**参与交集的集合个数**。

> [!warning] 原文记号修正
> 原文将计数公式简写成 $A\cup B\cup C=A+B+C-\cdots$。严格来说，参与加减的是元素个数，应写成 $|A|$、$|A\cap B|$ 等。并集的大小也不等于未经去重的三类元素个数之和。

> [!note] 原图缺失
> 原文写有“如图1所示”，但所给文本未附图1，也未提供图片文件名。上述公式和解释不依赖该图。

## 2. 怎样压缩成一般公式

把 $A,B,C$ 改记为 $A_1,A_2,A_3$。对于 $n$ 个集合，记 $[n]=\{1,2,\ldots,n\}$，令 $I\subseteq[n]$ 表示所选集合的下标，并定义

$$
A_I=\bigcap_{i\in I}A_i\qquad(I\ne\varnothing).
$$

例如，$I=\{1,3\}$ 时，$A_I=A_1\cap A_3$。$|I|=k$ 表示选了 $k$ 个集合，不是说交集里有 $k$ 个元素。

一般的并集容斥公式为

$$
\left|\bigcup_{i=1}^{n}A_i\right|
=\sum_{k=1}^{n}(-1)^{k+1}
\sum_{\substack{I\subseteq[n]\\|I|=k}}|A_I|.
$$

外层求和决定“这次取几个集合”，内层求和遍历“具体取哪几个集合”。$(-1)^{k+1}$ 控制奇加偶减。

### 用三个集合逐项对应

当 $n=3$ 时：

$$
\begin{aligned}
k=1:\quad &I=\{1\},\{2\},\{3\},\\
&\sum_{|I|=1}|A_I|=|A_1|+|A_2|+|A_3|;\\[4pt]
k=2:\quad &I=\{1,2\},\{1,3\},\{2,3\},\\
&\sum_{|I|=2}|A_I|
=|A_1\cap A_2|+|A_1\cap A_3|+|A_2\cap A_3|;\\[4pt]
k=3:\quad &I=\{1,2,3\},\\
&\sum_{|I|=3}|A_I|=|A_1\cap A_2\cap A_3|.
\end{aligned}
$$

给这三组分别加上 $+,-,+$，就回到熟悉的公式。这里的简写 $\sum_{|I|=k}$ 始终要求 $I\subseteq[3]$。

### 六个集合的写法

$$
\begin{aligned}
\left|\bigcup_{i=1}^{6}A_i\right|
={}&\sum_{i=1}^{6}|A_i|
-\sum_{1\le i<j\le6}|A_i\cap A_j|\\
&+\sum_{1\le i<j<\ell\le6}|A_i\cap A_j\cap A_\ell|
-\cdots-|A_1\cap\cdots\cap A_6|.
\end{aligned}
$$

> [!warning] 原文末项符号修正
> 原文一处六集合展开式末项写成了加号。因为 $(-1)^{6+1}=-1$，并集公式的六重交集项应为减号；求补集时才反转为加号。

> [!proof] 补充证明：为什么奇加偶减恰好去重
> 固定一个属于其中恰好 $r\ge1$ 个集合的元素。它在所有 $k$ 重交集的和中被计入 $\binom rk$ 次，总贡献为
>
> $$
> \sum_{k=1}^{r}(-1)^{k+1}\binom rk=1,
> $$
>
> 因为二项式定理给出 $\sum_{k=0}^{r}(-1)^k\binom rk=(1-1)^r=0$。不属于任何集合的元素贡献为零。因此右边恰好把并集中的每个元素计一次。

## 3. 从求并集变成求补集

并集回答“至少属于一个 $A_i$”；题目有时要求“所有 $A_i$ 都不属于”。后者是

$$
S\setminus\bigcup_{i=1}^{n}A_i
=\bigcap_{i=1}^{n}\overline{A_i}.
$$

因此

$$
\begin{aligned}
\left|\bigcap_{i=1}^{n}\overline{A_i}\right|
&=|S|-\left|\bigcup_{i=1}^{n}A_i\right|\\
&=|S|-\sum_{k=1}^{n}(-1)^{k+1}
\sum_{\substack{I\subseteq[n]\\|I|=k}}|A_I|\\
&=|S|+\sum_{k=1}^{n}(-1)^k
\sum_{\substack{I\subseteq[n]\\|I|=k}}|A_I|.
\end{aligned}
$$

符号变化来自外面的减号：$-(-1)^{k+1}=(-1)^k$。

约定空下标集合对应全集，即 $A_{\varnothing}=S$。因为大小为零的下标集合只有 $\varnothing$ 一个，$|S|$ 就能并入 $k=0$ 项：

$$
\boxed{
\left|\bigcap_{i=1}^{n}\overline{A_i}\right|
=\sum_{k=0}^{n}(-1)^k
\sum_{\substack{I\subseteq[n]\\|I|=k}}|A_I|
}.
$$

把求和下标 $k$ 改成 $j$ 不会改变任何数学含义。

### 用三个集合再次对照

$$
\begin{aligned}
|S\setminus(A\cup B\cup C)|
={}&|S|-|A|-|B|-|C|\\
&+|A\cap B|+|A\cap C|+|B\cap C|\\
&-|A\cap B\cap C|.
\end{aligned}
$$

| 对比项 | 并集容斥 | 补集容斥 |
| --- | --- | --- |
| 计算对象 | 至少属于一个集合 | 一个集合都不属于 |
| 全集项 | 无 | 先加全集大小 |
| 一个集合的项 | 加 | 减 |
| 两个集合交集的项 | 减 | 加 |
| 一般符号 | $(-1)^{k+1}$，从 $k=1$ 开始 | $(-1)^k$，从 $k=0$ 开始 |

例如，若全集有 100 个元素，并集大小为 $U$，那么补集大小就是 $100-U$；仅知道全集大小，还不能算出具体的 $U$。

“偶加奇减”是从全集减去并集后出现的符号顺序。使用时先明确要数哪个集合，再决定公式。

下一步：[[数学系/离散数学/容斥原理与口味序列计数/02 六种口味排成十位序列|将交集大小代入口味问题]]。返回 [[数学系/离散数学/容斥原理与口味序列计数/学习指南|学习指南]]。