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

A set $A$ has $n$ elements. A subset of $P$ of $A$ is chosen (with replacement) and another subset $Q$ is chosen. Find number of ways of choosing $P$ and $Q$ such that $P\cap Q=\emptyset$

If $n(P)=0$, number of subsets $Q=^nC_0+^nC_1+\cdots +^nC_n=2^n$

If $n(P)=1$, then number of subsets $Q=^nC_0+^nC_1+\cdots +^nC_{n-1}$

Adding all the cases, number of ways is $(n+1)\cdot^nC_0+n\cdot^nC_1+\cdots ^nC_n$

But answer given is $3^n$.

(I have already seen two posts on SE regarding the same question but not this method. What is the mistake I am making?)

• I will delete the post as soon as I know my mistake. – Aditya Dev Jan 8 '16 at 14:55
• What is $n(P)$? Is it cardinality of $P$? – Wojciech Karwacki Jan 8 '16 at 14:56
• Number of elements of P. – Aditya Dev Jan 8 '16 at 15:03
• You shouldn't delete your post once you know your mistake. Leave it for others to learn if they search for it. – Dustan Levenstein Jan 8 '16 at 15:04
• @EliRose I believe the $n$'s are supposed to be next to the $C$'s, which is one way to write $n$ choose $k$. – kccu Jan 8 '16 at 15:06

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

• There are n+1 number of $^nC_0$s, n number of $^nC_1$s, n-1 number of $^nC_2$ ...and only one $^nC_n$ (which is from n(P)=1 case), if I were to continue doing my mistake :) – Aditya Dev Jan 8 '16 at 16:32
• Oh I see now. I was confused because you summed the number of possibilities for $Q$ to get $2^n$ when $n(P)=0$, but you didn't use that number in your sum later on. – kccu Jan 8 '16 at 16:44

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.

• I like that. Similar reasoning to the one stating that the set of all partial functions from $A$ into $B$, where $|A| = n$ and $|B| = k$ has cardinality $(k+1)^n$. – Wojciech Karwacki Jan 8 '16 at 15:27

Then when $n(P)=1$ you have number of subsets $Q = { n-1 \choose {0}} + { n-1 \choose 1} + \dots + {n-1 \choose n-2} + { n-1 \choose n-1}$