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$
2
  • 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, 2017 at 7:41
  • 1
    $\begingroup$ You might find this page helpful. $\endgroup$
    – Mroog
    Mar 3, 2017 at 17:27

1 Answer 1

Reset to default
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .