Combinatorial counting Problem on Sets

Question

The number of triplets (A,B,C) where A,B,C are subsets of X = {1,2,3,...100} such that $A\bigcap B\bigcap C= \phi$ but $A \bigcap B \neq \phi$ and $B\bigcap C \neq \phi$ is how much? My approach is we have seven places to store these 100 numbers only A alone, only B alone, only C alone, only A and B together, only B and C together, only C and A together and common region A,B,C. So if entire freedom were given we could have arranged the numbers $7^{100}$ ways. But atleast one in $A\bigcap B$ means $7^{100} - 6^{100}$. Then atleast one in $B\bigcap C$ means $7^{100} - 6^{100}$. Counting them together gives $2*7^{100} - 2*6^{100}$. But we are double counting the places where atleast one element is there in these subsets. so we have to minus them. Also negate the places where elements are there in $A\bigcap B\bigcap C$. now I'm lost. Ans : $7^{100} - 2*6^{100} + 5^{100}$. Any help is thanked in advance.

Answer 1

Let $S=\{1,...,n\}$, where $n=100$.

To construct a triple $(A,B,C)$ with $A\cap B\cap C=\varnothing$, each $x\in S$ must be placed in exactly one of the $7$ sets

• $A\cap B'\cap C'$
• $B\cap C'\cap A'$
• $C\cap A'\cap B'$
• $A\cap B$
• $B\cap C$
• $C\cap A$
• $A'\cap B'\cap C'$

so we have an initial count of $7^n$.

But this is an overcount since this includes triples $(A,B,C)$ for which $A\cap B =\varnothing$, or $B\cap C =\varnothing$.

For $A\cap B=\varnothing$, we have $6$ choices for each $x\in S$, hence we have $6^n$ such triples $(A,B,C)$.

Similarly, for $B\cap C=\varnothing$, we also have $6^n$ triples.

Removing those triples from the count, our adjusted count is $7^n-2\cdot 6^n$.

But the triples where both $A\cap B =\varnothing$, and $B\cap C =\varnothing$ hold were removed twice, so we need to add back the count for those triples.

To have both $A\cap B =\varnothing$, and $B\cap C =\varnothing$, we have $5$ choices for each $x\in S$, hence we have $5^n$ such triples $(A,B,C)$.

Therefore the final count is $7^n-2\cdot 6^n+ 5^n$.