2
$\begingroup$

I need to approximate the ratio $$ \frac{(2M)!}{(2M-N)!}\bigg/\frac{M!}{(M-N)!} $$

where $M$ and $N$ are huge, and $M\gg N$.

I tried taking the logarithm, applying Stirling's formula, and taking the exponential again but I didn't get a nice, simple order-of-magnitude answer.

Any suggestions?

$\endgroup$
  • $\begingroup$ Is that a ratio of ratios? Or is it two ratios to consider independtly $\endgroup$ – jameselmore Oct 28 '15 at 21:01
2
$\begingroup$

The product of $N$ terms each about $2M$ divided by the product of $N$ terms each about $M$ is about $2^N$, and in fact slightly more since $\frac{2M-1}{M-1} \gt 2$ etc.

For example with $M=10^6$ and $N=10^3$, this suggests something slightly bigger than $2^{1000}$. The actual value is about $2^{1000.36}$, about $28\%$ higher than the approximation.

$\endgroup$
2
$\begingroup$

That looks like $2^N$: $$ \frac{(2M)!}{(2M-N)!}\bigg/\frac{M!}{(M-N)!}=\frac{2M·(2M-1)·(2M-2)·...·(2M-N+1)}{M·(M-1)·(M-2)·...·(M-N+1)}=\prod_{i=0}^{N-1}\left(2+\frac{i}{M-i}\right) $$ As M is very large, the fraction added to $2$ is very little, so the whole expression is aproximately $2^N$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.