# Combination with repetition with limit

I have a following problem: Having n boxes, and k balls where each box can contain maximum of m balls, we randomly insert the balls to the boxes. What is the expected number of non-empty boxes after the operation? If anyone would point me to sources when that problem was studied or solved I would be grateful, below I present what I managed to get myself.

The formula I got is:

$\frac{\sum\limits_{i=\lceil \frac{k}{m}\rceil}^{k} i{n \choose i} \sum\limits_{h=0}^{\lfloor \frac{k-i}{m}\rfloor} (-1)^{h}{i \choose h} {k-1-hm \choose k-i-hm}}{\sum\limits_{i=0}^{\lfloor \frac{k}{m+1} \rfloor} (-1)^{i}{n \choose i}{n+k-1-i(l+1) \choose k-i(m+1)}}$

(By a computer program I wrote I already checked it on many input values, and it always worked. Explanation of the formula (the sum limits may be largely ignored, they just say outside where addends would be 0 anyway): In denominator I count all combinations that keep the max limit given. First component (for i = 0) is just a regular combination with repetition, then I subtract all that have at least 1 box overfilled, then I need to add those that have at least 2 box overfilled (since earlier I counted them too many times) and so on according to inclusion-exclusion principle. In numerator situation is similar, yet every time I choose just i boxes that can be used (i.e. only them can be non-empty)).

This formula can be written in a little nicer form as follows:

$\frac{\sum\limits_{i=\lceil \frac{k}{m}\rceil}^{k} i{n \choose i} \sum\limits_{h=0}^{\lfloor \frac{k-i}{m}\rfloor} (-1)^{h}{i \choose h} {k-1-hm \choose i-1}}{\sum\limits_{i=0}^{\lfloor \frac{k}{m+1} \rfloor} (-1)^{i}{n \choose i}{n+k-1-i(m+1) \choose n-1}}$

But apart from that I don't know how to convert it to a digestible (i.e. reasonably efficiently computable) one. At this point I am not considering approximating, yet if someone had a good advice there, I would be grateful too (approximating every binomial separately doesn't seem to be a good idea).

$\sum\limits_{i} (-1)^{i}{n \choose i}{n+k-1-i \choose n-1} = 0$ ,

$\sum\limits_{i} (-1)^{i}{n \choose i}{n+k-1-2i \choose n-1} = {n \choose k}$ ,

$\sum\limits_{i} (-1)^{i}{n \choose i}{n+k-1-(k+1)i \choose n-1} = {n + k -1 \choose k}$

(they come from taking the denominator, and setting max limit to respectively 0, 1, k, which respectively means no such combinations, combinations without repetition, combinations with repetition. Same can be done with nominator. Those equations may be actually new, since I didn't see them at http://en.wikipedia.org/wiki/Binomial_coefficient , Knuth's "The Art of Computer Programming" or anywhere else that I looked up to now).

The most problematic part is for sure the "hm" in the sum.

Any help or advice will be greatly appreciated.

• I removed the "nt.number-theory" tag, which doesn't seem very relevant – David Loeffler Mar 4 '12 at 10:07
• I think in case $k \ge (n-1)m$ a simpler formula (i.e. no sum in denominator and a single sum in nominator) is possible. The question is, if this case is of relevance to you ? – Ralph Mar 4 '12 at 19:32

Let $X$ be the number of empty boxes, and let $X_i$ be the random variable which is $0$ if box #$i$ is not empty and $1$ otherwise, so that $X=X_1 + \cdots +X_n.$ Then, $$\mathbb{E}(X)=\mathbb{E}(X_1)+\cdots+\mathbb{E}(X_n)=n\mathbb{E}(X_1).$$ Now, $\mathbb{E}(X_1)=\mathbb{P}(X_1=1)$ which is easy to compute since it's just the probability of distributing the balls so that box #1 is empty, which is a classical application of inclusion-exclusion and the combination with repetition formula.