How many ways to distribute $k$ indistinguishable balls over $m$ of $n$ distinguishable bins of finite capacity $l$?

Solution 1:

First, you can select the non-empty bins in $\binom{m}{n}$ ways. So the remaining problem is to figure out how to distribute $k$ balls among $m$ bins win none getting more than $l$.

By stars and bars there are $\binom{k - 1}{m - 1}$ ways to distribute $k$ balls into $m$ bins with none empty. But this disregards the cases where some bins have more than $l$ balls. This in turn can be handled by the principle of inclusion and exclusion, considering the different sets as the solutions that violate 1, 2, ... of the constraints. Say the first bin has more than $l$ balls. Add $l$ balls to the first bin, you still have to distribute $k - l$ balls among all $m$ bins (overfilling bin number 1) so that no bin is empty, which can be done in $\binom{k - l - 1}{m - 1}$ ways. But the bin violating the constraint can be selected in $\binom{m}{1}$ ways. In all, adding in the factor given at the beginning: $$ \binom{n}{m} \sum_{j \ge 0} (-1)^j \binom{m}{j} \binom{k - j l - 1}{m - 1} $$