How to show that $\sum\limits_{k=1}^{n-1}\frac{k!k^{n-k}}{n!}$ is asymptotically $\sqrt{\frac{\pi n}{2}}$?

According to "Concrete Mathematics" on page 434, elementary asymptotic methods show that $\displaystyle \sum_{k=1}^{n-1}\frac{k! \; k^{n-k}}{n!}$ is asymptotically $\sqrt{\frac{\pi n}{2}}$. Does anybody see how to show this?

The sum can asymptotically be replaced by an integral $$\sum_{k=1}^{n-1}\frac{k! \; k^{n-k}}{n!} \sim \int_1^n dk\, \frac{k! k^{n-k}}{n!}.$$ The integral can be approximated by its saddle point (which here coincides with a boundary). For that first use Stirling $$k! k^{n-k} \sim k^n e^{-k} = e^{-k +n \log k}.$$ The maximum of $-k+n \log k$ is attained at $k=n$ such that we can expand the integrand around this value and obtain $$\frac{k! \; k^{n-k}}{n!} \approx e^{-(k-n)^2/2n}$$ up to second order in the exponent. Thereby $$\sum_{k=1}^{n-1}\frac{k! \; k^{n-k}}{n!} \sim \int_1^n dk\, \frac{k! k^{n-k}}{n!} \sim \int_{-\infty}^n dk\, e^{- (k-n)^2/2n} = \sqrt{\frac{n \pi}{2}}. $$

Edit: as an answer to the comment of Didier Piau I try to be a bit more rigorous.

To estimate the integrand, we expand the exponent around the saddle point. This amounts to finding the maximum of $$\log \left[\frac{k! \; k^{n-k}}{n!} \right] \sim (n-k) \log k + k (\log k -1) - n (\log n -1).$$ Taking the derivative with respect to $k$ yields $(n-k)/k$ with the maximum at $n= k$. Expanding around this maximum to second order in $k-n$, we obtain $$\log \left[\frac{k! \; k^{n-k}}{n!} \right] \sim -\frac{(k-n)^2}{2n}.$$

What Didier Piau observed is a subdominant linear term ($i/2n$ in his comment). This leads to a shift in the position of the maximum but the curvature stays the same. In fact, the first nonvanishing term around the maximum is always second order as the linear term vanishes by definition. To make this more explicit, we have to include the next term in the Stirling expansion $$\log \left[\frac{k! \; k^{n-k}}{n!} \right] \sim (n-k) \log k + k (\log k -1) + \frac{1}{2} \log k - n (\log n -1) - \frac{1}{2} \log n.$$ The maximum is now obtained at $k^*= (2n -1)/2$ (exactly due to the shift noted by Didier Piau). Expanding to second order around this point yields $$\log \left[\frac{k! \; k^{n-k}}{n!} \right] \sim- \frac{(k - k^*)^2}{2n+1}.$$ The shifts of order 1 in the position of the maximum and in the curvature do not affect the result in leading order.

I don't think the accepted answer is sufficiently rigorous, so I dug up Knuth's derivation in The Art of Computer Programming, Vol. 1 (3rd ed.), Section 1.2.11.3, pp. 119-120. Here's a summary of his argument.

Use Stirling's approximation on $k!$ to get $$\sum_{k=0}^n \frac{k^{n-k} k!}{n!} = \frac{\sqrt{2\pi}}{n!}\sum_{k=0}^n k^{n+1/2} e^{-k}\left(1 + O(k^{-1})\right).$$

Then, use the Euler-Maclaurin formula to obtain

$$\sum_{k=0}^n k^{n+1/2}e^{-k} = \int_0^n x^{n+1/2} e^{-x} dx + \frac{1}{2} n^{n+1/2}e^{-n} + \frac{1}{24}n^{n-1/2}e^{-n} - R,$$ where $R$ is the remainder term and can be shown to be $O(n^n e^{-n})$.

Since the integral is an incomplete gamma function, we have $$\sum_{k=0}^n k^{n+1/2}e^{-k} = \gamma \left(n+\frac{3}{2},n\right) + O(n^{n+1/2}e^{-n}).$$

In a two-page analysis earlier in the section, Knuth shows that for large values of $x$ and fixed $y$, $$\frac{\gamma (x+1,x+y)}{\Gamma(x+1)} = \frac{1}{2} + O\left(\frac{y}{\sqrt{x}}\right).$$

Putting this all together yields $$\sum_{k=0}^n \frac{k^{n-k} k!}{n!} = \frac{\sqrt{2\pi}}{\Gamma(n+1)} \left[\Gamma\left(n+\frac{3}{2}\right)\left(\frac{1}{2} + O\left(\frac{1}{\sqrt{n}}\right)\right) + O\left(\Gamma\left(n+\frac{1}{2}\right)\right)\right].$$ Since, for fixed $a$ and $b$ (see, for instance, here), $$\frac{\Gamma(n+a)}{\Gamma(n+b)} = n^{a-b}\left(1 + O(n^{-1})\right),$$ we finally get $$\sum_{k=0}^n \frac{k^{n-k} k!}{n!} =\sqrt{ \frac{\pi n}{2}} + O(1).$$

Knuth says, "Our derivations... use only simple techniques of elementary calculus." So perhaps this is what is meant by "elementary asymptotic methods" in Concrete Mathematics, rather than "this derivation is easy." :)

Knuth also describes more advanced techniques whereby you can get the more precise estimate

$$\sum_{k=0}^n \frac{k^{n-k} k!}{n!} = \sqrt{ \frac{\pi n}{2}} - \frac{2}{3} + \frac{11}{24} \sqrt{\frac{\pi}{2n}} + \frac{4}{135n} - \frac{71}{1152} \sqrt{\frac{\pi}{2n^3}} + O(n^{-2}).$$