1
$\begingroup$

I am interested in the growth of the binomial coefficient ${n\choose n^a}$ for some fixed $a\in (1/2,1]$. Of course, for $a=1$ the binomial constantly equal to $1$. For $a<1$, computations suggest that \begin{align}\lim_{n\to\infty}\frac{\exp(n^b)}{{n\choose n^a}}=\begin{cases}0&\text{if }b\leq a\\\infty&\text{if }b>a\end{cases}\end{align} i.e., that ${n\choose n^a}$ grows slightly faster than $\exp(n^a)$ (but for example slower than $\exp(n^a\log n)$). Is there a simple form of the exact growth rate? I find it slightly surprising that the growth rate of ${n\choose n^a}$ increases with $a$ although the binomial coefficient is constantly $1$ for $a=1$.

$\endgroup$
1
$\begingroup$

This should be nice enough: $${n\choose n^a}\sim_{n\to\infty}\left(\frac{n}{n-n^a}\right)^n\left(\frac{n-n^a}{n^a}\right)^{n^a}\frac{1}{\sqrt{2\pi\left(n^a-n^{2a-1}\right)}}. $$


We have $${n\choose{n^a}}=\frac{n!}{(n-n^a)!\ n^a!},$$ but since $n-n^a$ is not an in integer for all $0<a<1$ (and $n\ne 0,1)$, making use of the $\Gamma$ function write $$\frac{\Gamma(n+1)}{\Gamma(n-n^a+1)\ \Gamma(n^a+1)}. $$ Even so, Stirling's approximation yields $$\frac{\Gamma(n+1)}{\Gamma(n-n^a+1)\ \Gamma(n^a+1)}\sim_{n\to\infty}\frac{\sqrt{2\pi n}(n/e)^n}{\sqrt{4\pi^2 n^a(n-n^a)}\left((n-n^a)/e\right)^{n-n^a}(n^a/e)^{n^a}}=\\ \frac{n^ne^{n-n^a}e^{n^a}}{e^n\sqrt{2\pi(n^a-n^{2a-1})}(n-n^a)^{n-n^a}n^{a\cdot n^a}}=\left(\frac{n}{n-n^a}\right)^n\left(\frac{n-n^a}{n^a}\right)^{n^a}\frac{1}{\sqrt{2\pi\left(n^a-n^{2a-1}\right)}}. $$


Indeed, we can see now that as $a$ approaches $1$, the binomial coefficient increases. We still need $n\to \infty$ because when $a=1$ the asymptotic formula does not hold, since two fractions in it exist for $a\ne1$, and thus $0!=1$ applies. A significant example: $$\frac{\Gamma(201)}{\Gamma\left(201-200^{0.9}\right) \ \Gamma\left(1+200^{0.9}\right)}\approx 3.9\times 10^{57} $$ but $$\frac{\Gamma(201)}{\Gamma\left(201-200^{0.999}\right) \ \Gamma\left(1+200^{0.999}\right)}\approx 264. $$

$\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.