A rooted, labeled tree on $n$ vertices is a tree with vertex set $[n] := \{1,2,\ldots,n\}$ in which one vertex has been designated the root. A leaf of a rooted tree is a vertex $v$ for which either: $v$ is not the root and has degree $1$; or $v$ is the root and has degree $0$.
Using standard generating function techniques (i.e. Lagrange inversion) it is not hard to prove that the number $t_{n,m}$ of rooted, labeled trees on $n$ vertices with exactly $m$ leaves is $t_{n,m} = \frac{n!}{m!} S(n-1,n-m)$, where $S(n,k)$ is the Stirling number of the $2$nd kind.
Together with Cayley's formula, this gives a proof of the identity $n^{n-1} = \sum_{m=1}^{n} \frac{n!}{m!} S(n-1,n-m)$.
But actually there is a much simpler proof of that identity: $\frac{n!}{m!} S(n-1,n-m)$ clearly counts the number of functions $f\colon [n-1]\to [n]$ whose image has cardinality $n-m$.
This makes me wonder: is there a simple bijection between functions $[n-1]\to [n]$ and rooted, labeled trees on $n$ vertices for which $n$ minus the cardinality of the image becomes the number of leaves of the tree?
Unless I'm mistaken, the Prüfer code does not accomplish this.
