Asymptotics of sum of binomials How can you compute the asymptotics of 
$$S=n  + m - \sum_{k=1}^{n} k^{k-1} \binom{n}{k} \frac{(n-k)^{n+m-k}}{n^{n+m-1}}\;?$$
We have that $n \geq m$ and $n,m \geq 1$.
A simple application of Stirling's approximation gives
$$S \approx T =  n + m - \frac{n^{3/2-m}}{\sqrt{2\pi}} \sum_{k=1}^n \frac{(n-k)^{m-1/2}}{k^{3/2}}$$
A more accurate approximation is given by
$$n+m- \frac{\left(1+\frac{1}{12 n}\right) n }{\sqrt{2 \pi }} \sum _{k=1}^{n-1} \frac{ (1-\frac{k}{n})^{m-\frac{1}{2}}}{\left(1+\frac{1}{12 k}\right) k^{3/2} \left(1+\frac{1}{12 (n-k)}\right) }$$
Via an indirect and handy wavy argument, my guess is guess for constant $m$ is that the answer is
$$S \sim \sqrt{2n} \frac{\Gamma(m+\frac{1}{2})}{(m-1)!}$$
Update.  When $m$ grows almost as quickly as $n$ I think my guess is an underestimate.  For example when $n=m$ it seems numerically that $S \sim 1.841 n$ and in fact if $n=m$ then it is suggested that $S \sim n\left(2-\left( -W\left(-\frac{1}{\mathrm{e}^2}\right)\right)\right)$ (see Is $\sum_{k=1}^{n} k^{k-1} (n-k)^{2n-k} \binom{n}{k} \sim\frac{n^{2n}}{2\pi} $?). 
Update 2.  When $m=1$ then $S$ is precisely the average number of people required to find a pair with the same birthday.  This is solved at the wikipedia entry for the Birthday Problem and so $S \sim \sqrt{\frac{\pi n}{2}}$ (which equals  my guess above).  I would however ideally like to find the asymptotics in terms of $m$ and $n$ without assuming that $m$ is fixed.  
Update 3.  For the $m=1$ case we can prove that the correct asymptotics is $\sqrt{\frac{\pi n}{2}}$ in two ways.


*

*We will first show the result using the following identity. 


$$n  + 1 - \sum_{k=1}^{n} k^{k-1} \binom{n}{k} \frac{(n-k)^{n+1-k}}{n^{n+1-1}}=1 + \sum_{k=1}^n \frac{n!}{(n-k)!n^k} = 1+Q(n)$$
The numerator of the sum on the left is $n^{n+1}-Q(n)n^n$ (Q(n) is called Ramanujan's function by Knuth) according to A219706 and A063169.  This immediately gives the identity.
We also know that $Q(n) \sim \sqrt{\frac{\pi n}{2}}$ from the wikipedia (is there a better reference?).


*

*The second proof follows from the amazing answer of GEdgar where he shows that


$$\sum_{k=1}^n \binom{n}{k} k^{k-1}(n-k)^{n-k+1} =
 n^n\Bigg( n
 -\frac{\sqrt{2\pi}}{2} n^{1/2} + \frac{1}{3}
 -\frac{\sqrt{2\pi}}{24} n^{-1/2}
 +\frac{4}{135}n^{-1}
 -\frac{\sqrt{2\pi}}{576}n^{-3/2}
 +O\left(n^{-2}\right)\Bigg)
$$
 A: Computation for constant $m$ positive integer.
This uses the same method as in Estimate $\sum_{k=1}^{n} k^{k-1} \binom{n}{k} (n-k)^{n+1-k}$ ,
further explanation is there.
Write
\begin{equation*}
 u_{-1}(z) = \sum_{n=1}^\infty \frac{n^{n-1}}{n!} z^n
\tag{1}\end{equation*}
Then the unique singularity nearest to the origin is at $z=e^{-1}$,
and we have an expansion there:
\begin{equation*}
 u_{-1}(z) = 1 - \sqrt{2}(1-ez)^{1/2}+\frac{2}{3}(1-ez)
 +O\left((1-ez)^{3/2}\right)
\tag{2}\end{equation*}
as $z \to e^{-1}$ from the left.
Define recursively $u_m(z) = z u_{m-1}'(z)$ for $m = 0,1,2,\dots$.
Then we have
\begin{equation*}
 u_m(z) = \sum_{n=0}^\infty \frac{n^{n+m}}{n!}z^n
\tag{3}\end{equation*}
by induction.  To expand these at $e^{-1}$ we will also need
the expansion of $z$:
\begin{equation*}
 z = e^{-1} - e^{-1}(1-ez) = e^{-1} +O\left((1-ez)^1\right)
\tag{4}\end{equation*}
Now differentiate (2) and multiply by (4) to get
\begin{align*}
 u_0(z) = \frac{1}{\sqrt{2}}(1-ez)^{-1/2}-\frac{2}{3}
 +O\left((1-ez)^{1/2}\right)
\tag{5}\end{align*}
Differentiate this and multiply by (4) to get
\begin{align*}
 u_1(z) &= \frac{1}{2\sqrt{2}} (1-ez)^{-3/2}
 +O\left((1-ez)^{-1/2}\right)
 \\ &= 
 \frac{\Gamma(3/2)}{\sqrt{2\pi}} (1-ez)^{-3/2}
 +O\left((1-ez)^{-1/2}\right)
\end{align*}
Continuing, by induction we get
\begin{equation*}
 u_m(z) = \frac{\Gamma(m+1/2)}{\sqrt{2\pi}}(1-ez)^{-m-1/2}
 +O\left((1-ez)^{-m+1/2}\right)
\tag{6}\end{equation*}
for $m \ge 1$.
Now fix positive integer $m$.  (The extra term $-2/3$ in (5) 
mean that the formula for $m=0$ is different, but can also be done
by this method.)
Multiply (1) and (3) to get
\begin{equation*}
 h(z) := u_{-1}(z)u_m(z)
 = \sum_{n=1}^\infty\left(\frac{1}{n!}
 \sum_{k=1}^n \binom{n}{k}\frac{k^{k-1}}{k!}\,
 \frac{(n-k)^{n-k+m}}{(n-k)!}\right)z^n
 =:\sum_{n=1}^\infty c_n z^n
\end{equation*}
Multiply (2) and (6) to get
$$
 h(z) = \frac{\Gamma(m+1/2)}{\sqrt{2\pi}}(1-ez)^{-m-1/2}
 -\frac{\Gamma(m+1/2)}{\sqrt{\pi}}(1-ez)^{-m}
 +O\left((1-ez)^{-m+1/2}\right)
$$
as $z \to e^{-1}$ from the left.  So by the Szegö method, we get
an asymptotic series
\begin{align*}
 c_n &\approx e^n\left[
 \frac{\Gamma(m+1/2)}{\sqrt{2\pi}}\binom{n+m-1/2}{n}
 -\frac{\Gamma(m+1/2)}{\sqrt{\pi}}\binom{n+m-1}{n}+\dots
 \right]
 \\
 c_n &= e^n\Bigg[
 \frac{\Gamma(m+1/2)}{\sqrt{2\pi}}\left(
 \frac{1}{\Gamma(m+1/2)}n^{m-1/2}+O(n^{m-3/2})\right)
 \\ &\qquad\qquad
 -\frac{\Gamma(m+1/2)}{\sqrt{\pi}}\left(
 \frac{1}{(m-1)!}n^{m-1} +O\left(n^{m-2}\right)
 \right) +O\left(n^{m-3/2}\right)
 \Bigg]
 \\ &=
 e^n\left[\frac{1}{\sqrt{2\pi}}n^{m-1/2}
 -\frac{\Gamma(m+1/2)}{(m-1)!\sqrt{\pi}}n^{m-1}+O\left(n^{m-3/2}\right)\right]
\end{align*}
as $n \to \infty$.
Multiply by Stirling's formula,
$$
 n! = e^{-n}n^n\sqrt{2\pi}\left(
 n^{1/2}+O\left(n^{-1/2}\right)\right)
$$
to get
\begin{align*}
 &\sum_{k=1}^n\binom{n}{k} \frac{k^{k-1} 
 (n-k)^{n-k+m}}{n^{n+m-1}} = c_n\frac{n!}{n^{n+m-1}}
% \\ &\qquad
 = n - \frac{\sqrt{2}\,\Gamma(m+1/2)}{(m-1)!}\,n^{1/2} + O\left(1\right)
\end{align*}
so
\begin{align*}
 S &=
 n+m-\sum_{k=1}^n\binom{n}{k} \frac{k^{k-1} 
 (n-k)^{n-k+m}}{n^{n+m-1}}
 \\  &=
 n+O\left(1\right)
 -n + \frac{\sqrt{2}\,\Gamma(m+1/2)}{(m-1)!}\,n^{1/2} 
 + O\left(1\right)
 \\
 &=
 \frac{\sqrt{2}\,\Gamma(m+1/2)}{(m-1)!}\,n^{1/2} 
 + O\left(1\right)
\end{align*}
as $n \to \infty$, since $m$ is constant.
