Derivation of bound on expression involving binomial coefficient from Erdős and Rényi 1959 I'm in the process of working through Erdős and Rényi's 1959 article "On Random Graphs I".  In the proof of the first Lemma, equation 14 gives a bound on an expression involving several binomial coefficients:
$$\binom{n}{s}\frac{\displaystyle\binom{\binom{n}{2}-s(n-s)}{N_c}}{\displaystyle\binom{\binom{n}{2}}{N_c}}\le\frac{e^{(3-2c)s}}{s!}$$
where $N_c = [\frac{1}{2}n\log{n} + c n]$, $s\le n/2$ and $n > n_0$ for some $n_0$, and $[x]$ denotes the largest integer less than or equal to $x$.  (Equation 15 gives a corresponding expression for the case $s \ge n/2$.)
After spending some time playing around with Stirling's approximation and bounds such as $\left(\frac{n}{k}\right)^k \le \binom{n}{k} \le \frac{n^k}{k!} \le \left(\frac{n \cdot e}{k}\right)^k$, I don't feel that I'm any closer to understanding where this bound comes from.
It seems like there ought to be a fairly straightforward procedure for obtaining such bounds, given that the authors didn't feel any need to elaborate.  I'd be very grateful for any pointers on how to proceed!
 A: If $s$ is not too large, the inequality is correct.  This is because the quotient of binomial coefficients is
$$
\prod_{0\le i<N_c} \frac{{n\choose 2}-s(n-s)-i}{{n\choose 2}-i}
=
\prod_{0\le i<N_c} \left(1-\frac{s(n-s)}{{n\choose 2}-i}\right)
\le \exp -\frac{2s(n-s)}{n^2} N_c,
$$
so it is enough to have
$$
n^s \exp -\frac{2s(n-s)}{n^2} N_c \le e^{(3-2c)s},
$$
or, taking logarithms,
$$
- \frac{2s(n-s)}{n^2} N_c +s\log n\le (3-2c)s.
$$
Now, $N_c=\frac{1}{2}n\log n+cn-\theta$, for some $0\le\theta<1$, and inserting this into this last inequality cancels the terms $s\log n$ and $-2cs$, leaving
$$
\frac{2s(n-s)}{n^2}\theta +\frac{2s^2}{n^2}(\frac{1}{2}n\log n+cn)\le 3s,
$$
which is true if we require that $s\le n/\log n$ and that $n$ be sufficiently large.
If $s=\Omega(n)$, the inequality will not hold.  Set $s:=\lfloor n\delta \rfloor$, fix $\delta\in(0,\frac{1}{2}]$ and $c$, and let $n$ become large.  Look at the logarithms of each side.  The quotient of binomial coefficients on the left-hand side will give $$N_c \log(1-s(n-s){n\choose 2}^{-1})+O((\log n)^2)=\frac{1}{2}(n\log n) \log(1-2\delta(1-\delta)) + O(n),$$ while $\log {n\choose s}=O(n)$.  On the right-hand side, the logarithm of $1/s!$ is $-\delta n \log n + O(n)$, and $\log e^{(3-2c)s}$ is $O(n)$.  Therefore, if the inequality were true, we would have
$$
\frac{1}{2}( n\log n) \log(1-2\delta(1-\delta))+O(n)\le -\delta n\log n+O(n),
$$
but since $\frac{1}{2}\log (1-2\delta(1-\delta))>-\delta$ for all $\delta$ in $(0,\frac{1}{2}]$, this is false for large enough $n$.
The failure of the inequality for large $s$ is not a problem for the Erdős-Rényi paper.  This is because the use of this inequality (numbered (14) in the paper) is to bound the sum of the left-hand side of (14) as $s$ varies between some lower bound and $n/2$.  However, the quotient of binomial coefficients is decreasing over $0\le s\le n/2$, so if we set $s_0:=n/\log n$ and 
sum the left-hand side of (14) over $s_0\le s\le n/2$, the result will be no more than
$$
2^n \left.\binom{\binom{n}{2}-\lceil s_0\rceil(n-\lceil s_0\rceil)}{N_c}\right/\binom{\binom{n}{2}}{N_c}
\le 2^n \exp -\frac{2s_0(n-s_0)}{n^2} N_c,
$$
and taking the logarithm of the right-hand side gives
$$
n\log 2 - \frac{2s_0(n-s_0)}{n^2} (\frac{1}{2}n\log n+cn-\theta).
$$
However, if we fix $c$, this is $-n(1-\log 2)+O(n/\log n)$, which approaches $-\infty$ as $n$ becomes large.  Therefore, the right-hand side of the inequality (13) in the paper may be split into four pieces: (1) $M<s<n/\log n$, (2) $n/\log n\le s\le n/2$, (3) $n/2< s\le n-(n/\log n)$, and (4) $n-(n/\log n)<s<n-2N_c/n$.  Pieces (1) and (4) can be shown to be small by (14) and (15), (2) is small by the estimate immediately above, and (3) can also be shown to be small by the above estimate as the sum of the left-hand side of (14) does not change when $s$ is replaced by $n-s$.
