After canceling $1$'s and clearing denominators, the identity can be rearranged to this one:

$$n^{n+1} = \sum_{k=1}^{n} \binom{n}{k} k^{k-1} (n-k)^{n-k+1} + \sum_{k=1}^n \binom{n}{k} n^{n-k} k!$$

and now we proceed to give a bijective proof. The left side counts data of the form

- Endofunction $f: S \to S$ on an $n$-element set $S$, plus a distinguished point $s$ of $S$.

Draw the endofunction as a directed graph, where an edge is drawn from $x$ to $y$ if $f(x) = y$. This graph can be decomposed into connected components, and there are two disjoint possibilities:

Case 1: either $s$ belongs to a cycle (this includes the case where $f(s) = s$), or

Case 2: removal of the edge from $s$ to $f(s)$ produces a disconnection of the connected component of $s$.

Let us count the possibilities for the first case. The cycle to which $s$ belongs defines a $k$-element set, say, and gives a structure of linear order on this set, namely the ordering $s, f(s), \ldots, f^{k-1}(s)$. There are $k!$ ways of giving such a linear order, and this order describes the restriction of $f$ to the cycle containing $s$. The remainder of $f$ is just given by some function $S \backslash \mathrm{cycle}(s) \to S$ on the complement, of which there are $n^{n-k}$ many. Thus the second sum of the asserted identity counts the possibilities for case 1.

For case 2, consider the set of elements $x$ such that $f^{(j)}(x) = s$ for some $j \geq 0$. This defines some $k$-element subset, and the graph of the restriction of $f$ to this subset is described as a rooted tree with root at $s$. The number of such rooted tree structures on a $k$-element set is $k^{k-1}$, by Cayley's theorem. Then, the rest of $f$ is given by its restriction to the complement of this $k$-element set (notice it takes the complement to itself) -- there are $(n-k)^{n-k}$ possibilities here -- *plus* knowledge of the element $f(s)$ which belongs to this $(n-k)$-element set. Thus the first sum on the right side of the identity counts the number of possibilities for case 2, and we are done.