Limiting Sum including Stirling numbers I would like to simplify the following summation including $S(m,n)$, Stirling numbers of the Second kind.
$\begin{gather*}\\
&&
\frac{1}{n^{n+1}}\sum_{k=1}^{n-1}\binom{n}{n-k}S\left( n,n-k\right)
\left( n-k\right) !k\left( 1-\left( \frac{n-2}{n-1}\right) ^{k}\right)
&&
\end{gather*}$
I conjecture (in fact, computations show) that this sum approaches to $\frac{1}{e}(1-e^{-\frac{1}{e}})$ as $n$ approaches to $\infty$  . However, I do not have a proof.
It would be great if this can be simplified for any $n$ (I am not sure whether this is possible) or at least show the limiting result.
 A: We get for the sum term
$$\sum_{k=1}^{n-1} {n\choose k} {n\brace n-k} (n-k)! 
\times k x^k
\\ = n \sum_{k=1}^n 
{n-1\choose k-1} {n\brace n-k} (n-k)! \times x^k
\\ = n x \sum_{k=0}^{n-1} 
{n-1\choose k} {n\brace n-1-k} (n-1-k)! \times x^k
\\ = n x \times n! [z^n] \sum_{k=0}^{n-1} 
{n-1\choose k} (\exp(z)-1)^{n-1-k} x^k
\\ = n x \times n! [z^n] (\exp(z)-1+x)^{n-1}.$$
We find with $x=1$
$$n \times n! \times [z^n] \exp((n-1)z)
= n \times (n-1)^n.$$
We obtain for $x=(n-2)/(n-1)$
$$n \times  \frac{n-2}{n-1} \times
 n! [z^n] (\exp(z)-1/(n-1))^{n-1}.$$
Now the coefficient extractor is
$$\frac{1}{2\pi i} 
\int_{|z|=1} \frac{\exp((n-1)z)}{z^{n+1}} 
(1-\exp(-z)/(n-1))^{n-1} \; dz.$$
With $n$ large this becomes
$$\frac{1}{2\pi i} 
\int_{|z|=1} \frac{\exp((n-1)z)}{z^{n+1}} 
\exp(-\exp(-z)) \; dz.$$
We now apply the Saddle point Algorithm for Cauchy Coefficient Integrals
from pages 548 and 553 of Analytic Combinatorics by Flajolet and
Sedgewick.  (Theorem VIII.3) Our function $f(z)$ is
$$f(z) = (n-1)z-(n+1)\log z -\exp(-z)$$
and
$$f'(z) = (n-1) - (n+1)\frac{1}{z} + \exp(-z)$$
as well as
$$f''(z) = (n+1)\frac{1}{z^2} - \exp(-z).$$
Now let $\zeta_n$ be the positive real root of the saddle point equation
$f'(\zeta_n) = 0$ so that
$$\zeta_n (n-1) - (n+1) + \zeta_n \exp(-\zeta_n) = 0$$
and
$$\zeta_n = \frac{n+1}{n-1+\exp(-\zeta_n)}.$$
This implies
$$\frac{n+1}{n} \lt \zeta_n \lt \frac{n+1}{n-1}$$
so that with $n$ large $\zeta_n \approx 1.$ We get
for the asymptotics from equation 19 on the cited page
$$\frac{\exp(f(\zeta_n))}{\sqrt{2\pi f''(\zeta_n)}}$$
Now $f''(\zeta_n) = (n+1)/\zeta_n^2+(n-1)-(n+1)/\zeta_n$
and this evaluates to
$$\frac{\exp(n-1)\exp(-\exp(-1))}{\sqrt{2\pi (n-1)}}$$
Collecting everything from the two pieces we find
for the first piece
$$\frac{1}{n^{n+1}} \times n\times (n-1)^n
= \left(1-\frac{1}{n}\right)^n \sim \exp(-1)$$
and for the second piece
$$\frac{1}{n^{n+1}} \times n \frac{n-2}{n-1} n! \times
\exp(-1) \frac{\exp(n)\exp(-\exp(-1))}{\sqrt{2\pi (n-1)}}
\\ = \left(1-\frac{1}{n-1}\right) 
\exp(-1) \exp(-\exp(-1))
\frac{n!}{n^n} \frac{\exp(n)}{\sqrt{2\pi (n-1)}}
\\ \sim \left(1-\frac{1}{n-1}\right) 
\exp(-1) \exp(-\exp(-1))
\frac{n!}{n^n} \frac{\exp(n)}{\sqrt{2\pi n}}.$$
We apply Stirling's formula to conclude and get
$$\left(1-\frac{1}{n-1}\right) 
\exp(-1) \exp(-\exp(-1))
\sim \exp(-1) \exp(-\exp(-1)).$$
We join the two pieces to obtain
$$\bbox[5px,border:2px solid #00A000]{
\frac{1}{e}\left(1-e^{-1/e}\right)}$$
as proposed.
A: A different approach, first do $k=n-k$ so make the summation go in the inverse way and distribute, we get
$$
\frac{1}{n^{n+1}}\sum_{k=1}^{n-1}\binom{n}{n-k}S\left( n,n-k\right)
\left( n-k\right) !k\left( 1-\left( \frac{n-2}{n-1}\right) ^{k}\right)=\frac{1}{n^{n+1}}\left ( \sum_{k=1}^{n-1}\binom{n}{k}S\left( n,k\right)
\left( k\right) !(n-k)\right )-\frac{1}{n^{n+1}}\left ( \sum_{k=1}^{n-1}\binom{n}{k}S\left( n,k\right)
\left( k\right) !(n-k) \left (1-\frac{1}{n-1}\right )^{n-k}\right ),
$$
Recall that $x^n=\sum _{k=1}^nS(n,k)x^{\underline{k}}=\sum _{k=1}^nS(n,k)\binom{x}{k}k!,$  so that the first part becomes
$$\frac{1}{n^{n+1}}(n^{n+1}-n(n^n-(n-1)^n)),$$
where the negative part comes from, for example, OEIS. the limit of this is $1/e.$
Now, for the second part, one has
$$\frac{1}{n^{n+1}}\left ( \sum_{k=1}^{n-1}\binom{n}{k}S\left( n,k\right)
\left( k\right) !(n-k) \left (1-\frac{1}{n-1}\right )^{n-k}\right )=\frac{1}{n^{n+1}}\left ( \sum_{k=1}^{n-1}\binom{n}{n-k}S\left( n,k\right)
\left( k\right) !(n-k) \sum _{l=0}^{\infty}\binom{n-k}{l}(-1/(n-1))^l\right ),$$
exchanging the two sums and using $\binom{a}{b}\binom{b}{c}=\binom{a}{c}\binom{a-c}{b-c},$ one gets
$$\frac{1}{n^{n+1}}\sum _{l=0}^{\infty}\binom{n}{l}(-1/(n-1))^l\sum _{k=1}^{n-1}\binom{n-l}{n-k-l}k!S(n,k)(n-k),$$
which looks a lot like the first problem. Except that now $x=n-l.$
So we can check that the inner sum is
$$n(n-l)^n-n((n-l)^n-(n-l-1)^n),$$
so if one pushes the limit inside (ALERT: I am used to combinatorics, probably one has to check something about that pushing the limit) one then can see using that $\binom{n}{l}\sim n^l/l!,$
that one gets $$-\sum _{l=0}^{\infty}\frac{(-1)^{l}}{l!}e^{-(l+1)}=\frac{-1}{e}e^{-e^{-1}}.$$
Which agrees with your computation.
