[Math] A set $S$ has $n$ elements. How many ways we can choose subsets $P$ and $Q$ of $S$, so that $P \cap Q$ is $\emptyset$

combinatorics

This is how far I could go..

example:
S = {1,2,3}
Unique possible subset pairs such that the intersection is {}
P = {}    Q = {}
P = {}    Q = {1}
P = {}    Q = {2}
P = {}    Q = {3}
P = {}    Q = {1,2}
P = {}    Q = {1,3}
P = {}    Q = {2,3}
P = {}    Q = {1,2,3}
P = {1}   Q = {2}
P = {1}   Q = {3}
P = {1}   Q = {2,3}
P = {2}   Q = {1}
P = {2}   Q = {3}
P = {2}   Q = {1,3}
P = {3}   Q = {1}
P = {3}   Q = {2}
P = {3}   Q = {1,2}
Total = 17

Subset X of $S$ with $0$ elements doesn't intersect with any subsets of $S$.

So, total pairs = ${n \choose 0} \times 2^n$

Subset $X$ of $S$ with $1$ element doesn't intersect with any subsets of $S-X$.

So, total pairs = ${n \choose 1} \times \left (2^{n-1} – 1 \right) $

$-1$ because the subset $\{\}$ of $S-X$ has already been counted.

Subset $X$ of $S$ with $2$ element doesn't intersect with any subsets of $S-X$.

So, total pairs = ${n \choose 2} \times \left (2^{n-2} – 1 \right) $

$\vdots$

while $|X| <= \frac{n}{2} $

So, total pairs are:
$$\left \{ \sum_{r=0}^{\frac{n}{2}} {{n \choose r} \times 2^{n-r}} \right \} – \left \{ \sum_{r=1}^{\frac{n}{2}} {n \choose r} \right \}$$

which works. But how do I simplify it?

Also, what would be a better approach for this problem?

Best Answer

First we look at the number of ordered pairs $(P,Q)$ such that $P\cap Q=\emptyset$. Equivalently, we count the number of functions $f:S\to\{1,2,3\}$, where $f(s)=1$ if $s\in P$, $f(s)=2$ if $s\in Q$, and $f(s)=3$ if $s$ is in neither $P$ nor $Q$. There are $3^n$ such functions.

If we want to count the unordered pairs (and the question seems to ask for that), note that in the count $3^n$, all unordered pairs appear twice, except $(\emptyset,\emptyset)$. So the number of unordered pairs is $\frac{3^n-1}{2}+1$.

Related Question