高级宽容原则 - 宽容原则的证明

 

 

 

       我们要证明下面的等式：

 

 

 

       

 

 

 

         其中B代表全部Ai的集合

 

 

 

         我们需要证明在Ai集合中的任意元素，都由右边的算式被正好加上了一次（注意如果是不在Ai集合中的元素，是不会出现在右边的算式中的）。

 

 

 

         假设有一任意元素在k个Ai集合中（k>=1），我们来验证这个元素正好被加了一次：

 

 

 

         当size(C)=1时，元素x被加了k次。

 

 

 

         当size(C)=2时，元素x被减了C(2,k)次，因为在k个集合中选择2个，其中都包含x。

 

 

 

         当size(C)=3时，元素x被加了C(3,k)次。

 

 

 

         ……

 

 

 

         当size(C)=k时，元素x被加/减了C(k,k)次，符号由sign(-1)^(k-1)决定。

 

 

 

         当size(C)>k时，元素x不被考虑。

 

 

 

         然后我们来计算所有组合数的和。

 

 

 

         

 

 

 

         由二项式定理，我们可以将它变成：

 

 

 

 

    

 

 

 

 

 

         我们把x取为1，这时表示1-T（其中T为x被加的总次数），所以，证明完毕。