Asymptotic Behavior of a Sum with Binomial Coefficients

The Problem:

Find the asymptotic behavior (with respect to $n$) of the following sum $$\sum\limits_{j = 3}^n \binom{n}{j} \frac{(j - 1)!}{2\cdot n^j}. $$

Where the Problem Comes From: If we consider the random graph $G(n,p)$, i.e. the graph on $n$ vertices where each possible edge is added independently with probability $p$, then the expected number of cycles is $$ \sum\limits_{j = 3}^n \binom{n}{j} \frac{(j - 1)!}{2} p^j. $$

If we take $p = 1/n$, then we get the sum mentioned above.

What I've Done So Far: We can get a quick-and-not-so-great bound as follows: \begin{align*} \sum\limits_{j = 3}^n \binom{n}{j} \frac{(j - 1)!}{2\cdot n^j} &= \sum\limits_{j = 3}^n \frac{n!}{j\cdot(n - j)!} \frac{1}{2\cdot n^j} \\ &\leq \sum\limits_{j = 3}^n \frac{n^j}{j} \frac{1}{2\cdot n^j} \\ &= \sum\limits_{j = 3}^n \frac{1}{2\cdot j} \\ &=O(\log(n)). \end{align*}

However, based on a quick program I wrote, it seems that maybe this should actually be $O(1)$, as this sum appears to stay below $1$, even when $n = 130$ (about as large as Python will allow me before hitting an overflow error).

Using Stirling's formula (in various different ways) yielded no result. I also tried: \begin{align} \sum \binom{n}{j}\frac{(j-1)!}{2 n^j} &\leq \sum \left( \frac{e n}{j}\right)^j \frac{(j-1)!}{2 \cdot n^j} \\ &= \sum \frac{e^j (j - 1)!}{2\cdot j^j} \end{align} which diverges as $n \to \infty$. However, the sum $$ \sum \frac{\alpha^j (j - 1)!}{j^j}$$ converges for all $|\alpha| < e$. This suggests that maybe one could bound $$\binom{n}{j} \leq \left(\frac{\alpha n}{j}\right)^j $$ for some $\alpha < e$ (not depending on $n$) for all but $\log(n)$ terms; then we could break the terms up into those bounded with the constant $\alpha$ (which would converge) and the $\log(n)$ terms bounded with the constant $e$, which would also work. I haven't been able to figure out how to make that estimate work, though.

So, is this $O(1)$? Is it $O(\log(n))$? Any help (or intuition) is appreciated.

For any $j$, we have \begin{eqnarray*} \binom{n}{j} &=& \frac{1}{j!} \prod_{i=0}^{j-1} (n-i) \\ &=& \frac{n^j}{j!} \prod_{i=0}^{j-1} \left(1-\frac{i}{n}\right) \end{eqnarray*} Now suppose further that $j=o(n)$. In this case for each $0 \leq i \leq j-1$ we have the Taylor expansion $$\log\left(1-\frac{i}{n}\right) = -\frac{i}{n} +O(\frac{i^2}{n^2})=-(1+o(1))\frac{i}{n}$$ (with the constant implicit in the $o$ notation here depending only on $j$). This means we can bound $$\binom{n}{j} = \frac{n^j}{j!} \exp\left(-(1+o(1)) \sum_{i=0}^{j-1} \frac{i}{n}\right).$$ But if $i=o(\sqrt{n})$, the sum inside the exponent is $o(1)$. In other words, we have the (commonly used) asymptotic bound that

If $j$ is much smaller than $\sqrt{n}$, then $\binom{n}{j}=(1+o(1))\frac{n^j}{j!}$

Now let's see what this means for your sum. We have \begin{eqnarray*} \sum_{j=3}^{n-1} \binom{n}{j} \frac{(j-1)!}{2 n^j} &\geq& \sum_{j=3}^{n^{1/3}} \binom{n}{j} \frac{(j-1)!}{2n^j} \\ &=& (1+o(1)) \sum_{j=3}^{n^{1/3}} \frac{n^j}{j!} \frac{(j-1)!}{2 n^j} \\ &=& (\frac{1}{2}+o(1)) \sum_{j=3}^{n^{1/3}} \frac{1}{j} \\ &=& (\frac{1}{2}+o(1)) (\frac{1}{3} \log n + O(1)) \end{eqnarray*} The $\frac{1}{3}$ here can be replaced by any constant less than $1/2$. So your sum grows logarithmically with $n$.

If you're a little more careful, you can probably actually show that the sum is $(\frac{1}{4}+o(1)) \log n$. A rough sketch: For $j$ larger than $n^{1/2+o(1)}$ the same Taylor expansion gives that $\binom{n}{j}$ is much smaller than $\frac{n^j}{j! \log n}$. So the total contribution from $j$ larger than $n^{1/2+o(1)}$ is $o(1)$, the total contribution from $j$ up to $n^{1/2-o(1)}$ is roughly $\frac{1}{4} \log n$, and from your quick-and-not-so-great bound. the zone in between contributes $o(\log n)$