I've basically been looking for a simple explanation for the inclusion-exclusion principle. I've failed to find examples of this method on sets larger than 3, and have only found a different stackexchange question that had this for a set of four.
|A∪B∪C∪D|=|A|+|B|+|C|+|D|} all singletons
−(|A∩B|+|A∩C|+|A∩D|+|B∩C|+|B∩D|+|C∩D|)} all pairs
+(|A∩B∩C|+|A∩B∩D|+|A∩C∩D|+|B∩C∩D|)} all triples
−|A∩B∩C∩D|} all quadruples
My question is, for larger sets, does does it simply continue the pattern of adding and subtracting? That is, would the inclusion-exclusion principle for five sets basically be the same as the one above, but adding |A∩B∩C∩D∩E| (and the sets including E for the other ones)? And for a six sets, it would be that, minus |A∩B∩C∩D∩E∩F|?
Best Answer
In short, yes.
Start with the definitions for two and three sets: \begin{align} |A \cup B| & = |A|+|B|\\ & −(|A\cap B|) \\ \\ |A \cup B \cup C'| & = |A|+|B|+|C'|\\ & −(|A\cap B|+|A\cap C'|+|B\cap C'|)\\ & +|A\cap B\cap C'| \end{align}
Note that for $n$ sets, there will be ${n\choose k}$ k-intersection sets. If you added the null set up front, then the total number of summands would be the sum of the entries of $n^{th}$ row of Pascal's Triangle, which always sums to $2^n$. In other words, each time you add a set you will double the number of summands in the inclusion-exclusion principle formula.
So for four sets, we expect $2^4 = 16$ summands. Let's see if we can derive it.
Let $C' = C \cup D$, substitute and distribute to derive the new formula for four sets.
$|A \cup B \cup (C \cup D)|$
\begin{align} & =|A|+|B|+\color{red}{|C\cup D|}\\ & −\big(|A\cap B|+\color{blue}{|A\cap (C\cup D)|}+\color{green}{|B\cap (C\cup D)|}\big)\\ & +\color{orange}{|A\cap B\cap (C\cup D)|}\\ \\ & =|A|+|B|+\color{red}{|C|+|D| - |C\cap D|}\\ & −\big(|A\cap B|+\color{blue}{|(A\cap C)\cup(A\cap D)|}+\color{green}{|(B\cap C)\cup(B\cap D)|}\big)\\ & +\color{orange}{|(A\cap B\cap C)\cup(A\cap B\cap D)|}\\ \\ & = |A|+|B|+\color{red}{|C|+|D|-|C\cap D|}\\ &− (|A\cap B\big|+ \color{blue}{|A\cap C|+|A\cap D|-|(A\cap C)\cap (A\cap D)|} +\color{green}{|B\cap C|+|B\cap D|-|(B\cap C)\cap (B\cap D)|})\\ &+\color{orange}{|A\cap B\cap C|+|A\cap B\cap D|}\\ &-\color{orange}{|(A\cap B\cap C)\cap (A\cap B\cap D)|}\\ \\ & = |A|+|B|+\color{red}{|C|+|D|}\\ &− (|A\cap B\big|+ \color{blue}{|A\cap C|+|A\cap D|} +\color{green}{|B\cap C|+|B\cap D|} +\color{red}{|C\cap D|})\\ &+\color{orange}{|A\cap B\cap C|+|A\cap B\cap D|} +\color{blue}{|(A\cap C)\cap (A\cap D)|} +\color{green}{|(B\cap C)\cap (B\cap D)|}\\ &-\color{orange}{|(A\cap B\cap C)\cap (A\cap B\cap D)|}\\ \\ & = |A|+|B|+\color{red}{|C|+|D|}\\ &− (|A\cap B\big|+ \color{blue}{|A\cap C|+|A\cap D|} +\color{green}{|B\cap C|+|B\cap D|} +\color{red}{|C\cap D|})\\ &+\color{orange}{|A\cap B\cap C|+|A\cap B\cap D|} +\color{blue}{|A\cap C\cap D|} +\color{green}{|B\cap C\cap D|}\\ &-\color{orange}{|A\cap B\cap C\cap D|}\\ \\ &=|A \cup B \cup C \cup D|\\ \\ \end{align}
If you want to try five and six sets, you'll have 31 and 63 summands, respectively.