2
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ Why is the Central Limit Theorem unsatisfactory? $\endgroup$
    – Douglas Zare
    Commented Oct 28, 2011 at 19:24
  • $\begingroup$ 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$. $\endgroup$
    – Zack Wolske
    Commented Oct 28, 2011 at 19:37
  • $\begingroup$ Zack, you are right. I edited the question. $\endgroup$
    – Nick
    Commented Oct 28, 2011 at 20:03
  • $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Commented Oct 29, 2011 at 7:28
  • $\begingroup$ 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. $\endgroup$
    – Nick
    Commented Oct 29, 2011 at 19:27

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .