Occupancy theorem

In combinatorial mathematics, the occupancy theorem states that the number of ways of putting r indistinguishable balls into n buckets is

${n+r-1 \choose r} = {n+r-1 \choose n-1}.$

Furthermore, the number of ways of putting r indistinguishable balls into n buckets, leaving none empty is

${r-1 \choose r-n} = {r-1 \choose n-1}.$

Applications

This has many applications in many areas where the problem can be reduced to the problem stated above.

For example: Take 12 red and 3 yellow cards, shuffle them and deal them in such a way that all the red cards before the first yellow card go to player 1, between the 1st and 2nd second yellow cards go to player 2, and so on.

Q: Find Pr(Everyone has at least 1 card)

A: The number of allocations of 12 balls (red cards) to 4 buckets (players) is $15 \choose 3$. The number of allocations where each player gets at least one card is $11 \choose 3$, so the probability is $\frac{{11 \choose 8}}{{15 \choose 3}} = \frac{33}{91}$.

See also

• Multiset coefficients for an explanation of the result