4
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ 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 :) $\endgroup$ – Aditya Dev Jan 8 '16 at 16:32
  • $\begingroup$ 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. $\endgroup$ – kccu Jan 8 '16 at 16:44
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Wojciech Karwacki Jan 8 '16 at 15:27
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.