Let $X$ be a set of $5$ elements. Find the number of ordered pairs $(A,B)$ of subsets of $X$ such that $A, B\neq \emptyset$ and $A\cap B=\emptyset$

Question

I know this question involves use of combinatorics, but all the solutions I have seen just give the equation without explaining it. Can I get an explanation, because I know the answer and I know the method, I just don’t know how to apply.

Answer 1

Let us first find all possibilities such that $A \cap B = \varnothing$.

To create such a pair, each element in $X$ has exactly $3$ possibilities: It is in only $A$, or only $B$, or in neither.

This gives you that there are $3^5 = 243$ ordered pairs $(A, B)$ such that $A \cap B = \varnothing$.

Now, we count the possibilities where one of them is empty. If $A = \varnothing$, then there are exactly $2^5$ possibilities for $B$. ($2^5$ is the total number of subsets of $X$.)
Similarly, if $B = \varnothing$, then there are $2^5$ choices for $A$.

Thus, in total there are $2^5 + 2^5 - 1 = 63$ cases where $A = \varnothing$ or $B = \varnothing$. (The $-1$ is for the double counting of the case $A = B = \varnothing$.)

Thus, the desired answer is $243 - 63 = \boxed{180}.$

Answer 2

If $|A| = k>0$ then you have ${5\choose k}$ possibilities for $A$ and $2^{5-k}-1$ possibilities for $B$ since $B\subseteq X\setminus A$ and $B\ne \emptyset$. So you have to sum (use binomial theorem): \begin{align}\sum _{k=1}^5{5\choose k}(2^{5-k}-1) &= \color{red}{\sum _{k=1}^5{5\choose k}2^{5-k}} -\color{blue}{\sum _{k=1}^5{5\choose k}}\\ &=\color{red}{(2+1)^5-2^5} -\color{blue}{(1+1)^5+1} \\&= 3^5-2^6+1\\ &= 243-64+1 =180 \end{align}