0
$\begingroup$

I have problems understanding the problem of how many different ways are there to put $n$ balls into $m$ boxes?

Suppose Different balls, different boxes. The boxes are allowed to be empty. In this case we can order the balls by $1,2,3,...$ and the cells by $1, 2, 3,...$. Take ball 1. We can put it in cell $1$ or $2$ or $3 ...$ or $m$. In other words for each ball there are $m$ choices of where to put it. Consequently the total number of ways are $m \times m \times m \times ... \times m = m^n$

My question is why the total is not $n^m$ since for each box there are $n$ choices of balls?

Thank you

$\endgroup$
  • 1
    $\begingroup$ When you put a ball into a box, you are choosing a box for that ball. Instead, every box may be assigned to more than one ball. $\endgroup$ – Crostul Mar 3 '17 at 7:41
  • 1
    $\begingroup$ You might find this page helpful. $\endgroup$ – Mroog Mar 3 '17 at 17:27
2
$\begingroup$

The key is understanding why this is the result of multiplication. Each time you make a choice of box, the next step can occur for any of the possible $m$ first steps. Imagine actually doing this, first ball by ball, and then doing it over again box by box.

Going ball by ball: for the "first" ball you have $m$ choices of box. Put it in a box. Now, you only have $n-1$ balls left, but you still have $m$ bins. You can no longer put that ball anywhere. So for the "second" ball you can put it in any of the $m$ bins.

Going box by box: for the "first" box you have $m$ choices, pick one and put a ball in it. Now you have $n-1$ balls left but you still have $m$ boxes. So the "second" box could be the same as the first box.

Think about a simple example with two balls and three boxes.

Going ball by ball: place the "first" ball in a box. Either you put it in box $a,b,$ or $c$.

If you put it in box $a$ you can still put the second ball in box $a,b,$ or $c$.

If you put it in box $b$ you can still put the second ball in box $a,b,$ or $c$.

If you put it in box $c$ you can still put the second ball in box $a,b,$ or $c$.

So your possibilities are $(aa), (ab), (ac), (bb), (ba), (bc), (cc), (ca), (cb)$

Going box by box: pick a box, and place a ball in it.

If you pick box $a$ you can still put the second ball in box $a,b,$ or $c$.

If you pick box $b$ you can still put the second ball in box $a,b,$ or $c$.

If you pick box $c$ you can still put the second ball in box $a,b,$ or $c$.

So your possibilities are $(aa), (ab), (ac), (bb), (ba), (bc), (cc), (ca), (cb)$

$\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.