并集

假设有(n)个满足全集(U)的性质相同的集合(A_1,A_2,…,A_n),那么他们的并集种的元素个数为:

[left|bigcuplimits_{i=1}^{n}A_iright|=sumlimits_{k=1}^n(-1)^{k+1}left(sumlimits_{1leq i_1leq…i_kleq n}|A_{i_1}cap…cap A_{i_k}|right)
]

证明

证明此式,其实就是要证明每个元素仅出现了一次

考虑一个处于(bigcuplimits_{i=1}^{n}A_i)中的元素(x),他所属(m)个集合(S_1,S_2,…S_m),现在要统计他在并集中出现的次数。

  1. 选取一个集合时,(x)在其中出现的次数为(dbinom{m}{1}=m)

  2. 选取两个集合时,两个集合的贡献为两个集合并集中(x)出现的次数的相反数

    这样的贡献是就是(-dbinom{m}{2})

  3. 选取三个集合时,根据上述方法贡献为(dbinom{m}{3})

  4. 继续根据上述方法进行,当选取的集合树(>n)时,(x)不会在并集中出现,因此没有贡献

(x)出现的总次数为:

[begin{aligned}cnt=&dbinom{m}{1}-dbinom{m}{2}+dbinom{m}{3}-…+(-1)^{m-1}dbinom{m}{m}=&sumlimits_{i=1}^m(-1)^{i-1}dbinom{m}{i}end{aligned}
]

发现这玩意儿和二项式定理很像,试着化一化看看能不能化成二项式定理

[begin{aligned}cnt=&sumlimits_{i=1}^{m}(-1)^{i-1}dbinom{m}{i}=&-sumlimits_{i=1}^{m}(-1)^idbinom{m}{i}=&dbinom{m}{0}-dbinom{m}{0}-sumlimits_{i=1}^{m}(-1)^{i}dbinom{m}{i}end{aligned}
]

化到这一步发现右边两项之和就是二项式定理的式子了,可以进一步转化

[=dbinom{m}{0}-sumlimits_{i=0}^mdbinom{m}{i}(-1)^i1^{m-i}=1-(-1+1)^m=1
]

所以每个在(bigcuplimits_{i=1}^{n}A_i)中的元素都只出现了一次,合并起来就是并集的元素个数,得证

交集

用全集减去补集的并集即可得出,那么显然也为 补集的并集的 补集

[left|bigcaplimits_{i=1}^{n}A_iright|=|U|-left|bigcuplimits_{i=1}^{n}overline{A_i}right|=overline{bigcuplimits_{i=1}^noverline{A_i}}
]

拓展——(min-max)容斥

给定全序集合(S),设(max{S})(S)中的最大值,(min{S})(S)中的最小值,则:

[begin{aligned} max {S} &= sum_{Tsubseteq S}(-1)^{|T|-1} min {T} min {S} &= sum_{Tsubseteq S}(-1)^{|T|-1} max {T} end{aligned}
]

(min-max)容斥对于期望同样满足,所以可以很方便地解决一些概率和期望问题

证明见https://www.cnblogs.com/butterflydew/p/10457362.html

写在最后

写这个的时候突然就想起来之前(lyq)写的博客:

比较有趣,建议阅读

虽然是一年前写的,但现在仍然不朽/xl

本站资源均源自网络,若涉及您的版权、知识产权或其他利益,请附上版权证明邮件告知。收到您的邮件后,我们将在72小时内删除。
若下载资源地址错误或链接跳转错误请联系站长。站长q:770044133。

» 容斥原理

发表评论

免登录下载网,提供全网最优质的资源集合!