balls and buckets combinations with a minimum and maximum number of empty buckets

449 Views Asked by At

Given $K$ balls and $M$ buckets and the limits $L1$ and $L2$ where $0<L1<L2<M$. We distribute all balls in the buckets randomly so a bucket can end up with $0$ to $K$ balls.

How do I calculate the number of combinations that have a number of empty buckets $E$ where $L1<E<L2$?

As I understand it without the restrictions the number of combinations are $$ (K+M-1)!/(K!(M-1)!) $$ but I do not know where to go from here.

If it makes it easier we can add the restriction $K<=M$ or even $K=M$

1

There are 1 best solutions below

1
On BEST ANSWER

It looks like the bins are distinguishable. In this case, if we know which $E$ buckets are empty, we can use stars and bars (the positive integer version). So we sum over the possible $E$-subsets: $$ \sum_{\substack{\mathcal{E} \subseteq \{1,\ldots,M\} \\ L1 < |\mathcal{E}| < L2}} \binom{K-1}{M-|\mathcal{E}|-1} = \sum_{E=L1+1}^{L2-1} \binom{M}{E} \binom{K-1}{M-E-1}. $$