3
$\begingroup$

$3$ balls are tossed into $3$ boxes. In how many ways can that be done? Well, I did in the following way.

We have $5$ objects: $3$ balls and $2$ walls of boxes. So a configuration, for example:

00|0|

meaning : $2$ balls are in the left box, one ball is in the center box and one box is empty. Thus, to count all ways I took ${5 \choose 2} = 10$. But answer is $3^3$. Where I am wrong?

$\endgroup$
  • $\begingroup$ Are the balls labelled, or not? (That is, is the configuration "1|3|2" different from the configuration "1|2|3"?) $\endgroup$ – Billy Jun 30 '13 at 14:29
  • $\begingroup$ Hm... I think no, they aren't. But why do we care? $\endgroup$ – mechanician Jun 30 '13 at 14:33
  • 3
    $\begingroup$ For the obvious reason - if the balls are labelled, then "1|3|2" and "1|2|3" are different configurations, and if they're not, then "o|o|o" and "o|o|o" are the same configuration. So our method of counting is going to have to be different. If they're labelled, i.e. all the balls look different, then there are $3^3$ choices: choose which box 1 goes in, then choose which box 2 goes in, then choose which box 3 goes in, and there are 3 choices at each step (and all lead to different configurations). If they're not labelled, there are $\binom{5}{2}$ choices, as you said. $\endgroup$ – Billy Jun 30 '13 at 14:35
  • 3
    $\begingroup$ (I'm also assuming the boxes are labelled, of course. If both the boxes and the balls are unlabelled, there are only 3 choices, corresponding to ooo||, oo|o| and o|o|o. Do you see why labelling is important?) $\endgroup$ – Billy Jun 30 '13 at 14:37
  • $\begingroup$ Yes, I think I get it. Thanks a lot) $\endgroup$ – mechanician Jun 30 '13 at 14:38
4
$\begingroup$

Let's consider the general situation with $n$ balls and $k$ boxes. Then you have four different cases:

  • If both the balls and the boxes are distinguishable (what the comments and the other answer termed "labelled"), then it matters which ball goes to which box, and you have a total of $k^n$ possibilities, for three balls and three boxes that is §3^3$. That's obviously what was assumed for the given answer.

  • If the boxes are distinguishable, but the balls are not, then your reasoning is exactly the correct one, and you get a total of ${n+k-1\choose n} = {n+k-1 \choose k-1}$ possibilities. For $n=k=3$, ${5 \choose 2}$.

  • If the balls are distinguishable, but the boxes are not, I don't know a general formula, but you can calculate the number as follows:

    • The first ball has only one choice, since all boxes are indistinguishable.
    • The second ball has two choices (unless there's only one box total): Either it goes into the same box as the first, or it goes to a new one.
    • As long as there's more than one unoccupied box, any time a ball goes to a new box, the number of choices for the later balls grows by one.
    • As soon as all but one box contain a ball, the boxes are effectively labelled by the balls inside, and therefore the rest of the balls (if any) follow the rules of labelled boxes.

    For three balls and three boxes, this way we get five possibilities: 123||, 12|3|, 13|2|, 1|23|, 1|2|3

    Edit: For $n=k$, the number is given by Sloane's A000110

  • If neither the balls nor the boxes are indistinguishable, the number of possibilities equals the number of ways to write sums of exactly $k$ nonnegative integers adding up to $n$. As was noted in the comments, for three balls and three boxes this gives just three possibilities: ooo||, oo|o|, o|o|o

$\endgroup$
1
$\begingroup$

As discussed in the comments, i think the boxes and the balls are labelled. So if we consider a box, there are 3 possibilities:in that box, there are 1,2 or 3 balls( i am not considering 0 since it would mean all the balls are in other boxes). So if i consider the following, total no. of cases is $3^3$.

And if the boxes are not labeled, your answer is correct.

$\endgroup$
  • $\begingroup$ If the balls are not labelled, but the boxes are, his answer is correct. If the boxes are not labelled, but the balls are, the answer is different. $\endgroup$ – celtschk Jun 30 '13 at 15:14

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.