User robert - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T05:52:00Z http://mathoverflow.net/feeds/user/21808 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/89875/number-of-hyper-cube-cuts Number of Hyper-cube cuts Robert 2012-02-29T16:11:32Z 2012-03-02T19:31:25Z <p>In how many ways a single hyperplane can cut a hypercube? Two "ways" are considered different, if the sets into which they divide vertices of the hypercube are different. So e.g. a line can cut 2-dimensional hypercube in 4 + 2 = 6 ways. </p> <p>Actually, all I need to know is whether the number of those possible cuts is polynomial or exponential with respect to the number of vertices of the hypercube.</p>