5
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ 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? $\endgroup$ Mar 30 at 21:59
  • $\begingroup$ @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. $\endgroup$ Mar 30 at 22:01

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.