# How many ways are there to put $N$ different balls in $M$ different boxes so that no box is empty.

You are given $$N$$ different balls and $$M$$ different boxes. In how many ways can one distribute the balls so that no box is empty?

I've found it hard to answer, I've listed a few cases, but it seems to be much more complicated when $$M$$ is getting bigger. I don't know how to proceed. Any help appreciated.

• If the boxes were indistinguishable, I would have thought the answer was Stirling numbers of the second kind $\lbrace{N\atop M}\rbrace$. Since they are distinguishable, you have to multiply this by $M!$, so $M! \lbrace{N\atop M}\rbrace = \sum\limits_{i=0}^{M} (-1)^{i} \binom{M}{i} (M-i)^N$ – Henry Jun 1 at 17:05

The number of ways with no restrictions is $$N^M$$. We now use inclusion exclusion. The number of ways to do so with at least $$k$$ boxes empty is $${M \choose k} \times N^{M-k}$$ (the number of ways to choose the empty boxes, and the number of ways to distribute the remaining numbers).
So we obtain the answer $$\sum_{k=0}^{M-1} {M \choose k}N^{M-k} (-1)^k$$ which is simply $$(N-1)^M$$ by considering binomial expansion.
• I do not see how this works with $N=3$ and $M=2$, where I would expect the number to be $6$ – Henry Jun 1 at 16:59