Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

December 7, 2019

A Visual Telling of Joyal’s Proof Of Cayley’s Formula

Posted by Tom Leinster

Cayley’s formula says how many trees there are on a given set of vertices. For a set with nn elements, there are n n2n^{n - 2} of them. In 1981, André Joyal published a wonderful new proof of this fact, which, although completely elementary and explicit, seems to have been one of the seeds for his theory of combinatorial species.

All I’m going to do in this post is explain Joyal’s proof, with lots of pictures. In a later post, I’ll explain the sense in which Cayley’s formula is the set-theoretic analogue of the linear-algebraic fact I wrote about last time: that for a random linear operator on a finite vector space VV, the probability that it’s nilpotent is 1/#V1/\#V. And I’ll also give a new (?) proof of that fact, imitating Joyal’s. But that’s for another day.

Joyal’s proof was published here:

André Joyal, Une théorie combinatoire des séries formelles. Advances in Mathematics 42 (1981), 1–82.

(I try not to link to Elsevier, as I’m permanently furious with them for draining universities of an obscene amount of our precious funds. But this is a free download. To balance my karma, let me remind you that many paywalled papers can be found on Sci-Hub for free. The most effective way to use Sci-Hub is to put the DOI of the paper you’re seeking into the search box; the text search function doesn’t seem to work very well.)

Doron Zeilberger stated Joyal’s argument concisely in one of his infamous opinions (number 108):

Going back to “beauty-bare”, nothing in set theory rivals the beauty of André Joyal’s lovely proof of Arthur Cayley’s theorem that the number of labeled trees, T nT_n, on nn vertices equals n n2n^{n-2}. It is so beautiful that I can say it in words.

Let’s prove instead n 2T n=n nn^2 T_n = n^n .

The left side counts doubly-rooted trees, which are labeled trees with a directed path (possibly of one vertex) of labeled vertices with some trees (possibly trivial one-vertex ones) hanging from them. On the other hand the right side counts the number of functions, ff, from {1,,n}\{1,\ldots,n\} into {1,,n}\{1,\ldots,n\}. If you draw the directed graph of such a function joining vertex ii to vertex f(i)f(i), you would get a collection of cycles with some trees (possibly trivial one-vertex ones) hanging from them. So the left-side counts “lines of numbers” with hanging trees, and the right side counts “collection of cycles” with hanging trees. But “lines of numbers” are permutations in one-line notation, and “collection of cycles” are permutations in cycle-notation. QED!

If that’s crystal clear to you, great! You can stop reading here. But I wanted to state the argument in a more leisurely way, with pictures.

Let XX be a finite set. A tree on XX is an undirected graph with vertex-set XX, such that there’s a unique non-backtracking path between any two vertices. Here’s a typical tree on a 22-element set XX:

Step one

Category theorists and algebraists often use “tree” to mean rooted tree: one vertex is distinguished as special and conventionally placed at the bottom. But in the sense I’ll use the word here, trees don’t come with a distinguished vertex.

Cayley’s formula says that the number of trees on XX is n n2n^{n - 2}, where nn is the cardinality of XX. Joyal’s proof goes like this.

An equivalent statement is that the number of bipointed trees is n nn^n, where “bipointed” means that the tree comes equipped with an ordered pair of distinguished vertices (which are allowed to be the same). Here’s a bipointed tree on our 22-element set XX, with the first distinguished vertex towards the left in brown and the second towards the right in pink (both circled):

Step two

Joyal used the fabulous word vertebrate to mean bipointed tree, for reasons we’ll see in a moment. Since n nn^n is the number of functions from XX to itself, Cayley’s formula says:

the number of vertebrates on XX is equal to the number of endofunctions of XX.

That’s what we’ll show.

First note that by definition of tree, for any vertebrate on XX there’s a unique non-backtracking path from the first distinguished vertex to the second, here marked in blue:

Step three

You can look at the tree as the skeleton of some fantastical creature, with the blue path as the backbone, and the vertices on it as vertebrae, with the first (brown) distinguished vertex at the head end and the second (pink) one at the tail end. Hanging off each vertebra is a rooted tree, the root being that vertebra. If you let your imagination roam free, you can picture each tree as a rather ornate limb. The most similar real-life creature I could come up with is the amazing leafy seadragon (whose existence I think I learned of from David Roberts):

Leafy seadragon

Anyway, the blue path from the first distinguished vertex to the second determines a total order on the set of vertebrae. Once you’ve got that order, you might as well erase the edges between them, as they’re determined by the order. So a vertebrate amounts to a diagram like this:

Step four

So far everything has been canonical: no arbitrary choices. The set of vertebrates on XX is in canonical one-to-one correspondence with diagrams of this type. But now we’re going to break that pattern, using an elementary observation:

the number of total orders on a finite set SS is equal to the number of permutations of SS.

Of course, both are (#S)!(\# S)!. There’s no canonical bijection between orders on and permutations of an abstract set SS — for if there were, which order would correspond to the identity permutation? But that’s OK: all we need here is that there’s some bijection.

So, let’s arbitrarily choose, for each SXS \subseteq X, a bijection between orders on SS and permutations of SS. This done, we can replace the ordering of our five-element subset with a permutation of it. Which particular permutation it is depends on that arbitrary choice of bijection, but let’s say for sake of argument that it’s this one:

Step five

Hanging off each vertebra (yellow vertex) is a rooted tree. It makes no difference if we adorn its edges with arrows directed towards the root:

Step six

(There’s no choice involved in doing this.) Now what we’ve got is a directed graph with XX as its vertex-set, and with the property that each vertex is the source (tail) of exactly one arrow. This is nothing but a function f:XXf: X \to X! We seem to have also chosen a distinguished set of vertices, the yellow ones. But actually, they’re determined by ff: they’re exactly the periodic points. So we lose no information if we throw away the colouring:

Step seven

So what we have is precisely an endofunction of XX.

We’ve now shown that the vertebrates (bipointed trees) on XX are in bijection with the endofunctions of XX. Since there are n nn^n such functions, where n=#Xn = \# X, it follows that there are n nn^n vertebrates on XX, and therefore n n2n^{n - 2} unrooted trees on XX. And that’s Joyal’s proof of Cayley’s theorem.

Of course, the argument I’ve given is pictorial and not entirely rigorous. I didn’t even define “tree” rigorously. Probably the best way to make it rigorous is via species, the concept that Joyal pioneered in that same paper.

I’m not going to give a full introduction to species here, but let me just say briefly how it works. A species is a functor from the category of finite sets and bijections to the category of sets. For example, there’s a species OrdOrd that assigns to each finite set the set of total orders on it. There are several ways of putting two species together to make a third, and in particular, species can be “composed”. We’ve essentially shown that

Tree **OrdTree *, Tree_{\ast\ast} \cong Ord \circ Tree_{\ast},

where Tree **Tree_{\ast\ast} is the species of vertebrates (bipointed trees), Tree *Tree_{\ast} is the species of rooted (pointed) trees, and \circ is composition. This isomorphism expresses the fact explained in the first few pictures above: that a vertebrate is the same thing as a collection of rooted trees, with a total order on them (1–5 in the example shown). On the other hand, we also have

EndPermTree *, End \cong Perm \circ Tree_{\ast},

where EndEnd is the species of endofunctions and PermPerm is the species of permutations. This isomorphism expresses the fact explained in the last few pictures above: that an endofunction is the same thing as a collection of rooted trees, with a permutation of them.

Now OrdOrd and PermPerm are not isomorphic species; that is, as functors they are not naturally isomorphic. So we’re not going to conclude that Tree **Tree_{\ast\ast} and EndEnd are isomorphic species either. However, OrdOrd and PermPerm are pointwise isomorphic, in the sense that Ord(X)Ord(X) and Perm(X)Perm(X) have the same number of elements for each finite set XX (namely, (#X)!(\# X)!). It follows that Tree **Tree_{\ast\ast} and EndEnd are pointwise isomorphic too. In other words: on any finite set, there are the same number of vertebrates and endofunctions. That’s Cayley’s theorem.

Posted at December 7, 2019 5:29 PM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3172

5 Comments & 0 Trackbacks

Re: A Visual Telling of Joyal’s Proof Of Cayley’s Formula

I’d recently been trying to understand Cayley’s formula for myself, for the obvious reasons: I was teaching a class on combinatorics, and I was trying to understand endofunctions and their connection to trees, thanks to Tom’s puzzle on random endofunctions.

I found Zeilberger’s version of Joyal’s proof tough to follow. The version on Peter Cameron’s blog was easier, for some reason. The argument is logically the same, but I guess the precise wording strongly affects how easily I follow a piece of mathematics. I could follow Cameron’s argument at precisely the rate I read it, with no head-scratching.

So, here is Peter Cameron’s version:

Cayley’s Theorem says that the number of trees (connected graphs without cycles) on the vertex set {1,,n}\{1,\dots,n\} is n n2n^{n-2}. There are very many different proofs of this theorem; each proof tells us something new. It is one of the strongest arguments I know for having many proofs of a theorem.

Joyal’s proof works like this. Define a vertebrate to be a tree with a pair of distinguished vertices called the head and the tail. (They may be the same vertex.) If T(n)T(n) denotes the number of trees on {1,,n}\{1,\dots,n\} then there are n 2T(n)n^2 T(n) vertebrates, since there are nn choices for the head and the same for the tail.

An endofunction is a function from the set {1,,n}\{1,\dots,n\} to itself. Clearly there are n nn^n endofunctions, so we are done if we can prove that there are equally many vertebrates and endofunctions.

Now a vertebrate, as its name suggests, has a backbone, the unique path from its head to its tail. This is a path consisting of kk vertices, for some kk; the rest of the vertebrate consists of rooted trees attached at the vertices of the backbone. It is determined by specifying the value of kk, the set of kk vertices on the backbone, the order in which they come from head to tail, and the kk rooted trees attached at these points.

An endofunction has a set of recurrent points, which are permuted by the function; any other point arrives at a recurrent point after a series of moves, and these moves have a tree structure. So to specify an endofunction, we give the number kk of recurrent points, the set of there points, the permutation of them induced by the function, and the rooted trees attached at the points.

Comparing these specifications we see that the only difference is that we choose an ordering of kk points in one case and a permutation of kk points in the other. But the numbers of orderings and permutations are equal (namely k!k!), and so the numbers of vertebrates and endofunctions are also equal.

We see, moreover, that the number of vertebrates with kk points in their backbone is equal to the number of endofunctions with kk recurrent points.

Posted by: John Baez on December 7, 2019 11:44 PM | Permalink | Reply to this

Re: A Visual Telling of Joyal’s Proof Of Cayley’s Formula

Beautiful, thanks!

the number of total orders on a finite set SS is equal to the number of permutations of SS…. [but] there’s no canonical bijection… for if there were, which order would correspond to the identity permutation?

A slightly fancier way to say this, of course, is that the set of total orders is a torsor over the group of permutations. That is, a permutation takes one total order to another one, and any two total orders are related by a unique permutation. Thus, as with any GG-torsor XX, any element x 0Xx_0\in X determines a bijection GXG\to X by ggx 0g\mapsto g\cdot x_0.

In particular, although there is no one canonical bijection, there are (#S)!(\#S)! “jointly canonical” bijections, each determined by fixing a particular total order to correspond to the identity permutation.

Posted by: Mike Shulman on December 8, 2019 4:46 AM | Permalink | Reply to this

Re: A Visual Telling of Joyal’s Proof Of Cayley’s Formula

I’m glad you brought that up, Mike, because I’m going to want to emphasize it in my next post. The reason is that there’s a very similar situation for finite vector spaces (by which I mean finite-dimensional vector spaces over finite fields).

For a finite vector space VV, the number of ordered bases is the same as the number of automorphisms. The reason why is that the automorphism group Aut(V)Aut(V) acts freely and transitively on the set of ordered bases, which is nonempty. In other words, the set of ordered bases is a torsor over Aut(V)Aut(V).

There’s no canonical isomorphism, because if there was, which ordered basis would correspond to the identity automorphism? But like your observation about the “jointly canonical” bijections in the set-theoretic situation, there’s a canonical way of associating a bijection with each ordered basis.

(For the conversation we’re currently having it’s beside the point, but in my previous post I wrote about the number of ordered bases, or equivalently the number of automorphisms. It’s

n! q=(q n1)(q nq)(q nq n1), n!_q = (q^n - 1)(q^n - q) \cdots (q^n - q^{n - 1}),

where qq is the number of elements in the base field and n=dimVn = \dim V.)

Posted by: Tom Leinster on December 8, 2019 1:24 PM | Permalink | Reply to this

Re: A Visual Telling of Joyal’s Proof Of Cayley’s Formula

Did you mean to speak of the probability of a uniformly randomly chosen operator being idempotent, or (as in your other post) being nilpotent, or are they the same?

Posted by: L Spice on December 8, 2019 11:02 PM | Permalink | Reply to this

Re: A Visual Telling of Joyal’s Proof Of Cayley’s Formula

Nilpotent — now corrected. Thanks for catching that.

Posted by: Tom Leinster on December 9, 2019 12:12 AM | Permalink | Reply to this

Post a New Comment