The asymptotics of the following expression I wonder the asymptotics of the expression $$\sum_{k=1}^{n} \frac{n!}{kn^k(n-k)!}$$ when $n$ tends to be infinity and don't know how to do it. I have tried Stirling approximation but I think it doens't work. I can figure out that it's in $ O(\log n)$ scale but can't figure out its relation with $ \Theta(\log n / \log\log n)$. Can anybody give a guide on how to get its asymptotics? I conjecture that it doesn't exceed $ \Theta(\log n / \log\log n)$. Thanks a lot for any help!
 A: Let us denote your sum by $S(n)$. Making Maxim's calculations in the comments more precise, we can confirm Raymond Manzoni's asymptotics (with a more precise error term). Simple manipulation of Maxim's integral gives
$$
S(n) \sim \frac{{n!}}{{n^n e^{ - n} \sqrt {2\pi n} }}\frac{1}{2}\sqrt {\frac{n}{\pi }} \left( {\int_0^{ + \infty } {e^{ - nt} t^{ - 1/2} ( - \log t)dt}  - \log 2\int_0^{ + \infty } {e^{ - nt} t^{ - 1/2} dt} } \right)
$$
up to an absolute error which is $\mathcal{O}(n^{-1})$ times the leading order. By Theorem 2 on page 70 of R. Wong's book Asymptotic Approximations of Integrals, we have
$$
\int_0^{ + \infty } {e^{ - nt} t^{ - 1/2} ( - \log t)dt}  = \sqrt {\frac{\pi }{n}} \log n\left( {1 + \frac{{2\log 2 + \gamma }}{{\log n}} + \mathcal{O}\!\left( {\frac{1}{{\log ^2 n}}} \right)} \right).
$$
Also
$$
 - \log 2\int_0^{ + \infty } {e^{ - nt} t^{ - 1/2} dt}  =  - \log 2\sqrt {\frac{\pi }{n}} 
$$
and, by Stirling's formula,
$$
\frac{{n!}}{{n^n e^{ - n} \sqrt {2\pi n} }} = 1 + \mathcal{O}\!\left( {\frac{1}{n}} \right).
$$
Collecting all the results, we finally obtain
$$
S(n) = \frac{1}{2}\log n + \frac{{\log 2 + \gamma }}{2} + \mathcal{O}\!\left( {\frac{1}{{\log n}}} \right).
$$
Taking more terms in the asymptotic expansion coming from R. Wong's theorem, we can replace the error term by an asymptotic expansion in inverse powers of $\log n$.
A: Your $k$-th term is equal to
$$\frac1k\prod_{i=0}^{k-1} (1-\frac{i}{n}).$$
The product is strictly smaller than one, so the sum is dominated by $\sum_{k=1}^n \frac1k = H_n \sim \log n,$ bearing out your $O(\log n)$ statement.
If $k > n/\log n,$ then the product is of order $o(1/k),$ so is negligeable, and for smaller $k$ it can be estimated by taking logs and approximating by the integral, so you can get the precise constant (if you use the Euler-Mclaurin formula, you will see that the integral approximation is very good).
