## 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 $n$ elements, there are $n^{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 $V$, the probability that it’s nilpotent is $1/\#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_n$, on $n$ vertices equals $n^{n-2}$. It is so beautiful that I can say it in words.

Let’s prove instead $n^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, $f$, from $\{1,\ldots,n\}$ into $\{1,\ldots,n\}$. If you draw the directed graph of such a function joining vertex $i$ to vertex $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 $X$ be a finite set. A tree on $X$ is an undirected graph with vertex-set $X$, such that there’s a unique non-backtracking path between any two vertices. Here’s a typical tree on a 22-element set $X$: 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 $X$ is $n^{n - 2}$, where $n$ is the cardinality of $X$. Joyal’s proof goes like this.

An equivalent statement is that the number of bipointed trees is $n^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 $X$, with the first distinguished vertex towards the left in brown and the second towards the right in pink (both circled): Joyal used the fabulous word vertebrate to mean bipointed tree, for reasons we’ll see in a moment. Since $n^n$ is the number of functions from $X$ to itself, Cayley’s formula says:

the number of vertebrates on $X$ is equal to the number of endofunctions of $X$.

That’s what we’ll show.

First note that by definition of tree, for any vertebrate on $X$ there’s a unique non-backtracking path from the first distinguished vertex to the second, here marked in blue: 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): 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: So far everything has been canonical: no arbitrary choices. The set of vertebrates on $X$ 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 $S$ is equal to the number of permutations of $S$.

Of course, both are $(\# S)!$. There’s no canonical bijection between orders on and permutations of an abstract set $S$ — 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 $S \subseteq X$, a bijection between orders on $S$ and permutations of $S$. 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: 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: (There’s no choice involved in doing this.) Now what we’ve got is a directed graph with $X$ 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: X \to X$! We seem to have also chosen a distinguished set of vertices, the yellow ones. But actually, they’re determined by $f$: they’re exactly the periodic points. So we lose no information if we throw away the colouring: So what we have is precisely an endofunction of $X$.

We’ve now shown that the vertebrates (bipointed trees) on $X$ are in bijection with the endofunctions of $X$. Since there are $n^n$ such functions, where $n = \# X$, it follows that there are $n^n$ vertebrates on $X$, and therefore $n^{n - 2}$ unrooted trees on $X$. 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 $Ord$ 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_{\ast\ast} \cong Ord \circ Tree_{\ast},$

where $Tree_{\ast\ast}$ is the species of vertebrates (bipointed trees), $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

$End \cong Perm \circ Tree_{\ast},$

where $End$ is the species of endofunctions and $Perm$ 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 $Ord$ and $Perm$ are not isomorphic species; that is, as functors they are not naturally isomorphic. So we’re not going to conclude that $Tree_{\ast\ast}$ and $End$ are isomorphic species either. However, $Ord$ and $Perm$ are pointwise isomorphic, in the sense that $Ord(X)$ and $Perm(X)$ have the same number of elements for each finite set $X$ (namely, $(\# X)!$). It follows that $Tree_{\ast\ast}$ and $End$ 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

### 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,\dots,n\}$ is $n^{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)$ denotes the number of trees on $\{1,\dots,n\}$ then there are $n^2 T(n)$ vertebrates, since there are $n$ choices for the head and the same for the tail.

An endofunction is a function from the set $\{1,\dots,n\}$ to itself. Clearly there are $n^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 $k$ vertices, for some $k$; the rest of the vertebrate consists of rooted trees attached at the vertices of the backbone. It is determined by specifying the value of $k$, the set of $k$ vertices on the backbone, the order in which they come from head to tail, and the $k$ 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 $k$ 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 $k$ points in one case and a permutation of $k$ points in the other. But the numbers of orderings and permutations are equal (namely $k!$), and so the numbers of vertebrates and endofunctions are also equal.

We see, moreover, that the number of vertebrates with $k$ points in their backbone is equal to the number of endofunctions with $k$ 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 $S$ is equal to the number of permutations of $S$…. [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 $G$-torsor $X$, any element $x_0\in X$ determines a bijection $G\to X$ by $g\mapsto g\cdot x_0$.

In particular, although there is no one canonical bijection, there are $(\#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 $V$, the number of ordered bases is the same as the number of automorphisms. The reason why is that the automorphism group $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)$.

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^n - 1)(q^n - q) \cdots (q^n - q^{n - 1}),$

where $q$ is the number of elements in the base field and $n = \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

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

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

As it stands this is not a bijective proof of Cayley’s theorem, because we are helping ourselves to an arbitrary bijection between two sets of the same cardinality (in this case, a set of total orders and a set of permutations).

But I think we can construct a bijective proof if we throw in even more structure. We already threw in more structure by pointing each tree twice, and this changed the cardinality to $n^n$. Now I’m proposing to add a total order to the $n$ elements, which changes the cardinality to $n! n^n$. I think this is enough structure on a vertebrate to pick out a canonical endomorphism, and vice-versa.

Maybe this is completely obvious to people who think about bijective proofs, but it wasn’t to me so I thought I would make a note here.

My motivation for thinking about this has to do with discrete Morse theory on graphs, which has more to do with Kirchhoff’s matrix tree theorem, of which Cayley’s formula is a special case.

Posted by: Simon Burton on June 6, 2021 5:44 PM | Permalink | Reply to this

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

I guess there’s a question of terminology here. Is there a bijective proof that the number of total orders on a finite set is equal to the number of permutations of it? In one interpretation of “bijective proof” (yours, I think), the answer is no, because in order to obtain a bijection we have to choose an order to correspond to the identity permutation. In another interpretation, yes: there are lots of bijective proofs, one for each choice of order on the set.

I know you’re fully aware of this. I just say it because it seems to me that the term “bijective proof” is open to different interpretations.

Fortunately, Joyal’s theory of species clears up all the mathematical muddiness around this kind of question (e.g. the species of total orders and permutations are not isomorphic).

Posted by: Tom Leinster on June 7, 2021 7:38 PM | Permalink | Reply to this

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

I had emailed Simon with the same point Tom made, but we arranged to have a video-chat to go over this, where Simon brought out some additional good points. He said it would be all right if I talked about this here.

I don’t know that the notion of bijective proof has been formally established in the literature, but here is what Richard Stanley says (Enumerative Combinatorics I, page 11):

We now turn to the question of what is the best way to prove that a counting function has some given description. In accordance with the principle from other branches of mathematics that it is better to exhibit an explicit isomorphism between two objects than merely to prove they are isomorphic, we adopt the general principle that it is better to exhibit an explicit one-to-one correspondence (bijection) between two finite sets than merely to prove that they have the same number of elements. A proof that shows that a certain set $S$ has a certain number $m$ of elements by constructing an explicit bijection between $S$ and some other set that is known to have $m$ elements is called a combinatorial proof or bijective proof. The precise border between combinatorial and non-combinatorial proofs is rather hazy, and certain arguments that to an inexperienced enumerator will appear non-combinatorial will be recognized by a more experienced counter as combinatorial, primarily because he or she will be aware of certain standard techniques for converting apparently non-combinatorial arguments into combinatorial ones.

Stanley did not write “explicit natural bijection”, but clean bijective proofs often are natural in a categorical sense (and often there are additional desiderata, like making sure the constructions are “constructive”). So even if there’s some wiggle room for what counts as a bijective proof, it’s aesthetically nice to have natural bijections, possibly after “thickening” the structures involved.

For example, even though we don’t have a natural isomorphism between total/linear orders on a finite set $S$ and permutations on $S$, the set of linear orders $Lin(S)$ is a torsor of the group $Perm(S)$. This means we have a “choice-free” isomorphism

$(\alpha, \pi_2): Perm(S) \times Lin(S) \to Lin(S) \times Lin(S)$

where $\alpha$ is the action of $Perm(S)$ on $Lin(S)$ and $\pi_2$ is projection onto the second coordinate. In fact this isomorphism is natural in that we have a species isomorphism

$Perm \times Lin \to Lin \times Lin$

and thus we do get a bijective proof in Simon’s sense that $Perm$ and $Lin$ are equinumerous, but only after “thickening” in this way$^{(1)}$. (I see now that Mike Shulman made substantially the same point about 18 months ago. I apologize to Tom if I’ve forgotten his promised follow-up post.) Hence we obtain a species isomorphism

$(Perm \times Lin) \circ R \to (Lin \times Lin) \circ R$

where $R$ stands for the species of rooted trees.

(Joyal’s strategy also involved a “thickening”: we don’t count trees directly, but rather bipointed trees.)

Simon’s suggestion above, if I understand it correctly, would involves a species isomorphism

$Perm(S) \times Lin(S) \to BipointedTrees(S) \times Lin(S)$

which involves another kind of thickening, “smaller” than the one above based on torsors. It could be interesting comparing his approach with some of the other standard proofs of Cayley’s theorem – there’s one that talks about Prüfer sequences – and see whether there’s some hidden natural content there. But neither of us has looked into this yet.

(1): of course to “cancel” a $|Lin|$ factor on each side of the equation $|Perm| \times |Lin| = |Lin| \times |Lin|$, we have to know that $Lin(S)$ is nonempty. But that’s a given, since to say $S$ is finite means by definition there’s a bijection $\{1, \ldots, n\} \to S$ for some $n$, and the domain has the ready-made order.

Posted by: Todd Trimble on June 9, 2021 11:13 PM | Permalink | Reply to this

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

Nice. This helped me understand the idea of “thickening” and its connection with cancellation, one categorical level down. And the point that whenever you have a torsor (which is often!), you have a thickening.

Posted by: Tom Leinster on June 10, 2021 2:40 PM | Permalink | Reply to this

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

Here is a connection which deserves to be made here: the functional equation $w(z) = z e^{w(z)}$ characterizes the species of rooted trees: it says that a rooted tree structure on $X$ is given by choosing a root $x \in X$ (the $z$ factor), partitioning the remainder $X \setminus x$ (the exponential), and then choosing a rooted tree structure on each member of the partition.

This functional equation is basically the functional equation for the Lambert $W$ function: we have $w(z) = -W(-z)$ (and this variation of $W(z)$ is very often what actually comes up in applications – it’s not just some tortured change of variables.)

So we learn that the Taylor series for $w(z)$ is given by $\sum_{n \geq 1} \frac{n^{n-1}}{n!}z^n$. This is well-known, of course. But there you go – if you are ever led, in the course of some tortured analysis problem, to consider the Lambert W function, just know that you’re thinking about a super-fundamental combinatorial species.

Posted by: Tim Campion on October 23, 2021 6:21 PM | Permalink | Reply to this

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

Cool! I’m trying to lodge this in my brain, so that if I should happen to run into the Lambert $W$ function in a decade’s time, I’ll remember it comes from the species of rooted trees.

Posted by: Tom Leinster on October 23, 2021 6:56 PM | Permalink | Reply to this

Post a New Comment