Almost every tree can be turned over

On four labelled points there are sixteen trees, and on $n$ there are $n^{n-2}$ — a count that has been reached by codes, by a determinant and by reading functions as trees, and that every one of those proofs reaches only because the points carry labels. Strip the labels off and ask how many shapes there are — how many trees that cannot be turned into one another by renaming the points — and the answer on four points is two: the path and the star. Twelve of the sixteen labelled trees are paths and four are stars. The shapes do not share the labelled trees equally, and the reason they do not is the subject of this essay.

A shape’s labellings are the ways to write the labels $1, \ldots, n$ on its points, which is $n!$ ways, except that two labellings give the same labelled tree when a symmetry of the shape carries one to the other. The star on four points has its three leaves interchangeable in $3! = 6$ ways, so its $24$ labellings make only $4$ distinct labelled trees. The path on four points can only be reversed end for end, so its $24$ labellings make $12$. A shape with $s$ symmetries has exactly $n!/s$ distinct labellings — the orbit-counting rule from the theory of group actions — and the labelled count is the sum of that over all shapes:

$$n^{n-2} = \sum_{\text{shapes } T} \frac{n!}{|\mathrm{Aut}\, T|}.$$

Counting the same trees twice #

The gallery is Cayley’s formula on seven points, counted the other way round. Each of the eleven shapes is drawn from its centre, and under it are its symmetries and its labellings. The star, with its six leaves permutable in every order, has $6! = 720$ symmetries and so only seven labellings — one for each choice of label at the centre. A path can be reversed and nothing else, so its 5,040 labellings fall in pairs, giving 2,520. At the other end sits a single shape, a centre with three branches of lengths one, two and three, that has no symmetry at all: no two of its branches are alike and no point can be swapped with any other. Every one of its 5,040 labellings is a different labelled tree, which is also why such trees are the natural test cases for labelling puzzles where the labels must satisfy a condition: there is no symmetry to collapse the search.

Added up, the eleven columns of labellings come to $16{,}807$, which is $7^5$. That is not a coincidence the picture discovered; it is the identity above, which must hold because every labelled tree is a shape with a labelling. But the figure computes each symmetry count independently — from the shape alone, with no reference to Cayley — so the agreement is a genuine check, one that would fail if a single symmetry were miscounted.

The counting of symmetries is itself mechanical once the shape is drawn from its centre. At each point, the branches hanging below it can be permuted among themselves whenever they are identical, and only then; so the number of symmetries is a product, over all points, of the factorials of the numbers of identical branches, times the symmetries of the branches themselves. A tree whose centre is an edge rather than a point gains one more factor of two when its two halves are identical. That rule is how the gallery’s numbers were computed, and it is also the rule behind the classical fast algorithm that decides whether two trees have the same shape, which writes each tree as a nested string of brackets and sorts the brackets at every level.

Why a symmetric shape has fewer labellings #

The rule $n!/s$ is worth seeing as a picture rather than a formula, because it is the whole mechanism of this essay. Take the path on four points and lay out all $24$ ways to write $1, 2, 3, 4$ along it. Reversing the path end for end turns each labelling into another — $1{-}2{-}3{-}4$ into $4{-}3{-}2{-}1$ — and the two describe the same labelled tree, the same set of three edges. So the $24$ labellings fall into pairs, one pair per labelled tree, and there are $12$ labelled paths. For the star, each labelled tree is reached by $6$ labellings, which differ only in how the three leaf labels are arranged, so the $24$ fall into groups of six and there are $4$ labelled stars.

In general the symmetries of a shape form a group, and the labellings fall into blocks of exactly the group’s size, one block per labelled tree — the same slicing of a group into equal blocks that proves Lagrange’s theorem. The count is exact because a labelling is never fixed by a non-trivial symmetry: a symmetry that moves any point changes which label sits where. The labelled trees are the orbits, and a shape’s share of them is inversely proportional to how symmetric it is.

Where the question came from: counting molecules #

Cayley’s own reason for counting trees was chemical. In the 1870s chemists had learned that the saturated hydrocarbons, the alkanes, have carbon skeletons that are trees: four bonds per carbon, no rings, and every molecule $\mathrm{C}_n\mathrm{H}_{2n+2}$ determined by how its carbons are joined. Two molecules with the same formula and different skeletons — isomers — have different properties, and the question of how many isomers a formula admits is exactly the question of how many tree shapes there are with every point of degree at most four.

That is the unlabelled count, the hard one. A chemist does not label the carbons: two skeletons that differ only by renaming are the same molecule. Cayley’s 1875 paper attacked it with generating functions and made errors at larger sizes that took decades to straighten out; George Pólya’s counting theorem of 1937, which counts objects up to symmetry by averaging over the symmetries, settled the method, and it was built on exactly the orbit-counting rule above. Butane, $\mathrm{C}_4\mathrm{H}_{10}$, has two isomers — the path and the star on four carbons, the first two shapes of this essay. Decane, with ten carbons, has seventy-five.

The labelled count, $n^{n-2}$, answers a question no chemist asked: how many skeletons there are if every carbon is individually tagged. The difference between the two counts is the difference between asking about molecules and asking about tagged atoms, and it is entirely made of symmetry.

Pólya’s method runs the orbit count in reverse. Instead of dividing each shape’s labellings by its symmetries, it averages, over all $n!$ renamings of the points, the number of labelled objects each renaming leaves unchanged; the average is the number of shapes. It is the rule that counts necklaces up to rotation, applied to a larger group, and for trees it turns into a functional equation for the generating function of shapes — the equation Otter later used to find their growth rate. The labelled count needs none of this, because a labelled object has no symmetry to average over; the unlabelled count needs all of it.

One to twelve points #

The same bookkeeping runs to twelve points, where there are 551 shapes.

Two things stand out. First, the asymmetric shapes are rare and late. On two to six points every tree has a symmetry — with so few points, some pair of leaves or some pair of branches is always interchangeable — and the first asymmetric tree has seven points. Even at twelve, only 29 of the 551 shapes, about one in nineteen, lack a symmetry.

Second, those few shapes carry far more than their share of the labelled trees: 22.4% of all labelled trees on twelve points have an asymmetric shape, because each asymmetric shape contributes the full $12!$ labellings while a symmetric one contributes a fraction. This is the weighting that the essay on random trees described: choosing a labelled tree at random is not choosing a shape at random, and it favours irregular, asymmetric shapes. A natural guess from the table is that as $n$ grows the labelled trees will come to be dominated by asymmetric shapes, since the weighting favours them more and more.

The guess is wrong.

The smallest trees with nothing to swap #

It is worth looking at the asymmetric trees before seeing why they lose.

An asymmetric tree must avoid every possible repetition. No point can carry two leaves, since the two leaves could be swapped. No point can carry two identical branches of any size. And if the tree has a central edge, its two halves must differ. On seven points the only way to manage it is the “spider” with legs of one, two and three. Each additional point opens a few more ways, and the counts grow — 1, 1, 3, 6, 15, 29 from seven to twelve points — but slowly, and every one of them is a tree that has carefully avoided putting two leaves side by side.

Two leaves side by side is called a cherry, and it is the single most common source of symmetry in a tree: swapping the two leaves of a cherry changes nothing about the shape.

Why the guess fails: cherries everywhere #

The probability that a large random tree has no cherry at all goes to nought, and the figure shows how fast.

At small sizes the curves are irregular — at seven points the single asymmetric shape pulls the symmetric share down to 70% — but from twenty points on both rise steadily. At fifty points 97% of random trees have a cherry; at a hundred, nearly all; at two hundred, all 2,000 trees sampled. It is a classical fact, and the starting point of a paper by Allen Schwenk in 1973, that the share with a cherry tends to one: in a large random tree there are about $n/e$ leaves scattered among the points, and the chance that no two of them land on the same point falls off exponentially.

So almost every tree has a symmetry, whether the trees are counted as shapes or weighted by their labellings. The weighting towards asymmetric shapes is real at every size, and it loses to the sheer number of places a cherry can form. The table’s 22.4% at twelve points is close to the top of the asymmetric share’s career: from there it declines towards nothing.

The tree in the last figure is typical. It was drawn from a random Prüfer code, and nothing about it was arranged; it has five cherries, one of them carrying three leaves, and between them they account for 96 of its 192 symmetries. The rest come from larger repeated branches. A random tree is not a special object, and it is almost certainly a symmetric one.

The surprising thing: trees are the opposite of graphs #

The comparison that makes this worth knowing is with graphs in general. In 1963 Paul Erdős and Alfréd Rényi proved that almost every graph is asymmetric — and the infinite random graph sits at the opposite extreme, with symmetries everywhere: among all graphs on $n$ labelled points, the share with any symmetry at all — any renaming of points that keeps the edges — tends to nought. A graph has about $n^2/2$ possible edges, each present or absent independently in a random graph, and a symmetry has to preserve all of them at once, which is overwhelmingly unlikely.

Trees go the other way, and the reason is their sparseness. A tree has only $n - 1$ edges, a third or more of its points are leaves, and a leaf is about as featureless as a point can be: two leaves on the same point are indistinguishable. A dense random graph gives every point a distinctive neighbourhood; a random tree gives a third of its points the same one. So the two most natural random objects in graph theory sit at opposite ends — the dense one almost never symmetric, the sparse one almost always — and the crossover between them, as edges are added, is a question about how many leaves are left.

The consequence that made Schwenk’s paper famous concerns eigenvalues. A graph’s adjacency matrix has a spectrum, and two graphs can share it without having the same shape. Schwenk showed that almost every tree shares its spectrum with a different tree: the same argument that finds a cherry finds, in almost every large tree, a branch that can be replaced by a different branch with the same effect on the eigenvalues. So the spectrum, which for most graphs is believed to determine the shape, almost never determines the shape of a tree. Trees are the family on which hearing the shape of a graph fails.

Labelled trees are counted, shapes are not #

The exact counts stop at twelve points. Every tree on up to twelve points was generated and its symmetries counted, and Cayley’s identity checked in every row. Beyond that the figure samples random labelled trees, which says how often a labelled tree has a symmetry. How often a tree shape chosen uniformly from all shapes has one is a different question; the answer is again almost always, but no figure here samples shapes, because a random shape cannot be drawn as easily as a random Prüfer code.

The share curve’s small-size wobbles are real. The dip at seven points is the single asymmetric spider carrying 30% of the labelled trees on its own, and similar effects at eight and nine points are visible. They are not sampling error — those points are exact — and they illustrate how misleading the first dozen sizes would be as a guide to the limit.

A symmetry count is a property of a shape, and every drawing here is one drawing of it. The layouts place each tree from its centre with branches spread by size, which makes most symmetries visible as mirror images. Some symmetries swap branches that are drawn far apart, and those cannot be seen in any single drawing; the counts were computed from the tree’s structure, not read off the picture.

Still open: how many shapes, and how hard to compare #

The number of tree shapes on $n$ points has no closed formula. Richard Otter showed in 1948 that it grows like $C \cdot 2.9557\ldots^n \cdot n^{-5/2}$, with constants that are computed numerically from a functional equation and are not known to have any simpler description. The labelled count is $n^{n-2}$ because labels break every symmetry; the unlabelled count is hard for exactly the reason this essay has drawn, that almost every tree has symmetries to quotient by.

Deciding whether two trees have the same shape is easy — the bracket encoding does it in time proportional to their size, as Aho, Hopcroft and Ullman showed in 1974 — and that ease is special to trees. For graphs in general, whether two given graphs are the same up to renaming is one of the few natural problems not known to be either efficiently solvable or among the hardest search problems; László Babai’s algorithm of 2015 runs in quasi-polynomial time, and whether polynomial time is possible is open. The symmetry that makes trees hard to count is the same tree structure that makes them easy to compare, and the general problem, without that structure, remains unsettled.

A narrower question sits inside this essay’s figures. The share of large random trees with a cherry tends to one exponentially fast, but the share of trees whose symmetry group is only the swaps of cherries — no larger repeated branches — has its own limit, and the distribution of the size of a random tree’s symmetry group, which in the sixty-point example was 192, has been described in the limit by its logarithm being roughly normal. How the largest symmetric pieces of a random tree are arranged is a finer question still, and the finer it gets, the less is settled.