## Sum of combinations

Is there a quick formula to find the ratios; $\displaystyle\frac{r(k)}{rtotal}$ for $k=1 \dots n$ without calculating the numerator and the denominator where;

$\displaystyle r(k) = \sum\limits_{i=1}^{n} {{n^2 \choose (k-1)*n+i}}$ and $\displaystyle rtotal = \sum\limits_{k=0}^{n} {r(k)}$.

I know the denominator $\displaystyle rtotal={n^2 \choose 0} + {n^2 \choose 1} + \dots + {n^2 \choose n^2} = 2^{n^2}$

If I can find a formula for each numerator;

$\displaystyle r(1)={n^2 \choose 1} + \dots + {n^2 \choose n} = ?$

$\displaystyle r(2)={n^2 \choose n+1} + \dots + {n^2 \choose 2n} = ?$

$\dots$

$\displaystyle r(n)={n^2 \choose (n-1)*n+1} + \dots + {n^2 \choose n^2} = ?$

then some cancelling would be possible yielding to easier calculations. I need the ratios for $1 < n < 100$ but for $n>40$, $rtotal$ gets huge in my program.

-
 Why is the Central Limit Theorem unsatisfactory? – Douglas Zare Oct 28 2011 at 19:24 You may want to begin at $0$ in $r_{total}$ if it is meant to be all possible subsets of $n^2$ elements, otherwise it will be $2^{n^2} - 1$. – Zack Wolske Oct 28 2011 at 19:37 Zack, you are right. I edited the question. – Nick Oct 28 2011 at 20:03 Since you say you only need this up to 100, I don't see why you can't just compute it exactly using a system with proper bignums. – David Eppstein Oct 29 2011 at 7:28 David, I didn't want to deal with numbers like 2^10000 first but after learning that it is not possible to get a closed formula for the exact values, I decided to use the GMP (GNU Multiple Precision) Bignum Library. Thanks everybody. – Nick Oct 29 2011 at 19:27
show 1 more comment

If you are interested in approximations to your ratios, you may find the accepted answer (and some comments of mine) to this MathOverflow post useful: http://mathoverflow.net/questions/17202/sum-of-the-first-k-binomial-coefficients-for-fixed-n .

Essentially, the approximations are geometric series starting with the dominant term in your sums, and except for k near n/2, should serve you well, especially if you collapse adjacent terms in the form of n^2 +1 choose j. For k near n/2, Michael Lugo has some suggestions in his answer to the question above. If you do a search on "binomial coefficients sum", you will find other MathOverflow posts considering sums similar to yours which might help you.

I think getting a nice closed form for the exact values for your numerators in general is unsolvable.

-