排容原理（Inclusion-Exclusion Principle）－老王的夢田

排容原理（Inclusion-Exclusion Principle）

問題：一年甲班共有40個人，本次段考國文及格的有26人，英文及格的有24人，數學及格的有17人；國文和英文都及格的有17人，國文和數學都及格的有12人，英文和數學都及格的有11人；三科都及格的有10人。

如果問至少一科及格的有多少人？我們都知道可以用排容原理處理。

設A表示國文及格的人所成的集合；
B表示英文及格的人所成的集合；
C表示數學及格的人所成的集合；那麼由題目知道

n(A)＝26，n(B)＝24，n(C)＝17；
n(A∩B)＝17，n(A∩C)＝12，n(B∩C)＝11；
n(A∩B∩C)＝10

排容原理：
n(A∪B∪C)＝n(A)＋n(B)＋n(C)－n(A∩B)－n(A∩C)－n(B∩C)＋n(A∩B∩C)

故至少一科及格的人數為
26＋24＋17－17－12－11＋10＝37

也可以知道三科都不及格的有3人。

如果現在問說「恰好只有一科及格的人有多少？」可以用小學生就會的方法：

畫出文式圖，然後分成D₁到D₈八個區塊，分別算出每個區塊的人數為
D₇＝10，得到D₄＝7，D₅＝2，D₆＝1，
D₁＝7，D₂＝6，D₃＝4，當然D₈＝3

所求為D₁＋D₂＋D₃＝17

其實可以這麼看

D₁＝n(A)－D₄－D₅－D₇
D₂＝n(B)－D₄－D₆－D₇
D₃＝n(C)－D₅－D₆－D₇
因此D₁＋D₂＋D₃＝n(A)＋n(B)＋n(C)－2 D₄－2 D₅－2 D₆－3 D₇

但是又有D₄＋D₇＝n(A∩B)，D₅＋D₇＝n(A∩C)，D₆＋D₇＝n(B∩C)

於是D₁＋D₂＋D₃＝n(A)＋n(B)＋n(C)－2×n(A∩B)－2×n(A∩C)－2×n(B∩C)＋3D₇

D₁＋D₂＋D₃＝n(A)＋n(B)＋n(C)－2×n(A∩B)－2×n(A∩C)－2×n(B∩C)＋3×n(A∩B∩C)……………………………………（※）

關於（※）式可以這麼解釋：
我們要算恰好只有一科及格的人，可以先將各科及格人數相加；但是兩科及格的人不需要算，他們被算了兩次，所以減去兩倍；但是三科都及格的人也不需要算，他們先被算了三次，又被減去六次，所以要加回三次才對。

這個式子，不就跟排容原理很像嗎？

重新定義符號：
給定n個集合A₁、A₂、……、A_n，宇集合為U，
S₀＝n(U)

S₁＝Σ_i n(A_i)
S₂＝Σ_i_＜j n(A_i∩A_j)
S₃＝Σ_i_＜j_＜k n(A_i∩A_j∩A_k)

………………………………………

S_n＝n(A₁∩A₂∩……∩A_n)

意思就是S_k表示所有k個集合的交集的元素個數總和。

又定義e_m表示恰好在m個集合中的元素個數(例如上面恰好只有一科及格的人數為e₁)，那麼排容原理就是

e_m＝S_m－C(m＋1，1)×S_m_＋1＋C(m＋2，2)×S_m_＋2－C(m＋3，3)×S_m_＋3＋……＋(－1)ⁿ^－mC(n，n－m)×S_n

【證明】

計算U中每個元素在上式的左右兩邊被計算的次數相等。

＜1＞如果x恰在m個集合中
在左式被算了一次；
在右式中，x會在S_m中但是不會在任何S_k(k＞m)中，
所以也被算了一次。

＜2＞如果x恰在m－i個集合中
那麼它就不在e_m中，左式沒算到；
在右式中，它也不會在任何S_k(k＞m)中，
所以也沒算到。

＜3＞如果x恰在m＋j個集合中
那麼它就不在e_m中，左式沒算到；
在右式中，計算S_m時，會有C(m＋j，m)個集合算到它；同樣的，
計算S_m_＋1時，會有C(m＋j，m+1) 個集合算到它；
也就是計算S_m_＋k時，會有C(m＋j，m+k) 個集合算到它；
一直到計算S_m_＋j時，會有C(m＋j，m+j) 個集合算到它；
以後計算S_m_＋k（k＞j）就都沒有算到了。
於是在右式中，x被算了
C(m＋j，m)－C(m＋1，1)×C(m＋j，m+1)＋C(m＋2，2)×C(m＋j，m+2)＋……
＋(－1)^kC(m＋k，k)×C(m＋j，m+k)＋……＋(－1)^jC(m＋j，j)×C(m＋j，m+j)
接著先來變個戲法：
C(m＋k，k)×C(m＋j，m+k)
＝[(m＋k)!/m!×k!]×[(m＋j)!/(j－k)!×(m＋k)!]
＝(m＋j)!/m!×k!×(j－k)!
＝[(m＋j)!/m!×j!]×[j!/k!×(j－k)!]
＝C(m＋j，m)×C(j，k)
於是x被算的次數就是
C(m＋j，m)－C(m＋j，m)× C(j，1)＋C(m＋j，m)× C(j，2)＋……
＋(－1)^kC(m＋j，m) C(j，k)＋……＋(－1)^jC(m＋j，m)×C(j，j)
＝C(m＋j，m)×[1－C(j，1)＋C(j，2)＋……(－1)^k C(j，k)＋……＋(－1)^j C(j，j)]
由二項式定理知道中括號裡面就是(1－x)^j的係數和，故為0，
也就是x在右式中也沒算到。