0
$\begingroup$

Anyone know where I can find the Inclusion-Exclusion Principle for five sets? I tried to use google but found nothing. Inclusion-Exclusion Principle for 4 sets are: \begin{align} &|A\cup B\cup C\cup D|\\[3pt] &=|A|+|B|+|C|+|D|\Big\}\text{ all singletons}\\ &-(|A\cap B|+|A\cap C|+|A\cap D|+|B\cap C|+|B\cap D|+|C\cap D|)\Big\}\text{ all pairs}\\ &+(|A\cap B\cap C|+|A\cap B\cap D|+|A\cap C\cap D|+|B\cap C\cap D|)\Big\}\text{ all triples}\\ &-|A\cap B\cap C\cap D|\Big\}\text{ all quadruples}\\ \end{align}

$\endgroup$
1
  • $\begingroup$ Yes you have to proceed in much the same way to get to 5 sets as well. In the case of 5 sets, you'll have five quadruples and one quintuple. $\endgroup$
    – Vizag
    May 22, 2019 at 15:35

3 Answers 3

8
$\begingroup$

All singles - all pairs + all triples - all quadruples + all quintuples.

$\endgroup$
1
  • $\begingroup$ Ok thanks I get it $\endgroup$ May 22, 2019 at 15:35
2
$\begingroup$

We have \begin{align} |A_1\cup A_2 \cup A_3 \cup A_4 \cup A_5| =& |A_1|+|A_2|+|A_3|+|A_4 |+|A_5| \\ & -|A_1\cap A_2| -|A_1\cap A_3| -|A_1\cap A_4| -|A_1\cap A_5| \\ & -|A_2\cap A_3| -|A_2\cap A_4| -|A_2\cap A_5| \\ & -|A_3\cap A_4| -|A_3\cap A_5| \\ & -|A_4\cap A_5| \\ & +|A_1\cap A_2\cap A_3| +|A_1\cap A_2\cap A_4| +|A_1\cap A_2\cap A_5| \\ & +|A_1\cap A_3\cap A_4| +|A_1\cap A_3\cap A_5| \\ & +|A_1\cap A_4\cap A_5| \\ & +|A_2\cap A_3\cap A_4| +|A_2\cap A_3\cap A_5| \\ & +|A_2\cap A_4\cap A_5| \\ & +|A_3\cap A_4\cap A_5| \\ & -|A_1\cap A_2\cap A_3 \cap A_4| \\& -|A_1\cap A_2\cap A_3 \cap A_5| \\& -|A_1\cap A_2\cap A_4 \cap A_5| \\& -|A_1\cap A_3\cap A_4 \cap A_5| \\& -|A_2\cap A_3\cap A_4 \cap A_5| \\ & +|A_1\cap A_2\cap A_3\cap A_4 \cap A_5| \end{align}

$\endgroup$
1
$\begingroup$

The Inclusion-Exclusion principle for $n$ sets can be found here for future reference. https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle

The Pattern indeed continues, i.e. $$|\cup^{n}_{i=1} A_i|=\sum |\text{Singletons}|-\sum |\text{Pairs}|+\sum |\text{Triples}|- \sum |\text{Quadruples}|+...+(-1)^{n+1} |\text{n-tuples}|$$

The inductive proof can be found here: https://proofwiki.org/wiki/Inclusion-Exclusion_Principle

Just consider the additive function used in the proof to be the function returning the size of a set. So if $|A|=n$, then $f(A)=n$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .