0

I am working on extending the Erdös-Rényi paper "On the evolution of random graphs" (http://www.renyi.hu/~p_erdos/1960-10.pdf). In theorem 2a they calculate the number of isolated trees of order k.

I cannot understand equation (2.13):

$M(\epsilon(S))=\frac{{{n-k \choose 2} \choose N-k+1}}{{n \choose 2} \choose N}=(\frac{2N}{n^2})^{k-1}e^{\frac{-2Nk}{n}}(1+O(\frac{N}{n^2}))$.

In equation (7) they state that they often use:

${n \choose k}\sim\frac{{n^k}e^{-\frac{k^2}{2n}-\frac{k^3}{6n^2}}}{k!}$.

With this I can replicate the first part $(\frac{2N}{n^2})^{k-1}$.

Can someone explain me how to get to the second part $e^{\frac{-2Nk}{n}}$?

user3314400
  • 1

1 Answers1

0

With the help of equation (7), it can be written: \begin{equation} M(\epsilon(S)) \sim \frac{\binom{n-k}{2}^{N-k+1}}{\binom{n}{2}^N} \frac{N!}{(N-k+1)!} e^{h_{n,N}} \end{equation} with $h_{n,N} = O(\frac{N}{n^2})$, so $e^{h_{n,N}}=1+O(\frac{N}{n^2})$. Using the Sterling approximation yields: \begin{equation} \frac{N!}{(N-k+1)!} \sim N^{k-1} \end{equation} Therefore: \begin{equation} M(\epsilon(S)) \sim \frac{\binom{n-k}{2}^{N-k+1}}{\binom{n}{2}^N} N^{k-1} (1+O(\frac{N}{n^2})) \end{equation} Now, concerning your question: \begin{eqnarray} \frac{\binom{n-k}{2}^{N-k+1}}{\binom{n}{2}^N} & = & \frac{2^N}{2^{N-k+1}} \frac{(n-k)^{N-k+1}(n-k-1)^{N-k+1}}{n^N(n-1)^N}\\ & = & (\frac{2}{n^2})^{k-1} (1-\frac{k}{n})^{N-k+1} (1-\frac{k}{n-1})^{N-k+1}\\ & \sim & (\frac{2}{n^2})^{k-1} (1-\frac{k}{n})^N (1-\frac{k}{n-1})^N\\ & \sim & (\frac{2}{n^2})^{k-1} (e^{-k})^{\frac{N}{n}} (e^{-k})^{\frac{N}{n-1}}\\ & \sim & (\frac{2}{n^2})^{k-1} (e^{-k})^{\frac{N}{n}} (e^{-k})^{\frac{N}{n}}\\ & = & (\frac{2}{n^2})^{k-1} e^{\frac{-2Nk}{n}} \end{eqnarray} which allows to conclude. Hope this helps despite being a somewhat late answer.

Regards

Batman
  • 1