• 容斥原理简述


    1. 问题引入

    主要用来解决集合的计数问题。

    最常见的应用题,A活动多少人,B活动多少人,AB两活动多少人之类的。

    两三个集合的时候还能画图进行识别,三个以上的集合则看不太出来了。

    2. 公式

    ∣ A 1 ∪ A 2 ∪ A 3 . . . ∪ A m ∣ = ∑ 1 ≤ i ≤ m ∣ A i ∣ − ∑ 1 ≤ i < j ≤ m ∣ A i ∩ A j ∣ + ∑ 1 ≤ i < j < k ≤ m ∣ A i ∩ A j ∩ A k ∣ − . . . + ( − 1 ) m − 1 ∣ A 1 ∩ A 2 ∩ A 3 . . . ∩ A m ∣ = ∑ k = 1 n ( − 1 ) k − 1 ∑ 1 < i 1 < i 2 < . . . < i k ≤ n ∣ A i 1 ∩ A i 2 . . . A i k ∣ \left\vert A_1 \cup A_2 \cup A_3...\cup A_m \right\vert = \sum_{1\le i \le m}\left\vert A_i \right\vert - \\ \sum_{1\le i \lt j \le m} \left\vert A_i \cap A_j\right\vert + \\ \sum_{1 \le i \lt j \lt k \le m} \left\vert A_i \cap A_j \cap A_k\right\vert- ...\\ +(-1)^{m-1}\left\vert A_1 \cap A_2 \cap A_3 ...\cap A_m\right\vert =\\ \sum_{k=1}^{n}(-1)^{k-1} \sum_{1 \lt i_1 \lt i_2 \lt ... \lt i_k \le n} |A_{i_1} \cap A_{i_2}...A_{i_k}| A1A2A3...Am=1imAi1i<jmAiAj+1i<j<kmAiAjAk...+(1)m1A1A2A3...Am=k=1n(1)k11<i1<i2<...<iknAi1Ai2...Aik

    3. 证明

    引入1
    ∣ ⋃ i = 1 n A i ∣ = ∣ A 1 ∪ A 2 . . . A i ∣ \left \vert \bigcup_{i = 1}^n{A_i} \right\vert = \left\vert A_1\cup A_2...A_i\right\vert i=1nAi =A1A2...Ai
    引入2 德摩根定理
    A ∪ B ‾ = A ‾ ∩ B ‾ A ∩ B ‾ = A ‾ ∪ B ‾ \overline{A \cup B} = \overline A \cap \overline B \\ \overline{A \cap B} =\overline A \cup \overline B AB=ABAB=AB

    数学归纳法

    n = 2
    ∣ A 1 ∪ A 2 ∣ = ∣ A 1 ∣ + ∣ A 2 ∣ − ∣ A 1 ∩ A 2 ∣ \left\vert A_1 \cup A_2 \right\vert = \left\vert A_1\right\vert + \left\vert A_2\right\vert - \left\vert A_1 \cap A_2\right\vert A1A2=A1+A2A1A2
    成立。
    假设当 n = s ( s ≥ 2 , s ∈ N ∗ ) n = s(s \ge 2, s \in N^*) n=s(s2,sN)时,结论成立。则当 n = s + 1 n = s+1 n=s+1

    ∣ ⋃ i = 1 n A i ∣ = ∣ ⋃ i = 1 s + 1 A i ∣ = ∣ ( ⋃ i = 1 s A i ) ∪ A s + 1 ∣ = ∣ ⋃ i = 1 s A i ∣ + ∣ A s + 1 ∣ − ∣ ( ⋃ i = 1 s A i ) ∩ A s ∣ = ∣ ⋃ i = 1 s A i ∣   + ∣ A s + 1 ∣ − ∣ ⋃ i = 1 s ( A i ∩ A s + 1 ) ∣ = ∑ 1 ≤ i 1 ≤ s + 1 ∣ A i ∣ + ∑ k = 2 s ( − 1 ) k − 1 ∑ 1 ≤ i 1 < i 2 < i 3 . . ≤ s ∣ A i 1 ∩ A i 2 ∩ A i 3 . . . ∩ A i k ∣ + ∑ k = 2 s + 1 ( − 1 ) k − 1 ∑ 1 ≤ i 1 < i 2 . . . < i k ≤ s + 1 ∣ A i 1 ∩ A i 2 ∩ A i 3 . . A i k ∣ = ∑ 1 ≤ i ≤ s + 1 ∣ A i ∣ + ∑ k = 2 s ( − 1 ) k − 1 ∑ 1 ≤ i 1 < i 2 < i 3 . . i k ≤ s ∣ A i 1 ∩ A i 2 ∩ A i 3 . . . ∩ A i k ∣ + ∑ k = 2 s ( − 1 ) k − 1 ∑ 1 ≤ i 1 < i 2 < i 3 . . ≤ i k ≤ s + 1 ∣ A i 1 ∩ A i 2 ∩ A i 3 . . . ∩ A i k ∣ + ( − 1 ) s ∣ A 1 ∩ A 2 ∩ A 3 ∩ . . . A s + 1 ∣ = ∑ 1 ≤ i ≤ s + 1 ∣ A i ∣ + ∑ k = 2 s + 1 ( − 1 ) k − 1 ∑ 1 ≤ i 1 < i 2 . . i k ≤ s + 1 ∣ A i 1 ∩ A i 2 ∩ . . . A i k ∣   + ( − 1 ) s ∣ A 1 ∩ A 2 ∩ A 3 ∩ . . . A s + 1 ∣ = ∑ k = 1 s + 1 ( − 1 ) k − 1 ∑ 1 ≤ i 1 < i 2 < i 3 . . . < i k ≤ s + 1 ∣ A i 1 ∩ A i 2 . . . ∩ A i k ∣ \left\vert \bigcup_{i=1}^{n}A_i\right\vert = \left\vert \bigcup_{i=1}^{s+1}A_i \right\vert= \left\vert \big(\bigcup _{i =1}^s A_i\big) \cup A_{s+1}\right\vert \\= \\ \left\vert \bigcup_{i=1}^s A_i\right\vert + \left\vert A_{s+1}\right\vert - \left\vert \big( \bigcup_{i=1}^s A_i\big)\cap A_{s}\right\vert \\ = \\ \left\vert \bigcup_{i=1}^s A_i \right\vert \ + \left\vert A_{s+1}\right\vert -\left\vert \bigcup _{ i=1}^s(A_i \cap A_{s+1}) \right\vert \\=\\ \sum_{1 \le i_1 \le s+1}\left\vert A_i\right\vert + \sum_{k =2}^{s}(-1)^{k-1} \sum_{1 \le i_1 \lt i_2 \lt i_3 .. \le s} \left\vert A_{i_1} \cap A_{i_2} \cap A_{i_3}... \cap A_{i_k}\right\vert + \sum_{k=2}^{s+1}(-1)^{k-1}\sum_{1\le i_1 \lt i_2... \lt i_k \le s+1 }|A_{i_1} \cap A_{i_2} \cap A_{i_3}..A_{i_k}| \\= \\ \sum_{1 \le i \le s+1}| A_{i}| +\sum_{k =2}^{s}(-1)^{k-1} \sum_{1 \le i_1 \lt i_2 \lt i_3 .. i_k\le s} \left\vert A_{i_1} \cap A_{i_2} \cap A_{i_3}... \cap A_{i_k}\right\vert +\sum_{k =2}^{s}(-1)^{k-1} \sum_{1 \le i_1 \lt i_2 \lt i_3 .. \le i_k \le s+1} \left\vert A_{i_1} \cap A_{i_2} \cap A_{i_3}... \cap A_{i_k}\right\vert +(-1)^s |A_1 \cap A_2 \cap A_3 \cap... A_{s+1}| \\= \\ \sum_{1 \le i \le s+1}|A_{i}| + \sum_{k=2}^{s+1}(-1)^{k-1}\sum_{1 \le i_1 \lt i_2 ..i_k \le s+1}|A_{i_1} \cap A_{i_2} \cap... A_{i_k}| \ + (-1)^s |A_1 \cap A_2 \cap A_3 \cap... A_{s+1}| \\ \\= \\ \sum_{k=1}^{s+1}(-1)^{k-1} \sum_{1 \le i_1 \lt i_2 \lt i_3... \lt i_k \le s+1}|A_{i_1} \cap A_{i_2}...\cap A_{i_k}| i=1nAi = i=1s+1Ai = (i=1sAi)As+1 = i=1sAi +As+1 (i=1sAi)As = i=1sAi  +As+1 i=1s(AiAs+1) =1i1s+1Ai+k=2s(1)k11i1<i2<i3..sAi1Ai2Ai3...Aik+k=2s+1(1)k11i1<i2...<iks+1Ai1Ai2Ai3..Aik=1is+1Ai+k=2s(1)k11i1<i2<i3..iksAi1Ai2Ai3...Aik+k=2s(1)k11i1<i2<i3..iks+1Ai1Ai2Ai3...Aik+(1)sA1A2A3...As+1=1is+1Ai+k=2s+1(1)k11i1<i2..iks+1Ai1Ai2...Aik +(1)sA1A2A3...As+1=k=1s+1(1)k11i1<i2<i3...<iks+1Ai1Ai2...Aik
    成立得证。

    另一种证明则是元素出现个数的时候的证明,参见OI_WIKI

    参考

    OI_WIKI
    百度百科

  • 相关阅读:
    ESP32C3 开发板 Download Mode 模式
    LeetCode Cookbook 数组习题(5)
    FreeSWITCH rtp 统计
    编译 qsqlmysql.dll QMYSQL driver not loaded
    WP-AutoPostPro 汉化版: WordPress自动采集发布插件 WordPress文章采集
    软件测试基础-测试环境项目部署
    pyspark分布式部署随机森林算法
    【疑问解决】在自动装箱中Integer赋予一个常量1,为什么会出现==判断true和flase的情况(JDK源码、内部缓冲)
    Go_原子操作和锁
    通俗易懂的==和equals()的使用
  • 原文地址:https://blog.csdn.net/bdn_nbd/article/details/133877857