Joyal’s Proof of Cayley’s Tree Formula

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} labelled 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}.

cayley-pseudoforest

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}):

cayley-tree

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s