Jetbrains全家桶1年46，售后保障穩定

容斥原理的證明

原鏈接地址

容斥原理（翻譯） – vici – 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被加的總次數），所以，證明完畢。

（自己畫的圖示理解）

題目

能滿足一定數目匹配的字符串的個數問題

給出n個匹配串，它們長度相同，其中有一些’?’表示待匹配的字母。然后給出一個整數k，求能正好匹配k個匹配串的字符串的個數。更進一步，求至少匹配k個匹配串的字符串的個數。

首先我們會發現，我們很容易找到能匹配所有匹配串的字符串。只需要對比所有匹配串，去在每一列中找出現的字母（或者這一列全是’?’，或者這一列出現了唯一的字母，否則這樣的字符串就存在），最后所有字母組成的單詞即為所求。

現在我們來學習如何解決第一個問題：能正好匹配k個匹配串的字符串。

我們在n個匹配串中選出k個，作為集合X，統計滿足集合X中匹配的字符串數。求解這個問題時應用容斥原理，對X的所有超集進行運算，得到每個X集合的結果：

此處f(Y)代表滿足匹配集合Y的字符串數。

如果我們將所有的ans(X)相加，就可以得到最終結果：

這樣，就得到了一個復雜度的解法。

這個算法可以作一些改進，因為在求解ans(X)時有些Y集合是重復的。

回到利用容斥原理公式可以發現，當選定一個Y時，所有中X的結果都是相同的，其符號都為。所以可以用如下公式求解：

這樣就得到了一個復雜度的解法。

現在我們來求解第二個問題：能滿足至少k個匹配的字符串有多少個。

顯然的，我們可以用問題一的方法來計算滿足k到n的所有結果。問題一的結論依然成立，不同之處在于這個問題中的X不是大小都為k的，而是>=k的所有集合。

如此進行計算，最后將f(Y)作為另一個因子：將所有的ans做和，有點類似二項式展開：

在《具體數學》(Graham, Knuth, Patashnik.“Concrete Mathematics”[1998])中，介紹了一個著名的關于二項式系數的公式：

根據這個公式，可以將前面的結果進行化簡：

那么，對于這個問題，我們也得到了一個的解法：

總結

以上是生活随笔為你收集整理的容斥原理的证明_容斥原理三集合公式解释的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。