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).
Additionally those equations may help:
$\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.