# Understanding $n$ Balls into $m$ Boxes

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

• 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. – Crostul Mar 3 '17 at 7:41

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