Return to Answer

$\newcommand{\lln}{\operatorname{\lln}}\newcommand{\bb}{\binom}$It is hard, if at all possible, to reconstruct the logic of Erdős and Rényi that allowed them to get \eqref{2} from \eqref{1}.

However, one can deduce from \eqref{1} a bound better than the ultimate bound in \eqref{2}. Actually, we are going to obtain the asymptotic of the upper bound in \eqref{1}.

Indeed, the upper bound on $P$ in \eqref{1} is \begin{equation*} p_n:=\sum_{s=2}^{\ln\ln n}\bb ns \sum_{r=1}^{\bb s2} \bb{\bb s2}r f_{s,r}, \end{equation*} where \begin{equation*} f_{s,r}:=\frac{\dbinom{\bb{n-s}2}{N_c-r}} {\dbinom{\bb n2} {N_c}}. \end{equation*}

Also, your definition of $N_c$ is incorrect: $N_c$ must be an integer. Let us follow the definition of $N_c$ in Erdős and Rényi's paper: \begin{equation*} N_c:=\lfloor\tfrac12\,n\ln n+cn\rfloor. \end{equation*}

Note that \begin{equation*} f_{s,r}=\frac{P_1 P_2}{P_3}, \end{equation*} where \begin{equation*} \begin{aligned} P_1&:=N_c\dotsm(N_c-r+1), \\ P_2&:=\Big(\bb n2-N_c\Big)\dotsm\Big(\bb{n-s}2-N_c+r+1\Big), \\ P_3&:=\bb n2\dotsm\Big(\bb{n-s}2+1\Big). \end{aligned} \end{equation*} Here and in what follows, $s$ is an integer in the interval $[2,\ln\ln n]$ and $r$ is an integer in the interval $[1,\bb s2]$.

To determine the asymptotics of $P_1,P_2,P_3$, we are going to use the following simple lemma, which will be proved at the end of this answer.

Lemma 1: If $a$ and $b$ are positive integers varying so that $b^3=o(a^2)$, then \begin{equation*} (a+b-1)\dotsm a\sim\Big(a+\frac{b-1}2\Big)^b. \end{equation*}

Using Lemma 1 and letting \begin{equation*} q_{n,s}:=\bb n2-\bb{n-s}2=s(n-(s+1)/2), \end{equation*} uniformly in $s,r$ as specified above we get the following (as $n\to\infty$): \begin{equation*} P_1\sim\Big(N_c-\frac{r-1}2\Big)^r =N_c^r\Big(1-\frac{r-1}{2N_c}\Big)^r\sim N_c^r, \end{equation*} \begin{equation*} P_3\sim\Big(\bb n2-\frac{q_{n,s}-1}2\Big)^{q_{n,s}} =\bb n2^{q_{n,s}}\Big(1-\frac{q_{n,s}-1}{n(n-1)}\Big)^{q_{n,s}} \\ \sim \bb n2^{q_{n,s}} e^{-s^2}, \end{equation*} \begin{equation*} \begin{aligned} P_2&\sim\Big(\bb n2-N_c-\frac{q_{n,s}-r-1}2\Big)^{q_{n,s}-r} \\ &=\bb n2^{q_{n,s}-r}\Big(1-\frac{2N_c+q_{n,s}-r-1}{n(n-1)}\Big)^{q_{n,s}-r} \\ &\sim \bb n2^{q_{n,s}-r} e^{-s\ln n-2cs-s^2}. \end{aligned} \end{equation*} So, \begin{equation*} f_{s,r}=\frac{P_1 P_2}{P_3} \sim\rho_n^r e^{-2cs}n^{-s}, \end{equation*} where \begin{equation*} \rho_n:=\frac{N_c}{\bb n2}. \end{equation*} So, \begin{equation*} \sum_{r=1}^{\bb s2} \bb{\bb s2}r f_{s,r} =\Big((1+\rho_n)^{\bb s2}-1\Big)e^{-2cs}n^{-s}\sim\rho_n\bb s2 e^{-2cs}n^{-s} \\ \sim\bb s2\frac{\ln n}n\,e^{-2cs}n^{-s}. \end{equation*} So, \begin{equation*} \begin{aligned} p_n&\sim\frac{\ln n}n\,\sum_{s=2}^{\ln\ln n}\bb ns \bb s2 e^{-2cs}n^{-s} \\ &\le\frac{\ln n}n\,\sum_{s=2}^\infty\frac1{s!} \bb s2 e^{-2cs} \\ &=C\frac{\ln n}{n}, \end{aligned} \end{equation*} where $C:=\frac{1}{2} e^{e^{-2 c}-4 c}$.

Moreover, by dominated convergence, \begin{equation*} p_n\sim C\frac{\ln n}{n}. \quad\Box \end{equation*}

It remains to present

Proof of Lemma 1: \begin{equation*} \begin{aligned} \big((a+b-1)\cdots a\big)^2&=\prod_{j=0}^{b-1}(a+j)(a+b-1-j) \\ &=\prod_{j=0}^{b-1}\Big[\Big(a+\frac{b-1}2\Big)^2-\Big(\frac{b-1}2-j\Big)^2\Big] \\ &=\Big(a+\frac{b-1}2\Big)^{2b} \prod_{j=0}^{b-1}\Big[1-\frac{(b-1-2j)^2}{(2a+b-1)^2}\Big] \\ &=\Big(a+\frac{b-1}2\Big)^{2b} \prod_{j=0}^{b-1}\Big[1-O\Big(\frac{b^2}{a^2}\Big)\Big] \\ &=\Big(a+\frac{b-1}2\Big)^{2b} \Big[1-O\Big(\frac{b^3}{a^2}\Big)\Big] \\ &\sim \Big(a+\frac{b-1}2\Big)^{2b}. \quad\Box \end{aligned} \end{equation*}

$\newcommand{\lln}{\operatorname{\lln}}\newcommand{\bb}{\binom}$We are going to deduce from \eqref{1} a bound better than the ultimate bound in \eqref{2}. Actually, we are going to obtain the exact asymptotic of the upper bound in \eqref{1}.

(In particular, it follows that the ultimate bound in \eqref{2} is not optimal. Already for this reason, it seems hard, if at all possible, to reconstruct the logic of Erdős and Rényi that allowed them to get \eqref{2} from \eqref{1}.)

To begin our consideration, note that the upper bound on $P$ in \eqref{1} is \begin{equation*} p_n:=\sum_{s=2}^{\ln\ln n}\bb ns \sum_{r=1}^{\bb s2} \bb{\bb s2}r f_{s,r}, \end{equation*} where \begin{equation*} f_{s,r}:=\frac{\dbinom{\bb{n-s}2}{N_c-r}} {\dbinom{\bb n2} {N_c}}. \end{equation*}

Note that \begin{equation*} f_{s,r}=\frac{P_1 P_2}{P_3}, \end{equation*} where \begin{equation*} \begin{aligned} P_1&:=N_c\cdots(N_c-r+1), \\ P_2&:=\Big(\bb n2-N_c\Big)\cdots\Big(\bb{n-s}2-N_c+r+1\Big), \\ P_3&:=\bb n2\cdots\Big(\bb{n-s}2+1\Big). \end{aligned} \end{equation*} Here and in what follows, $s$ is an integer in the interval $[2,\ln\ln n]$ and $r$ is an integer in the interval $[1,\bb s2]$.

To determine the asymptotics of $P_1,P_2,P_3$, we are going to use the following simple lemma, which will be proved at the end of this answer.

Lemma 1: If $a$ and $b$ are positive integers varying so that $b^3=o(a^2)$, then \begin{equation*} (a+b-1)\cdots a\sim\Big(a+\frac{b-1}2\Big)^b. \end{equation*}

Using Lemma 1 and letting \begin{equation*} q_{n,s}:=\bb n2-\bb{n-s}2=s(n-(s+1)/2), \end{equation*} uniformly in $s,r$ as specified above we get the following (as $n\to\infty$): \begin{equation*} P_1\sim\Big(N_c-\frac{r-1}2\Big)^r =N_c^r\Big(1-\frac{r-1}{2N_c}\Big)^r\sim N_c^r, \end{equation*} \begin{equation*} P_3\sim\Big(\bb n2-\frac{q_{n,s}-1}2\Big)^{q_{n,s}} =\bb n2^{q_{n,s}}\Big(1-\frac{q_{n,s}-1}{n(n-1)}\Big)^{q_{n,s}} \\ \sim \bb n2^{q_{n,s}} e^{-s^2}, \end{equation*} \begin{equation*} \begin{aligned} P_2&\sim\Big(\bb n2-N_c-\frac{q_{n,s}-r-1}2\Big)^{q_{n,s}-r} \\ &=\bb n2^{q_{n,s}-r}\Big(1-\frac{2N_c+q_{n,s}-r-1}{n(n-1)}\Big)^{q_{n,s}-r} \\ &\sim \bb n2^{q_{n,s}-r} e^{-s\ln n-2cs-s^2}. \end{aligned} \end{equation*} So, \begin{equation*} f_{s,r}=\frac{P_1 P_2}{P_3} \sim\rho_n^r e^{-2cs}n^{-s}, \end{equation*} where \begin{equation*} \rho_n:=\frac{N_c}{\bb n2}. \end{equation*} So, \begin{equation*} \sum_{r=1}^{\bb s2} \bb{\bb s2}r f_{s,r} =\Big((1+\rho_n)^{\bb s2}-1\Big)e^{-2cs}n^{-s}\sim\rho_n\bb s2 e^{-2cs}n^{-s} \\ \sim\bb s2\frac{\ln n}n\,e^{-2cs}n^{-s}. \end{equation*} So, \begin{equation*} \begin{aligned} p_n&\sim\frac{\ln n}n\,\sum_{s=2}^{\ln\ln n}\bb ns \bb s2 e^{-2cs}n^{-s} \\ &\le\frac{\ln n}n\,\sum_{s=2}^\infty\frac1{s!} \bb s2 e^{-2cs} \\ &=C\frac{\ln n}{n}, \end{aligned} \end{equation*} where $C:=\frac{1}{2} e^{e^{-2 c}-4 c}$.

Moreover, by dominated convergence, \begin{equation*} p_n\sim C\frac{\ln n}{n}. \quad\Box \end{equation*}

It remains to present

Proof of Lemma 1: \begin{equation*} \begin{aligned} \big((a+b-1)\cdots a\big)^2&=\prod_{j=0}^{b-1}(a+j)(a+b-1-j) \\ &=\prod_{j=0}^{b-1}\Big[\Big(a+\frac{b-1}2\Big)^2-\Big(\frac{b-1}2-j\Big)^2\Big] \\ &=\Big(a+\frac{b-1}2\Big)^{2b} \prod_{j=0}^{b-1}\Big[1-\frac{(b-1-2j)^2}{(2a+b-1)^2}\Big] \\ &=\Big(a+\frac{b-1}2\Big)^{2b} \prod_{j=0}^{b-1}\Big[1-O\Big(\frac{b^2}{a^2}\Big)\Big] \\ &=\Big(a+\frac{b-1}2\Big)^{2b} \Big[1-O\Big(\frac{b^3}{a^2}\Big)\Big] \\ &\sim \Big(a+\frac{b-1}2\Big)^{2b}. \quad\Box \end{aligned} \end{equation*}

$\newcommand{\lln}{\operatorname{\lln}}\newcommand{\bb}{\binom}$It is hard, if at all possible, to reconstruct the logic of Erdős and Rényi that allowed them to get (20) from (19).

However, one can deduce from (19) a bound better than the ultimate bound in (20). Actually, we are going to obtain the asymptotic of the upper bound in (19).

Indeed, the upper bound on $P$ in (19) is \begin{equation*} p_n:=\sum_{s=2}^{\ln\ln n}\bb ns \sum_{r=1}^{\bb s2} \bb{\bb s2}r f_{s,r}, \end{equation*} where \begin{equation*} f_{s,r}:=\frac{\dbinom{\bb{n-s}2}{N_c-r}} {\dbinom{\bb n2} {N_c}}. \end{equation*}

Also, your definition of $N_c$ is incorrect: $N_c$ must be an integer. Let us follow the definition of $N_c$ in Erdos and Renyi's paper: \begin{equation*} N_c:=\lfloor\tfrac12\,n\ln n+cn\rfloor. \end{equation*}

Note that \begin{equation*} f_{s,r}=\frac{P_1 P_2}{P_3}, \end{equation*} where \begin{equation*} \begin{aligned} P_1&:=N_c\cdots(N_c-r+1), \\ P_2&:=\Big(\bb n2-N_c\Big)\cdots\Big(\bb{n-s}2-N_c+r+1\Big), \\ P_3&:=\bb n2\cdots\Big(\bb{n-s}2+1\Big). \end{aligned} \end{equation*} Here and in what follows, $s$ is an integer in the interval $[2,\ln\ln n]$ and $r$ is an integer in the interval $[1,\bb s2]$.

To determine the asymptotics of $P_1,P_2,P_3$, we are going to use the following simple lemma, which will be proved at the end of this answer.

Lemma 1: If $a$ and $b$ are positive integers varying so that $b^3=o(a^2)$, then \begin{equation*} (a+b-1)\cdots a\sim\Big(a+\frac{b-1}2\Big)^b. \end{equation*}

Using Lemma 1 and letting \begin{equation*} q_{n,s}:=\bb n2-\bb{n-s}2=s(n-(s+1)/2), \end{equation*} uniformly in $s,r$ as specified above we get the following (as $n\to\infty$): \begin{equation*} P_1\sim\Big(N_c-\frac{r-1}2\Big)^r =N_c^r\Big(1-\frac{r-1}{2N_c}\Big)^r\sim N_c^r, \end{equation*} \begin{equation*} P_3\sim\Big(\bb n2-\frac{q_{n,s}-1}2\Big)^{q_{n,s}} =\bb n2^{q_{n,s}}\Big(1-\frac{q_{n,s}-1}{n(n-1)}\Big)^{q_{n,s}} \\ \sim \bb n2^{q_{n,s}} e^{-s^2}, \end{equation*} \begin{equation*} \begin{aligned} P_2&\sim\Big(\bb n2-N_c-\frac{q_{n,s}-r-1}2\Big)^{q_{n,s}-r} \\ &=\bb n2^{q_{n,s}-r}\Big(1-\frac{2N_c+q_{n,s}-r-1}{n(n-1)}\Big)^{q_{n,s}-r} \\ &\sim \bb n2^{q_{n,s}-r} e^{-s\ln n-2cs-s^2}. \end{aligned} \end{equation*} So, \begin{equation*} f_{s,r}=\frac{P_1 P_2}{P_3} \sim\rho_n^r e^{-2cs}n^{-s}, \end{equation*} where \begin{equation*} \rho_n:=\frac{N_c}{\bb n2}. \end{equation*} So, \begin{equation*} \sum_{r=1}^{\bb s2} \bb{\bb s2}r f_{s,r} =\Big((1+\rho_n)^{\bb s2}-1\Big)e^{-2cs}n^{-s}\sim\rho_n\bb s2 e^{-2cs}n^{-s} \\ \sim\bb s2\frac{\ln n}n\,e^{-2cs}n^{-s}. \end{equation*} So, \begin{equation*} \begin{aligned} p_n&\sim\frac{\ln n}n\,\sum_{s=2}^{\ln\ln n}\bb ns \bb s2 e^{-2cs}n^{-s} \\ &\le\frac{\ln n}n\,\sum_{s=2}^\infty\frac1{s!} \bb s2 e^{-2cs} \\ &=C\frac{\ln n}{n}, \end{aligned} \end{equation*} where $C:=\frac{1}{2} e^{e^{-2 c}-4 c}$.

Moreover, by dominated convergence, \begin{equation*} p_n\sim C\frac{\ln n}{n}. \quad\Box \end{equation*}

It remains to present

Proof of Lemma 1: \begin{equation*} \begin{aligned} \big((a+b-1)\cdots a\big)^2&=\prod_{j=0}^{b-1}(a+j)(a+b-1-j) \\ &=\prod_{j=0}^{b-1}\Big[\Big(a+\frac{b-1}2\Big)^2-\Big(\frac{b-1}2-j\Big)^2\Big] \\ &=\Big(a+\frac{b-1}2\Big)^{2b} \prod_{j=0}^{b-1}\Big[1-\frac{(b-1-2j)^2}{(2a+b-1)^2}\Big] \\ &=\Big(a+\frac{b-1}2\Big)^{2b} \prod_{j=0}^{b-1}\Big[1-O\Big(\frac{b^2}{a^2}\Big)\Big] \\ &=\Big(a+\frac{b-1}2\Big)^{2b} \Big[1-O\Big(\frac{b^3}{a^2}\Big)\Big] \\ &\sim \Big(a+\frac{b-1}2\Big)^{2b}. \quad\Box \end{aligned} \end{equation*}

$\newcommand{\lln}{\operatorname{\lln}}\newcommand{\bb}{\binom}$It is hard, if at all possible, to reconstruct the logic of Erdős and Rényi that allowed them to get \eqref{2} from \eqref{1}.

However, one can deduce from \eqref{1} a bound better than the ultimate bound in \eqref{2}. Actually, we are going to obtain the asymptotic of the upper bound in \eqref{1}.

Indeed, the upper bound on $P$ in \eqref{1} is \begin{equation*} p_n:=\sum_{s=2}^{\ln\ln n}\bb ns \sum_{r=1}^{\bb s2} \bb{\bb s2}r f_{s,r}, \end{equation*} where \begin{equation*} f_{s,r}:=\frac{\dbinom{\bb{n-s}2}{N_c-r}} {\dbinom{\bb n2} {N_c}}. \end{equation*}

Also, your definition of $N_c$ is incorrect: $N_c$ must be an integer. Let us follow the definition of $N_c$ in Erdős and Rényi's paper: \begin{equation*} N_c:=\lfloor\tfrac12\,n\ln n+cn\rfloor. \end{equation*}

Note that \begin{equation*} f_{s,r}=\frac{P_1 P_2}{P_3}, \end{equation*} where \begin{equation*} \begin{aligned} P_1&:=N_c\dotsm(N_c-r+1), \\ P_2&:=\Big(\bb n2-N_c\Big)\dotsm\Big(\bb{n-s}2-N_c+r+1\Big), \\ P_3&:=\bb n2\dotsm\Big(\bb{n-s}2+1\Big). \end{aligned} \end{equation*} Here and in what follows, $s$ is an integer in the interval $[2,\ln\ln n]$ and $r$ is an integer in the interval $[1,\bb s2]$.

To determine the asymptotics of $P_1,P_2,P_3$, we are going to use the following simple lemma, which will be proved at the end of this answer.

Lemma 1: If $a$ and $b$ are positive integers varying so that $b^3=o(a^2)$, then \begin{equation*} (a+b-1)\dotsm a\sim\Big(a+\frac{b-1}2\Big)^b. \end{equation*}

Using Lemma 1 and letting \begin{equation*} q_{n,s}:=\bb n2-\bb{n-s}2=s(n-(s+1)/2), \end{equation*} uniformly in $s,r$ as specified above we get the following (as $n\to\infty$): \begin{equation*} P_1\sim\Big(N_c-\frac{r-1}2\Big)^r =N_c^r\Big(1-\frac{r-1}{2N_c}\Big)^r\sim N_c^r, \end{equation*} \begin{equation*} P_3\sim\Big(\bb n2-\frac{q_{n,s}-1}2\Big)^{q_{n,s}} =\bb n2^{q_{n,s}}\Big(1-\frac{q_{n,s}-1}{n(n-1)}\Big)^{q_{n,s}} \\ \sim \bb n2^{q_{n,s}} e^{-s^2}, \end{equation*} \begin{equation*} \begin{aligned} P_2&\sim\Big(\bb n2-N_c-\frac{q_{n,s}-r-1}2\Big)^{q_{n,s}-r} \\ &=\bb n2^{q_{n,s}-r}\Big(1-\frac{2N_c+q_{n,s}-r-1}{n(n-1)}\Big)^{q_{n,s}-r} \\ &\sim \bb n2^{q_{n,s}-r} e^{-s\ln n-2cs-s^2}. \end{aligned} \end{equation*} So, \begin{equation*} f_{s,r}=\frac{P_1 P_2}{P_3} \sim\rho_n^r e^{-2cs}n^{-s}, \end{equation*} where \begin{equation*} \rho_n:=\frac{N_c}{\bb n2}. \end{equation*} So, \begin{equation*} \sum_{r=1}^{\bb s2} \bb{\bb s2}r f_{s,r} =\Big((1+\rho_n)^{\bb s2}-1\Big)e^{-2cs}n^{-s}\sim\rho_n\bb s2 e^{-2cs}n^{-s} \\ \sim\bb s2\frac{\ln n}n\,e^{-2cs}n^{-s}. \end{equation*} So, \begin{equation*} \begin{aligned} p_n&\sim\frac{\ln n}n\,\sum_{s=2}^{\ln\ln n}\bb ns \bb s2 e^{-2cs}n^{-s} \\ &\le\frac{\ln n}n\,\sum_{s=2}^\infty\frac1{s!} \bb s2 e^{-2cs} \\ &=C\frac{\ln n}{n}, \end{aligned} \end{equation*} where $C:=\frac{1}{2} e^{e^{-2 c}-4 c}$.

Moreover, by dominated convergence, \begin{equation*} p_n\sim C\frac{\ln n}{n}. \quad\Box \end{equation*}

It remains to present

Proof of Lemma 1: \begin{equation*} \begin{aligned} \big((a+b-1)\cdots a\big)^2&=\prod_{j=0}^{b-1}(a+j)(a+b-1-j) \\ &=\prod_{j=0}^{b-1}\Big[\Big(a+\frac{b-1}2\Big)^2-\Big(\frac{b-1}2-j\Big)^2\Big] \\ &=\Big(a+\frac{b-1}2\Big)^{2b} \prod_{j=0}^{b-1}\Big[1-\frac{(b-1-2j)^2}{(2a+b-1)^2}\Big] \\ &=\Big(a+\frac{b-1}2\Big)^{2b} \prod_{j=0}^{b-1}\Big[1-O\Big(\frac{b^2}{a^2}\Big)\Big] \\ &=\Big(a+\frac{b-1}2\Big)^{2b} \Big[1-O\Big(\frac{b^3}{a^2}\Big)\Big] \\ &\sim \Big(a+\frac{b-1}2\Big)^{2b}. \quad\Box \end{aligned} \end{equation*}

$\newcommand{\lln}{\operatorname{\lln}}\newcommand{\bb}{\binom}$It is hard, if at all possible, to reconstruct the logic of Erdős and Rényi that allowed them to get (20) from (19).

However, one can deduce from (19) a bound better than the ultimate bound in (20).

Indeed, the upper bound on $P$ in (19) is \begin{equation*} p_n:=\sum_{s=2}^{\ln\ln n}\bb ns \sum_{r=1}^{\bb s2} \bb{\bb s2}r f_{s,r}, \end{equation*} where \begin{equation*} f_{s,r}:=\frac{\dbinom{\bb{n-s}2}{N_c-r}} {\dbinom{\bb n2} {N_c}}. \end{equation*}

Also, your definition of $N_c$ is incorrect: $N_c$ must be an integer. Let us follow the definition of $N_c$ in Erdos and Renyi's paper: \begin{equation*} N_c:=\lfloor\tfrac12\,n\ln n+cn\rfloor. \end{equation*}

Note that \begin{equation*} f_{s,r}=\frac{P_1 P_2}{P_3}, \end{equation*} where \begin{equation*} \begin{aligned} P_1&:=N_c\cdots(N_c-r+1), \\ P_2&:=\Big(\bb n2-N_c\Big)\cdots\Big(\bb{n-s}2-N_c+r+1\Big), \\ P_3&:=\bb n2\cdots\Big(\bb{n-s}2+1\Big). \end{aligned} \end{equation*} Here and in what follows, $s$ is an integer in the interval $[2,\ln\ln n]$ and $r$ is an integer in the interval $[1,\bb s2]$.

To determine the asymptotics of $P_1,P_2,P_3$, we are going to use the following simple lemma, which will be proved at the end of this answer.

Lemma 1: If $a$ and $b$ are positive integers varying so that $b^3=o(a^2)$, then \begin{equation*} (a+b-1)\cdots a\sim\Big(a+\frac{b-1}2\Big)^b. \end{equation*}

Using Lemma 1 and letting \begin{equation*} q_{n,s}:=\bb n2-\bb{n-s}2=s(n-(s+1)/2), \end{equation*} uniformly in $s,r$ as specified above we get the following (as $n\to\infty$): \begin{equation*} P_1\sim\Big(N_c-\frac{r-1}2\Big)^r =N_c^r\Big(1-\frac{r-1}{2N_c}\Big)^r\sim N_c^r, \end{equation*} \begin{equation*} P_3\sim\Big(\bb n2-\frac{q_{n,s}-1}2\Big)^{q_{n,s}} =\bb n2^{q_{n,s}}\Big(1-\frac{q_{n,s}-1}{n(n-1)}\Big)^{q_{n,s}} \\ \sim \bb n2^{q_{n,s}} e^{-s^2}, \end{equation*} \begin{equation*} \begin{aligned} P_2&\sim\Big(\bb n2-N_c-\frac{q_{n,s}-r-1}2\Big)^{q_{n,s}-r} \\ &=\bb n2^{q_{n,s}-r}\Big(1-\frac{2N_c+q_{n,s}-r-1}{n(n-1)}\Big)^{q_{n,s}-r} \\ &\sim \bb n2^{q_{n,s}-r} e^{-s\ln n-2cs-s^2}. \end{aligned} \end{equation*} So, \begin{equation*} f_{s,r}=\frac{P_1 P_2}{P_3} \sim\rho_n^r e^{-2cs}n^{-s}, \end{equation*} where \begin{equation*} \rho_n:=\frac{N_c}{\bb n2}. \end{equation*} So, \begin{equation*} \sum_{r=1}^{\bb s2} \bb{\bb s2}r f_{s,r} =\Big((1+\rho_n)^{\bb s2}-1\Big)e^{-2cs}n^{-s}\sim\rho_n\bb s2 e^{-2cs}n^{-s} \\ \sim\bb s2\frac{\ln n}n\,e^{-2cs}n^{-s}. \end{equation*} So, \begin{equation*} \begin{aligned} p_n&\sim\frac{\ln n}n\,\sum_{s=2}^{\ln\ln n}\bb ns \bb s2 e^{-2cs}n^{-s} \\ &\le\frac{\ln n}n\,\sum_{s=2}^\infty\frac1{s!} \bb s2 e^{-2cs} \\ &=C\frac{\ln n}{n}, \end{aligned} \end{equation*} where $C:=\frac{1}{2} e^{e^{-2 c}-4 c}$. $\quad\Box$

It remains to present

Proof of Lemma 1: \begin{equation} \begin{aligned} \big((a+b-1)\cdots a\big)^2&=\prod_{j=0}^{b-1}(a+j)(a+b-1-j) \\ &=\prod_{j=0}^{b-1}\Big[\Big(a+\frac{b-1}2\Big)^2-\Big(\frac{b-1}2-j\Big)^2\Big] \\ &=\Big(a+\frac{b-1}2\Big)^{2b} \prod_{j=0}^{b-1}\Big[1-\frac{(b-1-2j)^2}{(2a+b-1)^2}\Big] \\ &=\Big(a+\frac{b-1}2\Big)^{2b} \prod_{j=0}^{b-1}\Big[1-O\Big(\frac{b^2}{a^2}\Big)\Big] \\ &=\Big(a+\frac{b-1}2\Big)^{2b} \Big[1-O\Big(\frac{b^3}{a^2}\Big)\Big] \\ &\sim \Big(a+\frac{b-1}2\Big)^{2b}. \quad\Box \end{aligned} \end{equation}

$\newcommand{\lln}{\operatorname{\lln}}\newcommand{\bb}{\binom}$It is hard, if at all possible, to reconstruct the logic of Erdős and Rényi that allowed them to get (20) from (19).

However, one can deduce from (19) a bound better than the ultimate bound in (20). Actually, we are going to obtain the asymptotic of the upper bound in (19).

Indeed, the upper bound on $P$ in (19) is \begin{equation*} p_n:=\sum_{s=2}^{\ln\ln n}\bb ns \sum_{r=1}^{\bb s2} \bb{\bb s2}r f_{s,r}, \end{equation*} where \begin{equation*} f_{s,r}:=\frac{\dbinom{\bb{n-s}2}{N_c-r}} {\dbinom{\bb n2} {N_c}}. \end{equation*}

Also, your definition of $N_c$ is incorrect: $N_c$ must be an integer. Let us follow the definition of $N_c$ in Erdos and Renyi's paper: \begin{equation*} N_c:=\lfloor\tfrac12\,n\ln n+cn\rfloor. \end{equation*}

Note that \begin{equation*} f_{s,r}=\frac{P_1 P_2}{P_3}, \end{equation*} where \begin{equation*} \begin{aligned} P_1&:=N_c\cdots(N_c-r+1), \\ P_2&:=\Big(\bb n2-N_c\Big)\cdots\Big(\bb{n-s}2-N_c+r+1\Big), \\ P_3&:=\bb n2\cdots\Big(\bb{n-s}2+1\Big). \end{aligned} \end{equation*} Here and in what follows, $s$ is an integer in the interval $[2,\ln\ln n]$ and $r$ is an integer in the interval $[1,\bb s2]$.

To determine the asymptotics of $P_1,P_2,P_3$, we are going to use the following simple lemma, which will be proved at the end of this answer.

Lemma 1: If $a$ and $b$ are positive integers varying so that $b^3=o(a^2)$, then \begin{equation*} (a+b-1)\cdots a\sim\Big(a+\frac{b-1}2\Big)^b. \end{equation*}

Using Lemma 1 and letting \begin{equation*} q_{n,s}:=\bb n2-\bb{n-s}2=s(n-(s+1)/2), \end{equation*} uniformly in $s,r$ as specified above we get the following (as $n\to\infty$): \begin{equation*} P_1\sim\Big(N_c-\frac{r-1}2\Big)^r =N_c^r\Big(1-\frac{r-1}{2N_c}\Big)^r\sim N_c^r, \end{equation*} \begin{equation*} P_3\sim\Big(\bb n2-\frac{q_{n,s}-1}2\Big)^{q_{n,s}} =\bb n2^{q_{n,s}}\Big(1-\frac{q_{n,s}-1}{n(n-1)}\Big)^{q_{n,s}} \\ \sim \bb n2^{q_{n,s}} e^{-s^2}, \end{equation*} \begin{equation*} \begin{aligned} P_2&\sim\Big(\bb n2-N_c-\frac{q_{n,s}-r-1}2\Big)^{q_{n,s}-r} \\ &=\bb n2^{q_{n,s}-r}\Big(1-\frac{2N_c+q_{n,s}-r-1}{n(n-1)}\Big)^{q_{n,s}-r} \\ &\sim \bb n2^{q_{n,s}-r} e^{-s\ln n-2cs-s^2}. \end{aligned} \end{equation*} So, \begin{equation*} f_{s,r}=\frac{P_1 P_2}{P_3} \sim\rho_n^r e^{-2cs}n^{-s}, \end{equation*} where \begin{equation*} \rho_n:=\frac{N_c}{\bb n2}. \end{equation*} So, \begin{equation*} \sum_{r=1}^{\bb s2} \bb{\bb s2}r f_{s,r} =\Big((1+\rho_n)^{\bb s2}-1\Big)e^{-2cs}n^{-s}\sim\rho_n\bb s2 e^{-2cs}n^{-s} \\ \sim\bb s2\frac{\ln n}n\,e^{-2cs}n^{-s}. \end{equation*} So, \begin{equation*} \begin{aligned} p_n&\sim\frac{\ln n}n\,\sum_{s=2}^{\ln\ln n}\bb ns \bb s2 e^{-2cs}n^{-s} \\ &\le\frac{\ln n}n\,\sum_{s=2}^\infty\frac1{s!} \bb s2 e^{-2cs} \\ &=C\frac{\ln n}{n}, \end{aligned} \end{equation*} where $C:=\frac{1}{2} e^{e^{-2 c}-4 c}$.

Moreover, by dominated convergence, \begin{equation*} p_n\sim C\frac{\ln n}{n}. \quad\Box \end{equation*}

It remains to present

Proof of Lemma 1: \begin{equation*} \begin{aligned} \big((a+b-1)\cdots a\big)^2&=\prod_{j=0}^{b-1}(a+j)(a+b-1-j) \\ &=\prod_{j=0}^{b-1}\Big[\Big(a+\frac{b-1}2\Big)^2-\Big(\frac{b-1}2-j\Big)^2\Big] \\ &=\Big(a+\frac{b-1}2\Big)^{2b} \prod_{j=0}^{b-1}\Big[1-\frac{(b-1-2j)^2}{(2a+b-1)^2}\Big] \\ &=\Big(a+\frac{b-1}2\Big)^{2b} \prod_{j=0}^{b-1}\Big[1-O\Big(\frac{b^2}{a^2}\Big)\Big] \\ &=\Big(a+\frac{b-1}2\Big)^{2b} \Big[1-O\Big(\frac{b^3}{a^2}\Big)\Big] \\ &\sim \Big(a+\frac{b-1}2\Big)^{2b}. \quad\Box \end{aligned} \end{equation*}