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

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.

share|improve this question
    
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
show 1 more comment

1 Answer

up vote 2 down vote accepted

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: 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.

Gerhard "Ask Me About System Design" Paseman, 2011.10.28

share|improve this answer
add comment

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.