Simple combinatorics - inclusion and exclusion problem

62 Views Asked by At

There are 3 groups ${{A}_{1}},{{A}_{2}},{{A}_{3}}$ What we know about them : \begin{align} & |{{A}_{1}}|=|{{A}_{2}}|=|{{A}_{3}}|=n \\ & |{{A}_{1}}\cup {{A}_{3}}|=2n-q \\ & {{A}_{1}}\cap {{A}_{2}}\subseteq {{A}_{3}} \\ & |{{A}_{2}}\cup {{A}_{3}}|=2n-p \\ \end{align} I need to find out the $|{{A}_{1}}\cup {{A}_{2}}\cup {{A}_{3}}|$ =? (only depend on n,p,q)
So what I did : \begin{align} & |{{A}_{1}}\cup {{A}_{3}}|=|{{A}_{1}}|+|{{A}_{3}}|-|{{A}_{1}}\cap {{A}_{3}}|=2n-q \\ & 2n-|{{A}_{1}}\cap {{A}_{3}}|=2n-q \\ & |{{A}_{1}}\cap {{A}_{3}}|=q \\ & \\ & |{{A}_{2}}\cup {{A}_{3}}|=|{{A}_{2}}|+|{{A}_{3}}|-|{{A}_{2}}\cap {{A}_{3}}|=2n-p \\ & 2n-|{{A}_{2}}\cap {{A}_{3}}|=2n-p \\ & |{{A}_{2}}\cap {{A}_{3}}|=p \\ & \\ & |{{A}_{1}}\cup {{A}_{2}}\cup {{A}_{3}}|=|{{A}_{1}}|+|{{A}_{2}}|+|{{A}_{3}}|-|{{A}_{1}}\cap {{A}_{2}}|-|{{A}_{1}}\cap {{A}_{3}}|-|{{A}_{2}}\cap {{A}_{3}}|+|{{A}_{1}}\cap {{A}_{2}}\cap {{A}_{3}}|= \\ & 3n-|{{A}_{1}}\cap {{A}_{3}}|-q-p+|{{A}_{1}}\cap {{A}_{2}}\cap {{A}_{3}}| \\ \end{align}

What I know from the fact that : \begin{align} |{{A}_{1}}\cap {{A}_{2}}|\subseteq {{A}_{3}} \end{align}
is that \begin{align} \|{{A}_{1}}\cap {{A}_{2}}|\le n\ \end{align}, And I don't know how to continue

2

There are 2 best solutions below

0
On BEST ANSWER

$|A_1 \cup A_3|=2n-q \implies A_1$ and $A_3$ have $q$ items in common.

$|A_2 \cup A_3|=2n-p \implies A_2$ and $A_3$ have $p$ items in common.

$A_1 \cap A_2 \subseteq A_3 \implies A_1$ and $A_2$ have no common items that are not also common to $A_3$.

Therefore, $|A_1 \cup A_2 \cup A_3|=3n-q-p$.

0
On

The in-and-out formula for three sets: $$|A_1\cup A_2\cup A_3|=|A_1|+|A_2|+|A_3|-|A_1\cap A_2|-|A_1\cap A_3|-|A_2\cap A_3|+|A_1\cap A_2\cap A_3|.$$ However, since $A_1\cap A_2\cap A_3=A_1\cap A_2$, this simplifies to $$|A_1\cup A_2\cup A_3|=|A_1|+|A_2|+|A_3|-|A_1\cap A_3|-|A_2\cap A_3|$$ which as you know is equal to $3n-q-p$.