Sum with Stirling numbers

Question

Show that for each $n>1$

$$\sum\limits_{k=1}^{n-1} \frac{(n-1)!}{(k-1)!}S(n,n-k) = (n-1)^n $$

where $S(n,m)$ is the Stirling number of the second kind.

Answer 1

Consider this:

$$ m^n = \sum_{j=1}^m \binom{m}{j} \, j! \, S(n,j) $$

The left side is the number of ways of placing $n$ distinct balls in $m$ distinct cells. The right side is the same, each term corresponds to the number of configurations that have $j$ occupied (non-empty) cells.

Then, replacing $k=m-j+1$:

$$ m^n = \sum_{j=1}^m \frac{m!}{(m-j)!} \, S(n,j) = \sum_{k=1}^m \frac{m!}{(k-1)!} \, S(n,m-k+1)$$

Pick the special case $m=n-1$, and you get your identity.