How many shapes a tree can take

Sixteen trees on four points counted labelled trees: $n^{n-2}$ of them on $n$ points, by Cayley’s formula, with a bijection to Prüfer codes that makes the count obvious. Almost every tree can be turned over then took the labels off and found the problem transformed. A shape with symmetries absorbs labellings — the star on seven points can be labelled only seven ways, an asymmetric shape 5,040 — so the number of shapes is not $n^{n-2}/n!$, and almost every tree turned out to have a symmetry. That essay counted shapes by brute force to twelve points and ended by asking how many there are in general.

The answer has no formula. It does have a recurrence, found in pieces by Arthur Cayley in 1875 and George Pólya in 1937, and a theorem of Richard Otter’s from 1948 that finishes it, and together they compute the number of tree shapes on two hundred points — a number of 89 digits — in a fraction of a second.

Finding the shapes by force #

For small sizes the shapes can simply be found. Every labelled tree on $n$ points corresponds to one of the $n^{n-2}$ Prüfer codes, so turning every code into a tree and reducing each tree to a canonical form — root it at its centre, write each branch as a bracketed string of its sub-branches sorted into order, and compare strings — lists every shape. On eight points the 262,144 codes produce exactly twenty-three distinct shapes, drawn above: the star, the path, and twenty-one shapes between them, sorted by the length of their longest path from two to seven.

The canonical form is what makes the comparison honest. Two trees have the same shape exactly when their canonical strings agree, because a tree’s centre — the point or pair of points left after stripping off leaves layer by layer — is fixed by every symmetry, and below the centre each branch is determined by its sorted list of sub-branches. Alfred Aho, John Hopcroft and Jeffrey Ullman made this into a linear-time test in 1974, and it is the reason trees, unlike graphs in general, can be sorted into shapes as fast as they can be read. Applied to every code, it groups the 262,144 labelled trees on eight points into twenty-three piles whose sizes are the labelled counts of each shape.

The method does not survive growth. Codes number $n^{n-2}$ and shapes only about $3^n$, so almost all the work is wasted on relabellings of shapes already found, and at ten points the search would examine a hundred million codes to find 106 shapes. Counting has to work with shapes directly.

Rooted trees first #

Trees with a root are easier, because a rooted tree is nothing but a root and an unordered collection of rooted trees hanging from it. That sentence is a functional equation. If $R(x) = \sum r(n) x^n$ counts rooted shapes by number of points, then choosing a multiset of rooted trees to hang below a new root gives

$$R(x) = x \exp\Big(\sum_{k \ge 1} \frac{R(x^k)}{k}\Big),$$

the exponential being Pólya’s way of choosing a multiset from objects counted by $R$ — the terms $R(x^k)$ account for choosing the same subtree $k$ times, which is where symmetry enters. Reading off coefficients gives the recurrence

$$r(n+1) = \frac1n \sum_{k=1}^{n} \Big(\sum_{d \mid k} d\, r(d)\Big)\, r(n - k + 1),$$

which computes 1, 1, 2, 4, 9, 20, 48, 115, 286, 719 rooted shapes on one to ten points, and every value to two hundred, in exact whole numbers; the division by $n$ always comes out exact, which the computation checks. It is the same move, from a sentence describing how an object is built to an equation its generating function satisfies, that counts the Catalan objects — with the twist that the pieces here are unordered, so the equation needs Pólya’s exponential rather than a product.

Taking the root away #

A tree on $n$ points can be rooted at any of its $n$ points, but rooting it at two points that a symmetry swaps gives the same rooted shape, so the number of rooted shapes from one tree is the number of classes of points under its symmetries — not $n$, and not a constant. Otter found the correction that makes the root removable.

In every tree the number of classes of points exceeds the number of classes of edges by exactly one — unless some symmetry flips an edge end for end, in which case they are equal. The tree in the figure has five classes of points and four of edges. The computation checks the identity on all 47 trees with two to eight points, and the reason is the tree’s centre: every symmetry fixes it, and pairing each point class with the edge class leading towards the centre accounts for every class but one.

Summing over all shapes turns the identity into a count. Rooting at a point class counts rooted trees, $r(n)$; rooting at an edge class counts unordered pairs of rooted trees joined by an edge, $\tfrac12\big(\sum_{i + j = n} r(i)\, r(j) + r(n/2)\big)$; rooting at a flipped edge counts the pairs with two equal halves, $r(n/2)$. Points minus edges plus flipped edges is one for each tree, so

$$t(n) = r(n) - \tfrac12\Big(\sum_{i + j = n} r(i)\, r(j) - r(n/2)\Big),$$

with $r(n/2) = 0$ for odd $n$. It gives 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551 trees on one to twelve points, agreeing with the direct search to eight points and with the previous essay’s brute force to twelve.

How fast the shapes multiply #

There are 823,065 shapes on twenty points and a 24-digit number of them on sixty. The dashed curve is what the count would be if no tree had any symmetry, $n^{n-2}/n!$, which grows like $e^n$; the true count grows like $2.96^n$, and the gap is the symmetry almost every tree carries. Rooted shapes outnumber free ones by a factor of about $0.82\,n$: most points of a large tree lie in classes of their own, so there are nearly $n$ ways to root it, but not quite.

The base of the exponential is a property of the functional equation. Its radius of convergence $\rho$ is where the equation first fails to define $R$ smoothly, and that happens where $R(\rho) = 1$: writing the equation as $R = x e^{R} \cdot \exp\big(\sum_{k \ge 2} R(x^k)/k\big)$, the map $R \mapsto R e^{-R}$ turns round at $R = 1$, so

$$\rho = \exp\Big(-1 - \sum_{k \ge 2} \frac{R(\rho^k)}{k}\Big),$$

a fixed-point equation that a few dozen iterations solve, since $R(\rho^k)$ for $k \ge 2$ involves only small arguments where the series converges fast. The computation gives $\rho = 0.338321856899$ and $\alpha = 1/\rho = 2.955765285652$, Otter’s constant to twelve figures.

The power that the root costs #

The square-root singularity of $R$ at $\rho$ makes the rooted counts grow like $\alpha^n n^{-3/2}$, the same power as for rooted labelled trees divided by $n!$. Removing the root costs one more power of $n$, because the dissimilarity formula subtracts from $r(n)$ a quantity of nearly the same size, and the difference is smaller by a factor of $n$. So $t(n) \approx c\, \alpha^n n^{-5/2}$, and the figure divides the exact counts by $\alpha^n n^{-5/2}$ to find $c$: the ratio comes down from 0.66 at ten points to 0.5374 at two hundred, approaching Otter’s constant $c = 0.53495$ from above. The approach is slow because the next correction is only a factor of $1 + O(1/n)$.

The power is easy to miss in data. The plain ratio $t(n)/t(n-1)$ creeps towards $\alpha$ very slowly — 2.809 at fifty points, 2.919 at two hundred — because the factor $n^{-5/2}$ drags each ratio down by about $5\alpha/(2n)$. Multiply that factor back in, and the ratio is within $10^{-3}$ of $\alpha$ by fifty points and within $10^{-4}$ by two hundred. An estimate of a growth rate from the raw ratios of a sequence is biased by whatever power of $n$ sits in front, and the bias falls only like $1/n$.

The same power for labels and for shapes #

There is a coincidence in the exponents worth stopping on. Labelled trees divided by $n!$ number $n^{n-2}/n!$, which by Stirling’s estimate is about $e^n n^{-5/2}/\sqrt{2\pi}$: a base of $e$, and the same power $n^{-5/2}$ that Otter found for shapes. Rooted labelled trees divided by $n!$ carry $n^{-3/2}$, the same power as rooted shapes. The bases differ — $e$ against 2.9558, the difference being exactly how much the symmetries of shapes thin them out — but the powers agree.

That is not an accident of trees. Generating functions with a square-root singularity always produce coefficients with the power $n^{-3/2}$, and the Catalan numbers, which count ordered trees, grow like $4^n n^{-3/2}/\sqrt{\pi}$ for the same reason. Removing a root from a tree-like object always costs one power of $n$. The power is fixed by the kind of singularity, which is the same for every family of trees built by hanging branches below a root, and the base by where the singularity sits, which depends on what counts as the same tree. Physicists call such shared exponents universal, and the $-3/2$ of rooted trees is the one that appears in the theory of branching processes and random polymers. It contrasts sharply with the partition numbers, whose generating function has a much stronger singularity and whose growth is $e^{c\sqrt n}$, not exponential at all.

A random shape is a different random tree #

Counting shapes also changes what “a random tree” means. Choosing uniformly among labelled trees and forgetting the labels does not give every shape the same chance: a shape with symmetry group of size $s$ turns up in proportion to $n!/s$, so asymmetric shapes are favoured and stars almost never appear. Choosing uniformly among the shapes themselves is a different experiment, and the two random trees differ in their details. A random labelled tree has about one point in $e$ as a leaf, 36.8%; a random shape has noticeably more, about 43.8% by a computation of Robert Robinson and Allen Schwenk from 1975, because shapes with many leaves are the symmetric ones that the labelled count underweights.

In the large they agree. Both kinds of random tree are about $\sqrt n$ points high, and after rescaling both look like the same continuum random tree that David Aldous described in 1991 — the limit object that random trees of every reasonable kind converge to. The base of the exponential and the share of leaves depend on how sameness is counted; the overall shape of a big random tree does not. That is the probabilistic face of the universal exponents above, and it is why so many different counts of trees end in the same $n^{-3/2}$ and $n^{-5/2}$.

Labelling a shape back #

The count of shapes and the count of labelled trees can be reconciled one shape at a time. A shape with symmetry group of size $s$ can be labelled in $n!/s$ different ways, so $\sum_{\text{shapes}} n!/s = n^{n-2}$, the identity the previous essay checked to twelve points. Otter’s count gives the number of terms in that sum and Cayley’s formula its total, and neither determines the other: the twenty-three shapes on eight points have labelled counts ranging from 8 for the star to 20,160 for the path, and the sum of the twenty-three is 262,144. Every shape’s own labellings are a separate problem, and some of them carry structure of their own — whether every tree has a graceful labelling, with its edges carrying the differences 1 to $n - 1$, is the most famous open problem about labelling a given shape.

The alkanes #

Cayley’s motive was chemical, and the same counting handles it with one change. An alkane $\mathrm{C}_n\mathrm{H}_{2n+2}$ has a carbon skeleton that is a tree in which no carbon has more than four carbon neighbours, and two molecules with the same skeleton are the same compound. Capping the branching in the functional equation — an alkyl group is a root with at most three groups below it, counted by the cycle index of the symmetric group on three slots, and a whole molecule a point with at most four — and applying Otter’s correction gives 1, 1, 1, 2, 3, 5, 9, 18, 35, 75 isomers for one to ten carbons: methane, ethane and propane each have one skeleton, butane two, pentane three, and decane seventy-five. Eicosane, with twenty carbons, has 366,319, and an alkane with forty carbons 62,481,801,147,341. The cap slows the growth from $2.96^n$ to about $2.82^n$, and Henze and Blair’s counts of 1931, done by hand to forty carbons with these recurrences, agree with every one.

Pólya’s paper of 1937 was written to count exactly such things. His theorem counts colourings of a structure up to its symmetries by averaging, over the symmetries, how many colourings each one fixes — the rule that makes necklaces prove Fermat’s little theorem — and it gave chemists the numbers of substituted benzenes, of alcohols and of isomers with a given formula in one sweep. The recurrence above is Pólya’s theorem applied to the symmetries of the branches hanging from a point, and the cycle indices of the symmetric groups on three and four slots are the averages that do the work for the alkanes.

The chemistry stops agreeing at larger sizes for reasons the counting cannot see. A tree count is a count of connections; real molecules also come in mirror-image forms when a carbon carries four different groups, and in shapes that cannot exist because their branches would crowd one another in space. Counts of stereoisomers need the symmetries of three-dimensional space as well as those of the graph, and the long-chain counts are counts of graphs, not of molecules anyone could make.

What the counting cannot show #

Every number here is exact, computed in whole numbers of any size, and the recurrence is checked against direct search wherever direct search is affordable — to eight points for trees, and through the published counts for alkanes. What the figures cannot show is any formula: there is none for $t(n)$, and the constants $\alpha$ and $c$ are known only as solutions of the functional equation, computed numerically. Nothing in the figures says whether $\alpha$ is algebraic, transcendental or expressible by known constants; nobody knows.

Nor do the drawings reveal the symmetries they count. The trees are drawn from their centres with branches spread by size, which shows some symmetries as mirror images and hides others, and the dissimilarity identity was checked from the trees’ structure, not read off the pictures.

Still open: what the constant is #

Is Otter’s constant $\alpha = 2.9557652856\ldots$ anything other than the root of its own equation? The functional equation determines it, and computing it to hundreds of digits is routine; no closed form is known, and no proof that none exists. The same is true of the constants for alkanes, for trees with other degree restrictions, and for most counts of unlabelled structures, which are all governed by equations of Pólya’s type. By contrast the labelled counts nearly always have closed forms, because labels remove the terms $R(x^k)$ for $k \ge 2$ that carry the symmetry. Whether there is a general reason that symmetry-weighted counting produces constants with no closed form, or only that nobody has found the forms, is a question without a framework. What is known is how to compute such constants to any precision, quickly and with proven error bounds, which for most purposes is all a closed form would have supplied.

The root, the edges and the count #

A tree has one more class of points than of edges, unless an edge is flipped, and that one fact turns the easy count of rooted tree shapes into the hard count of tree shapes. The rooted shapes come from a functional equation read coefficient by coefficient; Otter’s correction subtracts the trees rooted at edges; and the result counts 23 shapes on eight points, 823,065 on twenty and an 89-digit number on two hundred, growing like $0.535 \times 2.9558^n / n^{5/2}$, with the extra power of $n$ the price of not knowing where the root is. Capping the branching at four counts the alkanes.