How to show $\sum_{k=1}^n \binom{n-1}{k-1} n^{n-k} k! = n^n$

Question

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.

Answer 1

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}. $$

Answer 2

$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.

Answer 3

$\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}} $$

Answer 4

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} $$

Answer 5

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}