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$? 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?
 A: 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.
A: 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$. 
A: 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).
