容斥定理

参考 集合符

$$\left|\bigcup _{i=1}^n{A}_i\right|=\sum _{i=1}^n(-1{)}^{i-1}{A}_{[i]}$$
$$\left|\bigcup _{i=1}^n{A}_i\right|=\sum _{i=1}^n(-1{)}^{i-1}\sum _{1\le k_1<\cdots <k_i\le n}|A_{k_1}\cap \cdots \cap A_{k_i}|$$

这里证法应该是最简单、最直接的证法，而数学归纳法的缺点是必须先猜出答案。

约定

$A_{[i]}$ 与 $A_{(i)}$ 表示集合或者对应的基数，具体由上下文决定。

集簇

• 约定1： A = { A 1 , A 2 , … , A n } A = \{ A_{1}, A_{2}, \dots, A_{n} \} A={A1​,A2​,…,An​}
• 约定2：$A_{[i]}:=$ A 中所有 $i$ 个元素交的模的和，或 A 中所有 $i$ 个元素的交簇。
• 约定3：$A_{(i)}:=$ A 中所有仅有 $i$ 个元素交的模的和，或 A 中仅有 $i$ 个元素的交，$A_{(i)}$的元素称作i重元
• 约定4：$\Omega ={\bigcup }_{i=1}^n{A}_i={\bigcup }_{i=1}^n{A}_{(i)}$ 是样本空间
  其中 $A_{(1)}$… $A_{(n)}$是 $\Omega$ 的一个划分，若 i ≠j 则 $A_{(i)}$ 和 $A_{(j)}$无交集。
• 约定5：$t{A}_{(k)}$ 指 $A_{(k)}$ 中的元素算了 $t$ 次（$t\ge 0$）。

计数

$A_{[i]}$ 与 $A_{(i)}$的含义根据上下文理解
$A_{[i]}$ ：至少 $i$ 个集合相交的总和，存在重复计数
$A_{(i)}$ ：恰好 $i$ 个集合相交的总和，无重复、无重叠
$A_{[i]}$:从 $n$ 个集合中任意选 $i$ 个求交集，再将所有交集大小相加一个属于 $s$ 个集合的元素（$s\ge i$）会被计算 ${\mathrm{C}}_s^i$ 次
包含恰好 $i,i+1,\dots ,n$ 个集合相交的所有元素
$A_{(i)}$只属于恰好 $i$ 个集合的元素总数
元素不重复、不遗漏，两两之间无交集
所有 $A_{(i)}$ 构成样本空间的一个划分

T1

$A_{[k]}$ 对 $A_{(s)}$ 中的元素算了 $C_s^k$ 次（$s\ge k$）。

P1：
$x\in A_{(s)}$，则 $x$ 被确定的 $s$ 个集合包含。
从这 $s$ 个集合挑出 $k$ 个集合对应到 $A_{[k]}$ 上，每一种挑法 $x$ 都被算 1 次。

例如：

• $A_{[5]}$ 对 $A_{(3)}$ 算了 0 次。
• 因为 $A_{[5]}$ 中的元素至少是 5 个集合交出来的(也可能是大于5个集合交出的)
• 而 $A_{(3)}$ 中的元素是 3 个集合交出来的。
• 所以 $x\in A_{(3)}\Rightarrow x\notin A_{[5]}$。

$A_{[i]}$ 与 $A_{(i)}$ 的关系

为简化表达, 下面的$A_{[i]}$ 与 $A_{(i)}$ 都表示基数

• $A_{[1]}:C_1^1{A}_{(1)}+C_2^1{A}_{(2)}+\dots +C_n^1{A}_{(n)}$
• $A_{[2]}:0A_{(1)}+C_2^2{A}_{(2)}+\dots +C_n^2{A}_{(n)}$
• $\dots$
• $A_{[n]}:0A_{(1)}+0A_{(2)}+\dots +C_n^n{A}_{(n)}$

取第 1 行 - 第 2 行 + 第 3 行 - … 第 n 行，即得到：

$$A_{(1)}+A_{(2)}+\dots A_{(n)}$$
这正是总的样本空间的元素个数

解释

这里$A_{[i]}$ 与 $A_{(i)}$ 表示对应集合的基数, 即 用集合指代集合的基数
上面用到了恒等式
$$\sum _{i=1}^n(-1{)}^{i-1}{C}_n^i=1$$
故
$$\left|\bigcup _{i=1}^n{A}_i\right|=A_{(1)}+A_{(2)}+\cdots +A_{(n)}=A_{[1]}-A_{[2]}+A_{[3]}-\dots A_{[n]}$$
即
$$\left|\bigcup _{i=1}^n{A}_i\right|=\sum _{i=1}^n(-1{)}^{i-1}{A}_{[i]}$$

容斥定理例题

$$|A\cup B|=|A|+|B|-|A\cap B|$$

某班级有学生50人，其中喜欢数学的有30人，喜欢语文的有28人，两门都不喜欢的有5人。
请问：两门学科都喜欢的学生有多少人？

• 样本空间 $|\Omega |=50$（班级总人数）
• 喜欢数学 |A|=30 :
• 喜欢语文 |B|=28
• 都不喜欢： $|\Omega |-|A\cup B|$=5
  带入容斥定理得 $|A\cap B|=30+28-45=13$ 人