容斥定理

作者: Minglie | 来源:发表于2024-01-01 17:57 被阅读0次

容斥原理
HAOI 硬币购物 - 容斥
2021-12-03
[Combinatorial] 6 容斥与鸽巢
4-19容斥原理
理想主义现实手段
容斥原理与鸡兔同笼
第5课：容斥原理入门
分布式事务：CAP定理
数学专题整理

$\LARGE \left|\bigcup_{i=1}^{n} A_{i}\right|=\sum_{i=1}^{n}(-1)^{i-1} A_{[i]}$

上式中的A[i] 叫做积和符 ,是数学中很常见的一种符号。

容斥定理在4个以上的集合就很难画图了,而数学归纳法必须先猜出答案。
我使用A(j)划分来证明, 应该是最简单,自然,的证法。

4e25e3c73a62d43568e80210ee09a0d2.png

约定

A[i] 与A(i) 表示集合或者对应的基本元的个数,具体含义根据其周围的符号
$\bigcup$ , $\sum$ , | | ,+来判定

约定1

A={A1，A2，…An} Aj 中的元素叫基本元
引入基本元是防止与 A(i) 或 A[i]中的元素混淆

约定2

A[i] := A中所有i个元素交的模的和或 A中所有i个元素的交簇
A[i] 中有重复的基本元 (有重交)
例: A[2] 中的基本元是 $\bigcup_{i!=j}$ Aj∩ Aj 中的元素

约定3

A(i) := A中所有仅有i个元素交的模的和或 A中仅有i个元素的交簇
A(i) 已经把重复的部分排除了 (无重交)
例: A(2)中的基本元是 $\bigcup_{i!=j}$ Aj∩ Aj 排除重复部分的元素
k>s ⇒ A(s) 中的基本元不会出现在A[k]中
k≤s ⇒ A(s) 中的基本元在A[k]中出现了 $C_{s}^{k}$ 次
A(k)≤ A[k] 并且 A(k)在A[k] 中出现了1次

约定4 ：

𝓐= $\bigcup_{i=1}^{n} A_{i}=\bigcup_{i=1}^{n} A_{(i)}$ ; A(j)划分了𝓐, i!=j ⇒ A(i)∩A(j)=Φ
|𝓐|= $\left|\bigcup_{i=1}^{n} A_{i}\right|=\sum_{i=1}^{n}|A_{(i)}|$

约定5

tA(k) 指A(k)中的元素算了t次（t ≥0）

T1:A[k] 将 A(s)中的基本元算了 $C_{s}^{k}$ 次

P1: x是A(s) 中的一个基本元 , x被确定的s个集合包含, 从这s个集合挑出k个集合对应到A[k]上,
每一种挑法x都被算了1次
举个例子 : A[5] 对 A(3) 算了0次
A[5] 中的基本元至少是5个集交出来的
A(3)中的基本元是3个集交出来的
A(3)的基本元不会出现在A[5]中

A[i] 与A(i) 的关系阵是一个上三角阵

A[1] : $C_{1}^{1}$ A(1) $C_{2}^{1}$ A(2) ... $C_{n}^{1}$ A(n)