Combination with repetition with limit - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T04:00:29Z http://mathoverflow.net/feeds/question/90169 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/90169/combination-with-repetition-with-limit Combination with repetition with limit Robert 2012-03-04T00:51:48Z 2012-03-04T10:07:18Z <p>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.</p> <p>The formula I got is:</p> <p>$\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)}}$</p> <p>(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)).</p> <p>This formula can be written in a little nicer form as follows:</p> <p>$\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}}$ </p> <p>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). </p> <p>Additionally those equations may help:</p> <p>$\sum\limits_{i} (-1)^{i}{n \choose i}{n+k-1-i \choose n-1} = 0$ ,</p> <p>$\sum\limits_{i} (-1)^{i}{n \choose i}{n+k-1-2i \choose n-1} = {n \choose k}$ ,</p> <p>$\sum\limits_{i} (-1)^{i}{n \choose i}{n+k-1-(k+1)i \choose n-1} = {n + k -1 \choose k}$</p> <p>(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 <a href="http://en.wikipedia.org/wiki/Binomial_coefficient" rel="nofollow">http://en.wikipedia.org/wiki/Binomial_coefficient</a> , Knuth's "The Art of Computer Programming" or anywhere else that I looked up to now).</p> <p>The most problematic part is for sure the "hm" in the sum. </p> <p>Any help or advice will be greatly appreciated.</p> http://mathoverflow.net/questions/90169/combination-with-repetition-with-limit/90170#90170 Answer by Thierry Zell for Combination with repetition with limit Thierry Zell 2012-03-04T01:34:03Z 2012-03-04T01:34:03Z <p>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.</p> <p>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. </p> <p>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.</p> <p>I hope this helps!</p>