容斥原理

odoo13之文件预览widget/模块

并集

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

\[\left|\bigcup\limits_{i=1}^{n}A_i\right|=\sum\limits_{k=1}^n(-1)^{k+1}\left(\sum\limits_{1\leq i_1\leq…i_k\leq n}|A_{i_1}\cap…\cap A_{i_k}|\right) \]

证明

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

考虑一个处于\(\bigcup\limits_{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}\\=&\sum\limits_{i=1}^m(-1)^{i-1}\dbinom{m}{i}\end{aligned} \]

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

可能是Asp.net Core On host、 docker、kubernetes(K8s) 配置读取的最佳实践

\[\begin{aligned}cnt=&\sum\limits_{i=1}^{m}(-1)^{i-1}\dbinom{m}{i}\\=&-\sum\limits_{i=1}^{m}(-1)^i\dbinom{m}{i}\\=&\dbinom{m}{0}-\dbinom{m}{0}-\sum\limits_{i=1}^{m}(-1)^{i}\dbinom{m}{i}\end{aligned} \]

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

\[=\dbinom{m}{0}-\sum\limits_{i=0}^m\dbinom{m}{i}(-1)^i1^{m-i}\\=1-(-1+1)^m\\=1 \]

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

交集

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

\[\left|\bigcap\limits_{i=1}^{n}A_i\right|=|U|-\left|\bigcup\limits_{i=1}^{n}\overline{A_i}\right|=\overline{\bigcup\limits_{i=1}^n\overline{A_i}} \]

拓展——\(\min-\max\)容斥

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

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

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

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

写在最后

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

比较有趣,建议阅读

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

容斥原理
免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

数据结构中的树(二叉树、二叉搜索树、AVL树)