容斥原理的猜测与证明

摘要：容斥原理研究的是若干个有限集合的并集所包含的元素的个数，是一个为了计数有限集合中元素的个数而得到的结论，与集合的性质用以解决一类有限集合元素个数的问题。本文主要通过两个集合的容斥原理，猜测并证明三个集合和n个集合的容斥原理。

 关键词：容斥原理  猜测 证明

前言 

我们已经学习过两个集合的容斥原理，猜测并证明三个集合和n个集合的容斥原理。

一 .两个集合的容斥原理  n(A∪B)=n(A)+n(B) -n(A∩B)

二 .三个集合的容斥原理的猜测和证明

2．1由两个集合的容斥原理  n(A∪B)=n(A)+n(B) -n(A∩B)猜测三个集合的容斥原理。

猜测公式1：n(A∪B∪C)=n(A)+n(B)+n(C) -n(A∩B)-n(B∩C)-n(A∩C).

反例证明：A={a},  B={a,b},   C={a,b,c}

则有公式1：n(A∩B∩C)=n(A)+n(B)+n(C) -n(A∩B)-n(B∩C)-n(A∩C)=1+2+ 3-1-2-1=2

很明显，n(A∪B∪C)=3

所以，公式不正确

原因分析：由于所举反例中，A∩B∩C={a}≠Ф ，所以会使该类元素在运用公式计算中被全部除去，考虑到这一点，推出猜测公式2

猜测公式2：n(A∪B∪C)=n(A)+n(B)+n(C) -n(A∩B)-n(B∩C)-n(A∩C).+n(A∩B∩C)。

2．2三个集合的容斥原理 

n(A∪B∪C)=n(A)+n(B)+n(C) -n(A∩B)-n(B∩C)-n(A∩C)+n(A∩B∩C)

证明：n(A∪B∪C)=n((A∪B)∪C)

设M=（A∪B）

则原式=n(M∪C)

      =n(M)+n(C)-n(M∩C)

= n(A∪B)+n(C)-n((A∪B)∩C)

= n(A)+n(B)-n(A∩B)+n(C)-( n(A)+n(B)-n(A∩B))∩C

= n(A)+n(B)-n(A∩B)+n(C)-n(A∩C)-n(B∩C)+n(A∩B∩C)

         整理得：n(A∪B∪C)

                =n(A)+n(B)+n(C) -n(A∩B)-n(B∩C)-n(A∩C) +n(A∩B∩C)

  ∴n(A∪B∪C)=n(A)+n(B)+n(C) -n(A∩B)-n(B∩C)-n(A∩C)+n(A∩B∩C)

三 .n个集合的容斥原理的猜测与证明

3．1   n个集合的容斥原理的猜测

假设有集合A₁，A₂，A₃，A₄……A_n，由对三个集合的容斥原理的猜测、证明过程可知，求几个集合所包含的元素的个数，可以先将其中每个集合的元素个数全部相加，得到a所求元素个数。

显然，如果所有集合的之间任意若干个集合的交集均为Ф，那么a即为n(A₁∪A₂A₃∪……∪A_n)， 但如果这些集合中存在若干集合同时有的元素，那么所得a就多加了某些元素，所以在a的基础上减去一些被重复计数的元素。

   假设在A₁ 到A_n这些集合中，只有任意两个集合存在相同的元素，即A_i∩A_j≠Ф(i,j=1,2,3……,i≠j)，在任意三个或三个以上的集合中不存在这些集合均有的相同元素，那么，

n (A₁∪A₂∪A₃∪A₄……∪A_n)

= n (A₁)+n (A₂)+n (A₃) ……+ n (A_n)

-n(A₁∩A₂)- n(A₁∩A₃) ……- n(A₁∩A_n)- n(A₂∩A₃)- ……-n(A_n-1∩An)     (1)

   如果不符合上述要求，即在任意三个或三个以上不同集合中存在这些集合均有的元素，那就意味着在(1)式中，有一部分元素又被重复减去了，需要重新加上。

   所以，以此类推，综上所述，为了便于计数，得出了n个集合的容斥原理。

n (A₁∪A₂∪A₃∪A₄……∪A_n)

= n (A₁)+n (A₂)+n (A₃) ……+ n (A_n)-n(A₁∩A₂)- n(A₁∩A₃) ……- n(A₁∩A_n)- n(A₂∩A₃)- ……-n(A_n-1∩An)+n(A₁∩A₂∩A₃)+ n(A₁∩A₂∩A₃)+ ……+ n(A_n-2∩A_n-1∩An)- ……+……+(-1)^n-1.n(A₁∩A₂∩A₃∩……∩A_n)
3．2   n个集合的容斥原理的证明

证明：n (A₁∪A₂∪A₃∪A₄……∪A_n)

= n (A₁)+n (A₂)+n (A₃) ……+ n (A_n)-n(A₁∩A₂)- n(A₁∩A₃) ……- n(A₁∩A_n)- n(A₂∩A₃)- ……-n(A_n-1∩An)+n(A₁∩A₂∩A₃)+ n(A₁∩A₂∩A₃)+ ……+ n(A_n-2∩A_n-1∩An)- ……+……+(-1)^n-1.n(A₁∩A₂∩A₃∩……∩A_n)

用数学归纳法进行证明
  设：S₁= n (A₁)+n (A₂)+n (A₃) ……+ n (A_n)

S₂= n(A₁∩A₂)+ n(A₁∩A₃) ……+ n(A₁∩A_n)+ n(A₂∩A₃)+ ……+n(A_n-1∩An)

S₃= n(A₁∩A₂∩A₃)+ ……+ n(A_n-2∩A_n-1∩An)

_……

S_n =n(A₁∩A₂∩A₃∩……∩A_n)
   求证：A=n(A₁∪A₂∪A₃∪A₄……∪A_n)= S₁-S₂+ S₃+……+(-1)^n-1S_n

证明：当n=2时，A=n(A₁∪A₂)=n(A₁)+n(A₂) -n(A₁∩ A₂)= S₁-S₂

假设：当n=k(k>=2)时，A=n (A₁∪A₂∪A₃∪A₄……∪A_k)= S₁-S₂+ S₃+……+(-1)^k-1S_k 等式成立。

当n=k+1时，

A= n( (A₁∪A₂∪A₃∪A₄……∪A_k) ∪A_k+1)

 = n (A₁∪A₂∪A₃∪A₄……∪A_k)+n(A_k+1)-n((A₁∪A₂∪A₃∪A₄……∪A_k) ∩A_k+1)

= n (A₁∪A₂∪A₃∪A₄……∪A_k) +n(A_k+1)-n((A₁∩A_k+1) ∪(A₂∩A_k+1) ∪(A₃∩A_k+1) ∪ …∪ (A_k∩A_k+1))

∵ 当n=k时，等式成立

∴A= n (A₁∪A₂∪A₃∪A₄……∪A_k) +n(A_k+1)-(n (A₁∩A_k+1)+ n (A₂∩A_k+1)+ ……+n(A_k∩A_k+1)-n(A₁∩A₂∩A_k+1)-n(A₁A₃∩A_k+1) -……- n(A_k-1∩A_k∩A_k+1)+ ……+(-1)^k.n(A₁∩A₂∩A₃∩∪……∩A_k+1)

    = S₁-S₂+ S₃+……+(-1)^k-1S_k+n(A_k+1)-(n (A₁∩A_k+1)+ n (A₂∩A_k+1)+ ……+n(A_k∩A_k+1)-n(A₁∩A₂∩A_k+1)-n(A₁∩A₃∩A_k+1) -……- n(A_k-1∩A_k∩A_k+1)+ ……+(-1)^k.n(A₁∩A₂∩A₃∩∪……∩A_k+1)

     = S₁-S₂+ S₃+……+(-1)^kS_k+

综上所述，当n>=2时,n (A₁∪A₂∪A₃∪A₄……∪A_n)

= n (A₁)+n (A₂)+n (A₃) ……+ n (A_n)-n(A₁∩A₂)- n(A₁∩A₃) ……- n(A₁∩A_n)- n(A₂∩A₃)- ……-n(A_n-1∩An)+n(A₁∩A₂∩A₃)+ n(A₁∩A₂∩A₃)+ ……+ n(A_n-2∩A_n-1∩An)- ……+……+(-1)^n-1.n(A₁∩A₂∩A₃∩……∩A_n)

结束语

  我们在学习过程中，通过所学知识，触类旁通，不断探索，我们不仅能掌握所学知识，而且还会有新的收获，能更一步激发我们学习数学的兴趣。

作者：

高一(11)

费晔　马嫣砾　徐轶舟　潘宁馨　朱今雨　*田园