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.



Bijectively counting labeled trees by number of leaves
If you identify a function $f: [n-1] \to [n]$ with the Prüfer code $(f(1), f(2), \ldots, f(n-1))$ then it corresponds to an unrooted labelled tree on $n+1$ vertices in which the label $n+1$ is a leaf. Designate the neighbour of that leaf as the root and delete the leaf and you have the desired bijection.


