0
$\begingroup$

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|?

$\endgroup$
2
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.