容斥原理
loip
·
·
个人记录
容斥原理及其证明
现有 n 个集合 S_i (1≤i≤n),已知我们可以算出任意几个集合的交集的大小，如何求这 n 个集合并集的大小
容斥原理
\left | \bigcup_{i = 1}^{n}S_i \right | = \sum_{m=1}^{n} (-1)^{(m-1)}\sum_{a_i < a_{i+1}}^{}\left |\bigcap_{i=1}^{m}S_{a_i} \right |
口语化表述:
这n个集合并集大小 = \sum_{m=1}^{n} (-1)^{(m-1)} \times (从n个集合中任选m个集合交集的大小)
(注:选出的m个集合以不同顺序排列则只算一次)
证明:
运用二项式证明
考虑单个元素的贡献，若元素 a 出现在集合 T_1,T_2,T_3...T_k 中，那么只有当选出的m个集合中至少包含 T_{i...k} 中的一个且不包含任何其他不含a的集合时，a 才会属于这 m 个集合的交集，并被计算贡献
则 a 的贡献为:
\sum_{i=1}^{k} (-1)^{i-1}C_k^i = \binom{k}{1}-\binom{k}{2}+\binom{k}{3}-...(-1)^{k-1}\binom{k}{k}
引理: 二项式定理
(a+b)^k = \sum_{i=0}^kC_k^ia^{k-i}b^i
显然当 a=1,b=-1 时，有：
\binom{k}{0}-\binom{k}{1}+\binom{k}{2}-...(-1)^{k}\binom{k}{k}
移项得
\binom{k}{0} = \binom{k}{1}-\binom{k}{2}+...(-1)^{k-1}\binom{k}{k} = 1
于是元素 a 贡献为 1，发现每个元素的贡献都一样等于1，那么所有元素贡献的和就是并集的大小。
容斥原理一般化
即为子集反演，常用于集合的计数问题，而对于两个集合的函数 f(S),g(S) (S和T是集合，f和g是函数)，若
f(S) = \sum_{T \subseteq S} g(T)
(如果集合用二进制串表示那么这实际上就是高维前缀和)
那么有
g(S) = \sum_{T \subseteq S} (-1)^{\left|S\right|-\left|T\right|}f(T)
简单证明
g(S) = \sum_{T \subseteq S} (-1)^{\left|S\right|-\left|T\right|}f(T)
g(S) = \sum_{T \subseteq S} (-1)^{\left|S\right|-\left|T\right|}\sum_{Q \subseteq T} g(Q)
md下一步不会了，以后再证明吧