Question

Question #30daf

Answer 1

The number of distributions of `n` objects among `r` boxes, if empty boxes are allowed, equals to
`((n+r-1)!)/((n!)(r-1)!)`

Explanation:

If empty boxes are allowed, the problem is simple.
Let's model our problem using the following imaginary picture.

Assume, objects are dots on a line (so, we have `n` dots), and vertical separators that are positioned between these dots signify the boundaries between the boxes (so, we have `r-1` separators to model `r` boxes).

Any position of these `n+r-1` elements would model some distribution of objects in boxes. So, we have `(n+r-1)!` permutations.

This is great, except we did not take into account that objects are identical. That means that any permutation of dots that leaves the mutual configuration of dots and separators unchanged produces the same distribution of objects among boxes. That means, the same distribution we have counted `n!` times. So, we have to reduce our number of permutations by a factor of `n!`.
That results in `((n+r-1)!)/(n!)` distributions.

Let's analyze it further. The separators also can be permuted without distorting the distribution of objects among boxes. That means that another division must be used to compensate for over-counting. There are `(r-1)!` such permutations of `r-1` separators that result in the same object distribution among boxes.
That leaves us with the number of distributions of
`((n+r-1)!)/((n!)(r-1)!)`

This is the final answer.