Limit of sum when solving random graph problem The main problem is to prove that 
It is easy to prove that this limit is not bigger than 1 but every attempt to have better result was in vain.
 A: The idea is to break the sum into two separate parts: one for $3 \le k \le c \sqrt n$, and one for $c \sqrt n < k \le n$, for $c$ to be determined. The reason is that the fraction $$\frac{n!}{(n-k)!\,n^k}$$ undergoes a drastic change when $k = O(\sqrt n)$, from being very nearly $1$ to being a very small fraction. More precisely, we have
$$\Big(n-k\Big)^k < n(n-1)(n-2)(\dotsb)(n-k+1) < \Big(n-\frac k2\Big)^k$$
so
$$1 - \frac{k^2}{n} < \left(1 - \frac kn\right)^k < \frac{n!}{(n-k)!\,n^k} < \left(1 - \frac{k}{2n}\right)^k < e^{-k^2/2n} < 1.$$
Lower bound
For a lower bound on the sum, we will discard the upper half entirely and just consider, for $\epsilon>0$, $$\sum_{k=3}^{\epsilon \sqrt n} \frac{n!}{(n-k)!\cdot k\cdot n^k} > \sum_{k=3}^{\epsilon \sqrt n}\frac{1-\frac{k^2}{n}}{k} > \sum_{k=3}^{\epsilon \sqrt n} \frac{1 - \epsilon^2}{k}.$$
By the usual estimate on harmonic numbers, this is at least $(1-\epsilon^2 + o(1)) \log \epsilon \sqrt n = \left(\frac{1-\epsilon^2}{2} + o(1)\right) \log n$. So your limit is at least $\frac{1-\epsilon^2}{2}$ for all $\epsilon > 0$, which means it's at least $\frac12$.
Upper bound
For an upper bound on the sum, we will choose a large but constant $N>0$, break the sum apart at $$\sum_{k=3}^{N \sqrt n} \frac{n!}{(n-k)!\cdot k\cdot n^k} + \sum_{k=N\sqrt n}^n \frac{n!}{(n-k)!\cdot k\cdot n^k}$$ and consider the two parts separately. The first sum is at most $\sum_{k=3}^{N \sqrt n} \frac1k$ which is $(1+o(1)) \log N \sqrt n = \left(\frac12 + o(1)\right) \log n$. The second sum is $$\sum_{k=N\sqrt n}^n \frac{n!}{(n-k)!\cdot k\cdot n^k} < \sum_{k= N \sqrt n}^n \frac{e^{-k^2/2n}}{k}  < \sum_{k= N \sqrt n}^n \frac{e^{-(N \sqrt n)^2/2n}}{k} < \sum_{k=1}^n \frac{e^{-N^2/2}}{k}$$ which is $\left(e^{-N^2/2} + o(1)\right) \log n$. This proves that your limit is at most $\frac12 + e^{-N^2/2}$ for arbitrarily large $N$, which means it's at most $\frac12$.
