Ratio of large binomials in matlab

Question

I need to compute the following ratio $$ \frac{n!}{j!(n-j)!}/ \frac{n!}{(n/2)!(n/2)!}$$ I've tried to do this using nchoosek which works finte until $n\approx1000$. But I need at least $n\approx 10000$.

Is it possible to reformulate the equation in terms of "gammaln" and exponentiate the ratio at the end again? or maybe there is an easier way?

Answer 1

Assuming $n$ is even so $n/2 = m$ and $j \le m$ (otherwise $n-j < m$) you get $$ \frac{n!}{j!(n-j)!} \div \frac{n!}{(n/2)!(n/2)!} = \frac{(n/2)!(n/2)!}{j!(n-j)!} = \frac{(j+1) \times \ldots \times m}{(m+1) \times \ldots \times (2m-j)} $$ both numerator and denominator are straight integer products, should be quite quick to compute.

Answer 2

I think you have no way except using approximations! One good one is the Stirling's approximation for factorial:$$n!\approx \sqrt{2\pi n}\cdot \left({n\over e}\right)^n$$in that case you can further write$$\frac{n!}{j!(n-j)!}/ \frac{n!}{(n/2)!(n/2)!}{=\frac{1}{j!(n-j)!}/ \frac{1}{(n/2)!(n/2)!}\\\approx \frac{{\sqrt{\pi n}\cdot \left({n\over 2e}\right)^{n}}}{j!(n-j)!}}$$you can apply Stirling's approximation for $j!$ and $(n-j)!$ whenever needed.

Answer 3

I've tested your suggestions and they do work. gt6989b's solution is fast enough if you use matlab's "prod" which is vectorized. However, the restriction $j\leq m$ is quite severe.

Anyway, I've tried another approach:

    result=exp(2*gammaln(n/2+1)-gammaln(j+1)-gammaln(N-j+1));

This works surprisingly fast but has an error of order $\approx 10^{-14}$