A Proof of the Method of Inclusion-Exclusion July 25, 2011Noah FormanThroughout these notes we will use [n] to denote the set of positive integers no greater than n,[n] = {1, 2, · · · , n − 1, n}.Theorem 1. If A1, A2, · · · , Anare sets, thenn[j=1Aj=X∅6=I⊆[n](−1)|I|+1\j∈IAj.And, if each of the Aiare subsets of some universe U (so that¯Ai= U − Ai), thenn\i=1¯Ai= |U| −n[j=1Aj= |U| +X∅6=I⊆[n](−1)|I|\j∈IAj.So, for example, if n = 4, then the first of these claims asserts that|A1∪ A2∪ A3∪ A4| = |A1| + |A2| + |A3| + |A4|− |A1∩ A2| − |A1∩ A3| − |A1∩ A4| − |A2∩ A3| − |A2∩ A4| − |A3∩ A4|+ |A1∪ A2∪ A3| + |A1∪ A2∪ A4| + |A1∪ A3∪ A4| + |A2∪ A3∪ A4|− |A1∩ A2∩ A3∩ A4|.The terms in the first row of this expression correspond to I = {1}, I = {2}, I = {3} and I = {4}.The terms in the second row then correspond to I = {1, 2}, I = {1, 3} and so on.We will only prove the first equation of the theorem, since the second follows as a consequence.Proof. Let A =Snj=1Aj. We will begin with the formula on the left, and show that it equals |A|.Our strategy will be to manipulate that sum until it becomesPx∈A1, which equals |A|.X∅6=I⊆[n](−1)|I|+1\j∈IAj=X∅6=I⊆[n](−1)|I|+1Xx∈A1 if x ∈\j∈IAj0 otherwise=Xx∈AX∅6=I⊆[n](−1)|I|+11 if x ∈\j∈IAj0 otherwise.Let J(x) := {j ∈ [n] : x ∈ Aj}. So, for example, if x ∈ A1and x ∈ A5, but x 6∈ Ajfor any otherj, then J (x) = {1, 5}.Then, given some I ⊆ [n], it follows that x ∈Tj∈IAjif and only if I ⊆ J(x) (make sure thatyou understand and agree with this claim before you move on in the proof). SoXx∈AX∅6=I⊆[n](−1)|I|+11 if x ∈\j∈IAj0 otherwise.=Xx∈AX∅6=I⊆[n](−1)|I|+11 if I ⊆ J (x)0 otherwise=Xx∈AnXm=1XI ⊆ [n];|I| = m(−1)m+11 if I ⊆ J (x)0 otherwise=Xx∈A"nXm=1(−1)m+1|{I ⊆ [n] : |I| = m, I ⊆ J(x)}|#=nXl=1Xx ∈ A;|J(x)| = lnXm=1(−1)m+1lmif m ≤ l0 otherwise=nXl=1Xx ∈ A;|J(x)| = l"lXm=1(−1)m+1lm.#We now consider the term within the brackets,lXm=1(−1)m+1lm.(1)First, we observe that, by the binomial theorem,lXm=0(−1)m+1lm= −lXm=0(−1)mlm= −(1 − 1)l= 0.(2)The only difference between the sum in (2) and that in (1) is that the sum starts at m = 0 ratherthan 1. SolXm=1(−1)m+1lm= lXm=0(−1)m+1lm!− (−1)1l0= 1.Therefore, the quantity in (1) is always 1, regardless of x and l. SoX∅6=I⊆[n](−1)|I|+1\j∈IAj=nXl=1Xx ∈ A;|J(x)| = l1=Xx∈A1=
View Full Document
Unlocking...