I wanted to quickly write this proof up, complete with pictures, so that I won’t forget it again. In this post I’ll give a combinatorial proof (due to Joyal) of the following:

Theorem 1 (Cayley’s Formula)

The number of trees on $n$ labeled vertices is $n^{n-2}$.

Proof: We are going to construct a bijection between

• Functions $\{1, 2, \dots, n\} \rightarrow \{1, 2, \dots, n\}$ (of which there are $n^n$) and
• Trees on $\{1, 2, \dots, n\}$ with two distinguished nodes $A$ and $B$ (possibly $A=B$).

This will imply the answer.

Let’s look at the first piece of data. We can visualize it as $n$ points floating around, each with an arrow going out of it pointing to another point, but possibly with many other arrows coming into it. Such a structure is apparently called a directed pseudoforest. Here is an example when $n = 9$.

You’ll notice that in each component, some of the points lie in a cycle and others do not. I’ve colored the former type of points blue, and the corresponding arrows magenta.

Thus, a directed pseudoforest can also be specified by

• a choice of some vertices to be in cycles (blue vertices),
• a permutation on the blue vertices (magenta arrows), and
• attachments of trees to the blue vertices (grey vertices and arrows).

Now suppose we take the same information, but replace the permutation on the blue vertices with a total ordering instead (of course there are an equal number of these). Then we can string the blue vertices together as shown below, where the green arrows denote the selected total ordering (in this case $1 < 9 < 2 < 4 < 8 < 5$):

This is exactly the data of a tree on the $n$ vertices with two distinguished vertices, the first and last in the chain of green (which could possibly coincide). $\Box$