Combinatorics - Distributing n balls to 2 boxes

Question

Question:

How many ways there are to distribute n balls to 2 boxes such that:

a) The balls are distinguishable and the boxes are indistinguishable?

b) The balls are indistinguishable and the boxes are also indistinguishable?

---

I'm know how to solve problems in which the boxes are distinguishable. Here is my approach:

My answer:

I'm considering that the order of the balls inside the boxes is irrelevant.

a) At first, it doesn't matter which box to choose, since they are indistinguishable. So we choose 1 from our n balls and put it into a box: ${n \choose 1}$. Now we have a box with a ball and a box without a ball, which makes the boxes distinguishable and n-1 balls remaining to be distributed into those boxes. Let the remaining balls choose any of the two boxes: $2^{n-1}$. Hence, my answer is: ${n \choose 1}\cdot 2^{n-1}$.

b) At first, it doesn't matter which box to choose, since they are indistinguishable. So we choose 1 from our n balls, which are also indistinguishable, and put it in a box: we have $1$ way to do that. Now we have n-1 balls to be distributed to two distinguishable boxes (one with a ball and other without balls). Since the balls are indistinguishable, what matters here is the amount of balls in each box, therefore I used stars and bars method: $$ b1+b2=n-1 \text{ where }b1,b2\geq 0 \rightarrow {n \choose 1} $$ Hence, my answer is: ${n \choose 1}$.

---

Is it correct? If not, can someone please explain what is the error in my reasoning?

Thanks!

Answer 1

Your answer to a) overcounts by a factor of $n$: For any given final distribution of balls, you could have picked any of the $n$ balls as the starter ball. So there are actually $n$ ways you would come to that distribution. If you specifically said put ball $1$ (assuming the balls are labelled $1, 2,...,n$) in a box and then distributed the others as you suggested, you would come to the right answer.

Your answer to b) is not correct. You can only say that a ball makes a box distinguishable if the ball is subsequently distinguishable, which it is not. For this one, I think you are better off just looking at sums $a+b=n$, with both $a$ and $b$ nonnegative, but remembering that $a+b$ gives the same distribution as $b+a$ since everything is indistinguishable.

Answer 2

Try a special case - say with $n=3$.

(a) Balls are distinguishable but boxes are not. Possible distributions are:

(1) All $3$ balls in the same box

(2) Balls $1$ and $2$ in one box; ball $3$ in the other box

(3) Balls $1$ and $3$ in one box; ball $2$ in the other box

(4) Balls $2$ and $3$ in one box; ball $1$ in the other box

So we have $4$ different distributions.

(b) Neither balls nor boxes are distinguishable. Possible distributions are:

(1) All $3$ balls in the same box

(2) $2$ balls in one box; $1$ ball in the other box

So we have $2$ different distributions.

Now try the cases $n=4$ and $n=5$, and then see if you can generalise these special cases.