Proving Riordan's identity that $\sum_{k=1}^{n} {n-1 \choose k-1} \frac{k!}{n^k}=1$

We shall count the number of length $n+1$ sequences $(x_1,\ldots,x_{n+1})$ over a set of $n$ elements in two different ways.

The first is to just independently choose each $x_i$, yielding $n^{n+1}$ sequences.

Alternatively, let $x_{k+1}$ be the first repeated element in the sequence (a repetition must occur because the length of the sequence is greater than $n$). The first $k$ elements of the sequence can be chosen in $k!\binom{n}{k}$ ways (they must all be distinct), and $x_{k+1}$ can be chosen in exactly $k$ ways (choosing which of the first $k$ elements is repeated). The elements at the remaining $n-k$ positions can then be chosen in $n^{n-k}$ ways (there is no restriction on them). Multiplying these together and summing over $k$, we get

$$n^{n+1}=\sum_{k=0}^nk!\binom{n}{k}\cdot k\cdot n^{n-k}$$ $$1 = \sum_{k=0}^n \frac{k}{n}\binom{n}{k}\cdot\frac{k!}{n^k}$$ $$1=\sum_{k=1}^n\binom{n-1}{k-1}\frac{k!}{n^k}$$ which is exactly what we want.