Is there any easier way to get the asymptotic value of this sum? @Mike Spivey has proved in another question, that
$$
S(n) = \sum_{k \geq 1} \frac{n!}{k (n-k)! n^k} = \sum_{k \geq 1} \frac{n^{\underline{k}}}{k n^k} \sim \frac{1}{2} \log(n).
$$
But that proof is out of my ability to understand. So, is there more elementary way to prove it?
 A: Here is a rough argument. Filling in the details should be elementary, but challenging. I find myself reusing several ideas from this earlier question.
The sum is
$$\sum_{k=1}^n \frac{1}{k} (1-1/n)(1-2/n)\cdots (1-k/n)$$
As discussed in the earlier answer,
$$(1-1/n) (1-2/n) \cdots (1-k/n) \approx e^{-k^2/(2n)}.$$
So the sum is roughly
$$\sum_{k \geq 1} \frac{1}{k} e^{-k^2/(2n)} = \sum_{k \geq 1} \frac{1}{\sqrt{n}} \frac{\sqrt{n}}{k} e^{-(k/\sqrt{n})^2 /2}.$$
This is a Riemann sum approximation (with interval size $1/\sqrt{n}$) to the integral
$$\int_{1/\sqrt{n}}^{\infty} \frac{dx}{x} e^{-x^2/2}$$
Let $[x<1]$ be $1$ for $x<1$ and $0$ for $x \geq 1$. Then the integral is
$$\int_{1/\sqrt{n}}^{1} \frac{dx}{x} + \int_{1/\sqrt{n}}^{\infty} \frac{e^{-x^2/2} - [x<1]}{x} dx.$$
The first integral is $(1/2) \log n$.  The second approaches $\int_{0}^{\infty} \frac{e^{-x^2/2} - [x<1]}{x} dx$, which is convergent.
So our final integral is $(1/2) \log n + O(1)$. I don't want to make too strong a claim about how much accuracy is lost in all the approximations, but one should be able to work it out.
