Number of ways of choosing two subsets $P$ and $Q$ such that $P\cap Q=\emptyset$

For the case $n(P)=1$, you should have $${{n−1}\choose 0}+{{n−1}\choose 1}+\cdots+{{n−1}\choose {n−1}}=2^{n-1}$$ because you are not allowed to include any elements of $P$ (of which there is $1$) when you choose elements for $Q$. So in general, when $n(P)=k$, the number of possibilities for $Q$ is $${{n-k}\choose 0}+{{n-k}\choose 1}+\cdots+{{n-k}\choose{n-k}}=2^{n-k}$$ because there are $k$ elements (the elements of $P$) that you must exclude when choosing elements for $Q$.

Now when you add all the cases, it's not clear where the numbers are coming from. How do you get the coefficients $n+1$ and $n$ and so on? You should add up over all the cases (which are disjoint) the number of possibilities for $P$ times the number of possibilities for $Q$. When $n(P)=k$, there are $n \choose k$ possibilities for what the set $P$ is. We already computed that there are $2^{n-k}$ possibilities for $Q$ given $P$. So in total there are ${n\choose k}\cdot 2^{n-k}$ possibilities for $P$ and $Q$ when $n(P)=k$. So the answer is $$\sum_{k=0}^n{n\choose k}\cdot 2^{n-k}=3^k.$$ (You can use the binomial theorem to compute this sum.)


Others have talked about your method; here's a different way of looking at it.

Given a set of size $n$, there are $2^n$ subsets. This is because we can construct a subset by, for each element $x \in A$, making an independent choice: either $x$ is in the subset, or it is not.

So there's an analogous way to see why $3^n$ is correct for this problem -- for each element of $A$, there are three options: either it's in $P$, it's in $Q$, or it's in neither.


An easy way to think about the problem- Each of the elements in the set A has three options- go into set P, go into set Q or go into neither. It can't go into both since the intersection of P and Q is the null set.

Therefore 3^n ways of forming subsets P and Q