Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

I didn't get the chance to work out the precise formula, but maybe this will help. It will give you a shorter answer anyway. In a nutshell: linearity of expectation is your friend.

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.

This way, you will get something much simpler. There is still an alternating sum, and there is no way around that, but there only one level of summation rather than the two nested levels in your formulas.

I hope this helps!

share|improve this answer
    
It seems to me that you still get a double sum by this method, assuming that the balls are indistinguishable. If the balls are distinguishable, then no bounded number of sums will suffice. –  Richard Stanley Mar 4 '12 at 3:36
    
@Robert: You might want to take Richard Stanley's word over mine... As I wrote, I didn't work out all the details, but now I guess I should. I'll be sure let you know whatever comes out of it. –  Thierry Zell Mar 4 '12 at 3:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.