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.
 A: 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)$ 
