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$
  • $\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 '19 at 15:35
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Ok thanks I get it $\endgroup$ – Daniel Andersson May 22 '19 at 15:35
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$
0
$\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$

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.