容斥原理的证明_容斥原理三集合公式解释

容斥原理的证明

原链接地址

容斥原理（翻译） &＃8211; vici &＃8211; C++博客

       我们要证明下面的等式：

         其中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被加的总次数），所以，证明完毕。

         此处f(Y)代表满足匹配集合Y的字符串数。

         如果我们将所有的ans(X)相加，就可以得到最终结果：

         这样，就得到了一个复杂度的解法。

中X的结果都是相同的，其符号都为。所以可以用如下公式求解：

         这样就得到了一个复杂度的解法。

         现在我们来求解第二个问题：能满足至少k个匹配的字符串有多少个。

         显然的，我们可以用问题一的方法来计算满足k到n的所有结果。问题一的结论依然成立，不同之处在于这个问题中的X不是大小都为k的，而是>=k的所有集合。

         如此进行计算，最后将f(Y)作为另一个因子：将所有的ans做和，有点类似二项式展开：

在《具体数学》( Graham, Knuth, Patashnik. &＃8220;Concrete Mathematics&＃8221; [1998] )中，介绍了一个著名的关于二项式系数的公式：

根据这个公式，可以将前面的结果进行化简：

那么，对于这个问题，我们也得到了一个的解法：