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$?

Question

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?

Answer 1

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$.

Answer 2

Note that the set $\mathcal{S}$ of ordered pairs $(P,Q)$ with the property described can be described by the following sequence of choices. For $0\leq k\leq n$ first choose a $k$-subset $P\subseteq S$ (for which there are ${n\choose k}$ options), and then choose a subset $Q\subseteq S\setminus P$ (for which there are $2^{n-k}$ options). Thus we obtain all such pairs and we have the following count:

$$|\mathcal{S}|=\sum_{k=0}^n{n\choose k}2^{n-k}$$ By the argument given in @Andre Nicolas' solution, we have $\sum_{k=0}^n{n\choose k}2^{n-k}=3^n$ (which is cool).

Note that my solution above assumes that we count ordered pairs of such sets. If we seek to count unordered pairs, then there is a bit more we must do. Let $S(k,m)$ be the Stirling number of the $2^{nd}$ kind (i.e. $S(k,m)$ counts the number of partitions of $\{1,2,\cdots,k\}$ into exactly $m$ blocks). Then the set $\mathcal{S}^{\prime}$ you seek to count is described by the following sequence of choices. First there is unordered intersection $\phi\cap Q$ where $Q\subseteq S$ which contributes $2^n$ to the sum; note that this counts all unordered pairs with one set a singleton or at least one the empty set. For $2\leq k\leq n$ we first choose a $k$-subset $A\subseteq S$ (for which there are ${n\choose k}$ options), and then choose a partition into exactly $2$ parts (for which there are $S(k,2)$ options). Thus we obtain all such unordered pairs and

$$|\mathcal{S}^\prime|=2^n+\sum_{k=2}^n{n\choose k}S(k,2)$$

It is possible to obtain a simple formula for $S(k,2)$. In particular it is easy to obtain the recursion $S(k,m)=S(k-1,m-1)+mS(k-1,m)$ for all $2\leq k\leq m$ (consider partitions which contain $\{k\}$ as a block and those that don't) and $S(k,1)=1$ for all $k\geq1$. By induction and the recursion we can show $S(k,2)=2^{k-1}-1$ for all $k\geq2$ (noting trivially that $S(m,m)=1$ for all $m\geq1$). Hence our formula reduces to the following:

$$|\mathcal{S}^\prime|=2^n+\sum_{k=2}^n{n\choose k}S(k,2)=2^n+\sum_{k=2}^n{n\choose k}(2^{k-1}-1)$$

If you check this against your example, you'll notice that I count $14$ possible unordered pairs for a set of size $3$. Checking your example, you've counted the pairs $\{\{1\},\{2\}\}$, $\{\{2\},\{3\}\}$, and $\{\{1\},\{3\}\}$ two times each. Other than this discrepancy, our answers agree.

Answer 3

Each of the n elements of set S will have 3 choices. 1.Either join subset P & don't join subset Q 2.Either join subset Q don't join subset P 3.Neither join P nor join Q.

Therefore n elements with 3 choices gives us 3^n( 3 power n).