# Bijectively counting labeled trees by number of leaves

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.

• If you attach a vertex $n+1$ to the root then isn't the Prüfer code of the resulting tree a sequence of $n-1$ integers from $[n]$, none of which is one of the leaves, and which includes all of the non-leaves? Mar 30 at 21:59
• @PeterTaylor: Oh dear, I think you're right, I don't know how I missed that! If you post that as an answer I'll happily accept it. Mar 30 at 22:01

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.