0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – Henry Jun 1 at 17:05
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, I've found the answer is a special case of Twelvefold way. $\endgroup$ – 3usi9 Jun 1 at 15:01
  • $\begingroup$ I do not see how this works with $N=3$ and $M=2$, where I would expect the number to be $6$ $\endgroup$ – Henry Jun 1 at 16:59

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.