Every function is a tree with two marks

There are $n^{n-2}$ trees on $n$ labelled points. The formula is Cayley’s, from 1889, and the proof drawn earlier in this subject went through Prüfer’s code: strip leaves one at a time, write down each one’s neighbour, and every tree becomes a list of $n - 2$ labels while every list becomes a tree. It is a correct proof and a slightly mysterious one, because nothing in it explains why the exponent is $n - 2$ rather than something more natural.

There is a more natural count nearby. A function from the set $\{1, 2, \ldots, n\}$ to itself assigns to each point an image, chosen freely among the $n$ points, so there are exactly $n^n$ of them. Cayley’s number is that, divided by $n^2$. In 1981 André Joyal found the reason, and it is a picture: a function, drawn as an arrow from each point to its image, is a tree on the same points with two of them marked, read in a particular way. Two marks, each chosen among $n$ points, account for the $n^2$.

What a function looks like #

Draw any function on finitely many points as arrows, one leaving each point, and the picture always has the same anatomy. Start anywhere and follow the arrows; since there are finitely many points, the walk must eventually revisit one, and from then on it goes round a cycle. So every point leads into a cycle, every cycle is reached by trees of points that flow into it, and the picture is a collection of cycles with trees hanging off them. The same anatomy appeared in the middle-square method, where a seed wanders down a tree and falls into a loop; that rule was one particular function on ten thousand points, and this essay is about all of them at once.

In the hero figure the function sends $1$ to $7$, $2$ to $7$, $3$ to $5$, $4$ to $3$, $5$ to itself, $6$, $7$ and $8$ to $2$, and $9$ to $6$. The points on cycles are $2$, $5$ and $7$: $2$ and $7$ swap, and $5$ stays put. Every other point leads into one of them: $4$ to $3$ to $5$; $9$ to $6$ to $2$; $1$ to $7$; $8$ to $2$.

A tree, on the other hand, has no cycles at all. The task is to break the cycles of a function without losing information, and to record what was broken in two marks.

The reading that turns cycles into a path #

The function permutes its cyclic points. Each of $2$, $5$ and $7$ is sent to one of $2$, $5$ and $7$, and no two to the same one, since every cyclic point has exactly one cyclic predecessor. A permutation of a set can be written in two ways: as its cycles, which is how the arrows show it, or as a sequence — the list of images of the elements in a fixed order. Joyal’s whole idea is to switch from the first description to the second.

List the cyclic points in increasing order, $2 < 5 < 7$, and under each write its image: $7$, $5$, $2$. The bottom row is a sequence of the cyclic points, and a sequence of distinct points is a path. Join them in that order, $7 - 5 - 2$, mark the first as the head and the last as the tail, and hang every other point from its image exactly as before: $1$ from $7$, $3$ from $5$ and $4$ from $3$, $6$ and $8$ from $2$, and $9$ from $6$. The result, on the right of the hero figure, is a tree — connected, with eight edges on nine points and no cycles — carrying two marks.

Going back is just as mechanical. Given a tree with a head and a tail, there is exactly one path between them; list its points from head to tail, sort the same points, and pair them off: the $k$-th smallest point is sent to the $k$-th point of the path. Every point not on the path is sent to its neighbour one step closer to the path. That rebuilds the function, cycles and all.

Run it on the hero figure’s tree. The path from head to tail is $7, 5, 2$; sorted, its points are $2, 5, 7$; pairing the sorted list with the path sends $2$ to $7$, $5$ to $5$ and $7$ to $2$, which is the cycle $2 \to 7 \to 2$ and the fixed point $5$ again. The points off the path point one step towards it: $1$ to $7$, $3$ to $5$, $4$ to $3$, $6$ and $8$ to $2$, $9$ to $6$. Every arrow of the original function is back.

So functions and doubly marked trees correspond one to one. There are $n^n$ functions, and a doubly marked tree is a tree with an ordered choice of head and tail, which can be the same point, so $n^2$ choices per tree. Hence the number of trees is $n^n / n^2 = n^{n-2}$, with no code and no stripping of leaves.

When the head is the tail #

The count $n^2$ includes the choices in which the head and the tail are the same point, and those cases are where the reading is easiest to watch.

A function with exactly one cyclic point is one in which every walk ends at a single fixed point, a point sent to itself. Sorting one point and reading its image gives a path of length nought: the head and the tail coincide at the fixed point, and the tree is the hanging trees joined at it. The constant function, which sends every point to the same point $c$, becomes the star with $c$ at the centre, marked twice. At the other extreme a permutation, a function in which every point lies on a cycle, has no hanging trees at all, so its tree is a path through all $n$ points: the $n!$ permutations become the $n!$ ways to list the points along a path from head to tail. A path with its head and tail marked is exactly a sequence, so this is the familiar fact that the permutations of a set and its orderings are the same in number — rederived as the two extreme cases of one reading.

Between the extremes, the number of cyclic points can be anything from one to $n$, and the bijection says the functions with $k$ cyclic points correspond to the trees whose head-to-tail path has $k$ points. Both can be counted directly: choose and order the $k$ points of the path, $n(n-1)\cdots(n-k+1)$ ways, and then attach the remaining points as a forest rooted on the path, which can be done in $k\,n^{n-k-1}$ ways by a forest version of Cayley’s formula. Summing over $k$ gives $n^n$, a check on the bookkeeping that the census below performs by brute force.

A function is a set of cycles of trees #

Joyal found the reading while building a theory, and the theory is worth a paragraph because it says what kind of fact this is. His species are kinds of labelled structure — trees, functions, permutations, sets — treated as objects that can be combined. A permutation is a set of cycles; a rooted tree is a root together with a set of rooted trees; and a function, by the anatomy described above, is a set of cycles of rooted trees. In the language of species that sentence is an identity, and the labelled generating functions of the two sides are equal because the sentence is true, not because anybody computed them.

The bijection drawn here is the observation that “a set of cycles” and “a sequence” are interchangeable when the things being arranged come with labels, because a permutation is both. Replace the set of cycles of rooted trees with a sequence of rooted trees and the function becomes a path with trees hanging from it — a vertebrate, in Joyal’s word, with a head, a tail and a spine. The tree count then needs no generating function at all: vertebrates are trees with two marks, functions are $n^n$, and the two are the same.

Checked by running through every function #

A bijection is a claim about every case, and for small numbers of points every case can be tried.

The census sends all $6^6 = 46{,}656$ functions on six points through the reading and finds 46,656 different marked trees — $1{,}296$ trees, each with each of its $36$ choices of head and tail exactly once. Up to five points the inverse is run on every output as well, and gives back the function it came from in every case.

What the census confirms is that nothing is lost in either direction. The reading must not merge two functions, and the inverse must not merge two marked trees; the first fails if two functions have the same cyclic points permuted in the same way and differ elsewhere — they cannot, since elsewhere they are the hanging trees, which are kept — and the second fails if the sorting step could be confused, which it cannot because sorting is unambiguous. The census turns those two arguments into two counts that agree.

The surprising thing: a fact about trees from the birthday problem #

A bijection does more than count. It carries any statistic from one side to the other, and here one statistic carries something unexpected.

The number of cyclic points of a function corresponds, under the reading, to the number of points on the path from head to tail. So the question “on a random function, how many points lie on cycles?” is the same question as “in a random tree, with a random head and a random tail, how many points lie on the path between them?” Two questions about two different kinds of object are one question.

The figure counts both sides separately, by enumeration rather than through the bijection, and they agree in every column. And the first question has an answer that is already known from elsewhere. To find the cyclic points of a random function, start at a random point and follow the arrows until a point repeats; the walk’s length is exactly a birthday-problem wait, because each new image is a fresh random choice among the $n$ points until one of them has been seen. The expected number of cyclic points comes out to the sum

$$1 + \frac{n-1}{n} + \frac{(n-1)(n-2)}{n^2} + \cdots,$$

which Ramanujan studied in 1911 and which grows like $\sqrt{\pi n/2}$. So the average distance between two random points of a random labelled tree grows like $\sqrt{\pi n/2}$ as well — a fact about trees, first proved by Meir and Moon in 1970 by a different route, that the bijection derives from the birthday problem in one step.

The middle-square census meets this figure from the other side. A single seed of a random function wanders for about $\sqrt{\pi n/2}$ steps before it repeats, and the cycles of the whole function contain about that many points in all; the middle-square rule, which is one function on ten thousand points, had only eight cycles holding seventeen points between them — where a random function on ten thousand points would typically have about a hundred and twenty-five cyclic points. That shortfall, more than any single seed’s short life, is the clearest sign that the middle square is not a random map: its whole structure funnels into a handful of traps. Joyal’s reading turns that shortfall into a statement about a tree: the middle square, read as a marked tree, has a head-to-tail path of seventeen points where a random marked tree on ten thousand points would have one of about a hundred and twenty-five.

The growth is the reason random trees look the way they do. A random labelled tree on a thousand points has its typical pair of points about forty steps apart — far more than the logarithmic distances of a balanced tree, far less than the thousand steps of a path. Its height grows like the square root of its size, and the square root comes from the birthday problem through Joyal’s reading.

What the reading leaves out #

The bijection is between labelled objects, and the labels do real work. The step that sorts the cyclic points needs an order on the points, and the reading depends on which order is used: relabelling the points can change which tree a function becomes. That is not a defect. It is the reason the correspondence is between labelled functions and labelled trees, and it is why the symmetric object Cayley counted — trees on labelled points — is the one this argument reaches. Counting trees without labels, up to rearranging the points, is a different and harder problem, with no formula of this kind; the next question in this subject is what the labels hide, and how often a tree can be turned over onto itself.

The reading also says something about the matrix-tree theorem, which counts the trees of any graph by a determinant. For the complete graph that determinant gives $n^{n-2}$ again, by a third route. The three proofs — Prüfer’s code, the determinant and Joyal’s reading — find the same number by counting different things, and only Joyal’s makes the $n - 2$ look inevitable: two points out of $n$ are spent marking where a cycle was cut.

Checked to six points, proved for all #

The census reaches six points; the theorem covers all. Every function up to six points was checked, and the reading’s correctness for larger $n$ rests on the argument that it and its inverse undo each other — an argument that the figures illustrate on one function and verify on 50,000, without being able to display it for the next size up.

The distance figure’s agreement is exact at seven points and asymptotic beyond. At seven points both distributions were counted in full. At a thousand points the figure measures random functions and compares them with Ramanujan’s exact sum, so the dots agree with the line to within sampling error rather than exactly, and the claim that random trees have distances growing like $\sqrt{\pi n/2}$ is a theorem the picture is consistent with, not one it proves.

The tree drawings hang subtrees below a row. In the hero figure the cyclic points and the spine are drawn in a row with everything else below, which makes the correspondence easy to see and makes every tree look shallow. A random function on many points, drawn the same way, would have a few long cycles and trees of very uneven depth hanging from them, and no drawing on a page this size would hold one with a thousand points. The anatomy — cycles, then trees, then the reading — is the same at every size, and the pictures can show it only at the size where every point still fits on the page with its label.

Still open: other functions, other trees #

Joyal’s reading is one of a family of bijections between structures that count to the same number, and the family has gaps. Rooted forests on $n$ labelled points number $(n + 1)^{n-1}$, and so do parking sequences for $n$ cars; several readings connect the two, each carrying different statistics across. Bijective combinatorics consists in large part of such coincidences of counts, some with a reading that explains them and some still waiting for one.

The deeper open question is which statistics of functions, trees and parking sequences are carried into each other by some bijection, and which are not. Joyal’s reading carries cyclic points to path length; Prüfer’s code carries degrees to repetition counts; no single bijection is known that carries every natural statistic at once, and for some pairs of statistics it is not known whether one can exist.