Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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