How to show $\sum_{k=1}^n \binom{n-1}{k-1} n^{n-k} k! = n^n$ To me it appears that lhs is some fancy way to count all functions from $[n]$ to $[n]$. I tried several approaches, including interpreting $\binom{n-1}{k-1}$ as number of solutions for $n=x_1+\dots +x_k$ where $\forall_i x_i \ge 1$. But it didn't lend me to anything significant.
I'd appreciate some hints or solutions to this.
 A: Using the recurrence for Pascal's Triangle and a telescoping sum,
$$
\begin{align}
\sum_{k=1}^n\binom{n-1}{k-1}\frac{k!}{n^k}
&=\sum_{k=1}^n\left[\binom{n}{k}-\binom{n-1}{k}\right]\frac{k!}{n^k}\\
&=\sum_{k=1}^n\binom{n-1}{k-1}\frac{(k-1)!}{n^{k-1}}-\sum_{k=1}^n\binom{n-1}{k}\frac{k!}{n^k}\\
&=\sum_{k=0}^{n-1}\binom{n-1}{k}\frac{k!}{n^k}-\sum_{k=1}^n\binom{n-1}{k}\frac{k!}{n^k}\\[6pt]
&=1-0\tag{1}
\end{align}
$$
Multiply $(1)$ by $n^n$ and we get
$$
\sum_{k=1}^n\binom{n-1}{k-1}n^{n-k}k!=n^n\tag{2}
$$
A: That is a consequence of the Abel-Hurwitz formula.
The LHS can be seen as $(n-1)!$ times the coefficient of $x^n$ in the product between
$$ \sum_{k\geq 0} k x^k=\frac{x}{(1-x)^2},\qquad \sum_{k\geq 0}\frac{n^k x^k}{k!}=e^{nx}. $$
A: $n^n$ is the number of lists of length $n$ whose entries are taken from $1,2\dots n$.
Let $S_k$ be the set of such lists whose first $k$ elements are pairwise distinct, but whose first $k+1$ elements are not (with the convention that $S_n$ is just the set of lists with no repeats). The sets $S_k$ for $k=1,\dots,n$ are a partition of the set of all $n^n$ lists. Thus, proving that $|S_k|=\binom{n-1}{k-1}k!n^{n-k}$ proves your formula.
A: $\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\ol}[1]{\overline{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
\begin{align}
\color{#f00}{\sum_{k = 1}^{n}{n - 1 \choose k - 1}n^{n - k}\,\, k!} & =
n^{n}\sum_{k = 0}^{n - 1}{n - 1 \choose k}{\pars{k + 1}! \over n^{k + 1}}
\\[5mm] & =
n^{n}\sum_{k = 0}^{n - 1}{n - 1 \choose k}\pars{k + 1}!\ \overbrace{%
{1 \over \Gamma\pars{k + 1}}\int_{0}^{\infty}t^{k}\expo{-nt}\,\dd t}
^{\ds{\,\,\,\,\,\,=\ {1 \over n^{k + 1}}}}
\\[5mm] & =
n^{n}\int_{0}^{\infty}\expo{-nt}
\sum_{k = 0}^{n - 1}{n - 1 \choose k}\pars{k + 1}t^{k}\,\dd t
\\[5mm] & =
n^{n}\int_{0}^{\infty}\expo{-nt}\pars{1 + t}^{n - 2}\pars{1 + nt}\,\dd t
\\[5mm] & =
n^{n}\color{#f00}{\expo{n}}\bracks{%
n\int_{1}^{\infty}{\expo{-nt} \over t^{1 - n}}\,\dd t
-\pars{n - 1}\int_{1}^{\infty}{\expo{-nt} \over t^{2 - n}}\,\dd t}
\label{1}\tag{1}
\end{align}
Integrating by parts the RHS first integral:
\begin{align}
n\int_{1}^{\infty}{\expo{-nt} \over t^{1 - n}}\,\dd t & =
-\int_{t\ =\ 1}^{t\ \to\ \infty}{\dd\expo{-nt} \over t^{1 - n}} =
\expo{-n} +
\pars{n - 1}\int_{1}^{\infty}{\expo{-nt} \over t^{2 - n}}\,\dd t
\\ & \mbox{}
\end{align}
\begin{equation}
\mbox{such that}\quad
n\int_{1}^{\infty}{\expo{-nt} \over t^{1 - n}}\,\dd t
-\pars{n - 1}\int_{1}^{\infty}{\expo{-nt} \over t^{2 - n}}\,\dd t =
\color{#f00}{\expo{-n}}
\label{2}\tag{2}
\end{equation}

With \eqref{1} and \eqref{2}:
$$
\color{#f00}{\sum_{k = 1}^{n}{n - 1 \choose k - 1}n^{n - k}\,\, k!} =
\color{#f00}{n^{n}}
$$
A: It is similar to the answer given by robjohn but with more careful in treating the running indices:
\begin{align}
& \sum_{k=1}^n \binom{n-1}{k-1}n^{n-k}k! \\ 
&= \sum_{k=1}^{n-1} \binom{n-1}{k-1}n^{n-k}k! + n! \\
&= \sum_{k=1}^{n-1} \left\{\binom{n}{k} - \binom{n-1}{k} \right\}n^{n-k}k! + n! \\
&= \sum_{k=1}^{n-1} \binom{n-1}{k-1}n^{n-(k-1)}(k-1)! - \sum_{k=1}^{n-1} \binom{n-1}{k}n^{n-k}k! + n! \\
&= \sum_{k=0}^{n-2} \binom{n-1}{k}n^{n-k}k! - \sum_{k=1}^{n-1} \binom{n-1}{k}n^{n-k}k! + n! \\
&= \left\{n^n + \sum_{k=1}^{n-2} \binom{n-1}{k}n^{n-k}k!\right\} - \left\{\sum_{k=1}^{n-2} \binom{n-1}{k}n^{n-k}k! + n!\right\} + n! \\
&= n^n
\end{align}
