# 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 '11 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 '11 at 19:37
Zack, you are right. I edited the question. –  Nick Oct 28 '11 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 '11 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 '11 at 19:27