0
$\begingroup$

What is the number of ways to distribute $m$ indistinguishable balls to $n$ distinguishable boxes given no box can be empty and every ball has to be in a box?

This was a programming question that I found, but I'm curious how to do this in a combinatorics method.

$\endgroup$
  • $\begingroup$ This is a classic for the stars and bars method $\endgroup$ – eepperly16 Nov 30 '17 at 9:03
  • $\begingroup$ You want to find the number of solutions of the equation $x_1 + x_2 + \ldots + x_n = m$ in the positive integers. The method for solving this problem is explained in Theorem 1 in the link eeperly16 provided. $\endgroup$ – N. F. Taussig Nov 30 '17 at 10:46
0
$\begingroup$

You can solve this using stars and bars. Since you don't want to allow empty boxes, first place one of the balls into each box. Now you have $m-n$ balls. This becomes a regular stars and bars problem, where you can partition the remaining balls, allowing empty boxes. This gives a total of ${{m-1}\choose{n-1}}$ combinations.

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