# On the precise asymptotic scaling of $n!/(n-k)!$ as $n,k \to \infty$

On page 23 of [Erdős+Rényi 1960, "On the evolution of random graphs"], the following asymptotic formula is stated without proof: $$\binom{n}{k} \sim \frac{n^k \mathrm e^{-\frac{k^2}{2n} - \frac{k^3}{6n^2}}}{k!}$$ valid for $k \in o(n^{\text{[some illegible fraction]}})$. That is, we have $$\frac{n!}{(n-k)!} \;=\; n^k \exp\left(-\tfrac{k^2}{2n} - \tfrac{k^3}{6n^2}\right) \cdot \Bigl[1 \pm o(1)\Bigr].$$ I was curious about what the limitations of the illegible upper bound on $k$ were for this approximation, and hoped that I could use at least some useful scaling for $k \in \Theta(n^{2/3})$, so I tried to rederive it. However, using Stirling's approximation for the factorial, $$n! = n^{n+\frac{1}{2}} \mathrm e^{-n}\cdot \Bigl[\sqrt{2\pi} + o(1)\Bigr],$$ the best that I could rederive was the following: \begin{align} \frac{n!}{(n-k)!} \;&=\; \frac{n^{n-k+\frac{1}{2}} n^k \mathrm e^{n-k}}{(n-k)^{n - k + \frac{1}{2}} \mathrm e^n} \cdot \Bigl[1 \pm o(1)\Bigr] \\&=\; n^k \left(1 - \frac{k}{n}\right)^{-n+k-\frac{1}{2}} \mathrm{e}^{-k} \cdot \Bigl[1 \pm o(1)\Bigr]\end{align} which looks as though it should scale like $$\frac{n!}{(n-k)!} \;\;\stackrel{\;?\,}\sim\;\; n^k \exp\Bigl( - \tfrac{k^2}{n} + \tfrac{k}{2n} \Bigr),$$ for all $k \in o(n)$. This is close, but no cigar. Is there anything that I'm missing?

-
A comment on the "illegible fraction": the denominator seems to be a $4$. The numerator looks like a $2$, which doesn't make sense. It might also be a $3$. –  Andrew Uzzell Mar 6 '13 at 19:18
@AndrewUzzell: that's more or less what I thought, too. Mind you, if it's as trivial a formula as they imply (and it doesn't seem as though it should be too hard to prove in principle if correct, right?) then it shouldn't be too hard to show it, and possibly discover that the value of the exponent plays a particular role. –  Niel de Beaudrap Mar 6 '13 at 19:19

As you say, if $n$ approaches infinity so that $k/n\to 0$, by Stirling's approximation $$k! n^{-k} \binom{n}{k} = (1 + o(1)) (1-\frac{k}{n})^{-(n-k)} e^{-k}. \qquad\ \ \ (*)$$ Then, taking logarithms and expanding in a Taylor series with remainder gives \begin{eqnarray*} \log\left((1-\frac kn)^{-(n-k)} e^{-k}\right)&=&-k-(n-k)\log(1-\frac kn)\\ &=& -k + (n-k) \left(\sum_{1\le i\le j} \frac 1i (\frac kn)^i + O((\frac kn)^{j+1})\right)\\ &=& -\sum_{1\le i\le j-1} \frac 1 {i(i+1)} \frac{k^{i+1}}{n^i}+ O(\frac{k^{j+1}}{n^j}) \end{eqnarray*} for any fixed $j\ge 1$. Exponentiating and substituting this back into $(*)$ gives, as $n\to\infty$, $$\binom{n}{k} = (1 + o(1)) \frac{n^k}{k!} \exp\left(-\sum_{1\le i\le j-1}\frac{1}{i(i+1)} \frac{k^{i+1}}{n^i} \right),\ \ \ \text{where } k=o(n^{j/(j+1)}).$$ The formula in the Erdős-Rényi paper is obtained by setting $j:=3$. The illegible exponent should then be $3/4$.