3
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ No. For example, with 3 balls (labelled 1, 2, 3) and 3 boxes, you could have (123)()(); (12)(3)(); (13)(2)(); (23)(1)(); (1)(2)(3). A total of 5 arrangements. $\endgroup$ – paw88789 Sep 24 '18 at 15:43
  • $\begingroup$ For b) the answer is: ${n+1 \choose 1}/2$? Generalizing for k boxes: ${n+k-1 \choose k-1}/ k$? $\endgroup$ – Bruno Reis Sep 24 '18 at 16:29
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ My new answers for: a) $2^{n-1}$ and b) ${n+1 \choose 1}/2$ are correct now? $\endgroup$ – Bruno Reis Sep 24 '18 at 16:48
  • $\begingroup$ @BrunoReis (a) is correct. For (b), your answer simplifies to $\frac{n+1}{2}$. This is fine when $n$ is odd, but what about when $n$ is even e.g. when $n=4$ ? $\endgroup$ – gandalf61 Sep 25 '18 at 8:11

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.