Sixteen trees on four points

Four points, labelled 1 to 4. Join them with three edges so that everything is connected and nothing loops. How many different ways are there?

Sixteen. On five points there are 125, on six there are 1,296, and the pattern is n to the power n − 2. That is Cayley’s formula, and the exponent is what makes it worth explaining: nothing about connecting points suggests a power two less than the number of them.

Why the labels matter #

The count is of labelled trees, and the qualification is doing a great deal of work.

Ignoring labels, there are only two shapes on four points: a path, and a star with one centre joined to three leaves. The sixteen come from asking which labels sit where — there are 12 ways to label a path and 4 ways to label a star, and 12 + 4 = 16.

That split explains why the unlabelled count is a much harder problem. Counting labelled objects is usually the easier question because there are no symmetries to worry about: two labelled trees are the same only if they have exactly the same edges. Counting shapes means quotienting by all the relabellings that produce the same picture, and the quotient is uneven — a path can be labelled in more ways than a star, because the star has more symmetry.

The arithmetic of that split is worth doing once. There are 24 ways to write four labels in a row, and a path read forwards is the same path read backwards, so the 24 orderings give 12 distinct labelled paths. A star is determined by which label is at the centre, so there are 4 of them. Every one of the 16 is one or the other, and the blocks a symmetry cuts out are exactly what makes the two divisions different: the path’s symmetry group has two elements and the star’s has six.

This is the same asymmetry that makes counting colourings up to symmetry a separate subject from counting colourings. Labelled counts come out as clean formulas; unlabelled counts come out as sequences with no closed form.

A tree, written down as a list #

The proof of the formula is a code. Given a tree, produce a list of numbers; given the list, reconstruct the tree. If the two operations undo each other, the trees and the lists are in one-to-one correspondence, and counting lists is trivial.

The rule is: repeatedly find the leaf with the smallest label, record the label of its neighbour, and delete the leaf. Stop when two points are left. For a tree on n points that produces a list of n − 2 entries, each of which is one of the n labels — so there are n to the power n − 2 possible lists.

The encoding is easy to believe. The decoding is where the argument lives.

Reading the list backwards #

Given a list, the tree can be recovered without guessing, and the key is a single observation: a label appears in the list exactly as many times as its point has neighbours, minus one.

So the leaves of the original tree are precisely the labels that never appear in the list. The smallest of those was the first leaf removed, and the first entry of the list says what it was attached to, which reconstructs the first edge. Delete that leaf, cross off the first entry, and repeat: the process is forced at every step, with no choices to make.

When the list runs out, two points remain and there is exactly one edge left to draw between them.

Nothing in that procedure could have gone differently, which is what makes it a genuine inverse rather than a plausible reversal. Encoding then decoding returns the tree it started from; decoding then encoding returns the list. The correspondence is exact, so the number of trees is the number of lists, which is n to the power n − 2.

Why a tree can be coded at all #

The decoding works because trees are rigid in a way that most graphs are not, and the rigidity is worth stating separately because it is what the whole construction rests on.

A tree on n points has exactly n − 1 edges — one fewer than the number of points — and that is forced. Fewer and it is disconnected; more and it has a cycle. So a tree is simultaneously the sparsest connected graph and the densest acyclic one, which is a coincidence of exactly the kind that makes an object countable.

Two consequences follow immediately and both are used above. Every tree with at least two points has at least two leaves, since the degrees add to 2(n − 1) and cannot all be two or more; that is what guarantees the encoding never gets stuck. And removing a leaf from a tree leaves a tree, which is what lets the encoding recurse.

These are the same counting facts that decide when a walk over every bridge exists — there, degrees are counted modulo two rather than added up — and they are the reason so many statements about trees can be proved by peeling one point off and appealing to a smaller case.

Checked by enumeration #

The argument above is a proof and it is also the kind of proof that is easy to get subtly wrong — an off-by-one in the length of the list, a tie-breaking rule that is not quite forced, a claim of uniqueness that fails on some small case.

So the figures check it. For each size up to six, every tree is generated by brute force over subsets of edges, every one is encoded, and two things are required: that no two trees produce the same list, and that the number of lists produced is exactly n to the power n − 2. For six points that is 1,296 trees, each encoded and compared against all the others.

Both halves are needed. Distinct codes with too few of them would mean the encoding is injective but not onto; the right number of codes with a repeat among them would mean the count is a coincidence. Together they say the correspondence is a bijection, which is the whole content of the theorem.

Counting by bijection, as a method #

Setting up a one-to-one correspondence with something easier to count is the standard move in this part of the subject, and it is worth putting several instances side by side.

The Catalan numbers count triangulations of a polygon, bracket sequences, binary trees and lattice paths that stay above a diagonal, and all of those equalities are proved by exhibiting correspondences. Pascal’s triangle counts subsets and lattice paths at once for the same reason.

What distinguishes the Prüfer code from most such correspondences is how far it goes beyond the count. The code is a genuine data structure — a tree on n labelled points can be stored in n − 2 numbers rather than as a list of edges, and reconstructed from it. That is a compression scheme obtained as a side effect of a counting argument, and it is used in practice.

The code also proves more than the headline formula. Since a label appears in the list once fewer than its degree, the number of trees in which point k has a specified degree can be read off directly by counting lists with a specified number of occurrences — a refined count that follows from the same correspondence with no extra work.

What it counts, in the other language #

There is a second reading of the same number that connects it to a different corner of the subject.

A tree on n labelled points is a spanning tree of the complete graph on those points: a subset of its edges that reaches every point without a cycle. So Cayley’s formula says the complete graph on n points has n to the power n − 2 spanning trees, and asked that way it is a special case of a much more general theorem.

The matrix-tree theorem says the number of spanning trees of any graph is a determinant — take the matrix whose diagonal is the degrees and whose off-diagonal entries are minus one for each edge, delete any row and column, and take the determinant. For the complete graph that determinant evaluates to n to the power n − 2, which is Cayley’s formula obtained by linear algebra rather than by coding.

Two proofs of one formula, and they generalise in different directions: the code refines into degree-specified counts, and the determinant extends to every graph.

The determinant route has a further advantage that is easy to miss. It computes the count for a graph that is not complete — a grid, a cube, a road network — where no coding argument is available and no formula exists. The spanning trees of a graph are what a network’s redundancy is measured by, and the number of them is a determinant away for any graph somebody can write down, which is a far more useful statement than a formula for one family. The rank of a matrix is what the deletion of a row and a column is really about: the full matrix is singular for the same reason every row sums to zero, and the deleted minor is what carries the information.

There is one more count worth putting beside these. Not every subset of n − 1 edges is a tree, and the ones that fail do so by containing a cycle and therefore missing a point. At four points, 20 subsets of three edges give 16 trees, so exactly 4 fail — one for each triangle in the complete graph, since a triangle plus an isolated point is the only way to fail on four points. That kind of small-case accounting is what makes an exhaustive enumeration worth running: the failures are as informative as the successes, and a count that does not add up is the first sign of an error.

The count of shapes, and why nobody has a formula for it #

Setting the labelled count beside the unlabelled one shows what the labels bought.

The number of trees on n labelled points is 1, 1, 3, 16, 125, 1296. The number of tree shapes on n points is 1, 1, 1, 2, 3, 6, 11, 23, 47, 106 — a sequence with no closed form, computed by a generating function that satisfies an equation in terms of itself, and whose growth rate is a constant nobody can write in elementary terms.

The reason for the difference is the one given above: dividing by symmetry is not a division. If every tree had exactly n factorial labellings, the shape count would be the labelled count divided by n factorial and the formula would survive. Symmetric trees have fewer labellings than that, the deficit varies from tree to tree, and the arithmetic falls apart.

That contrast is a reliable guide to which counting questions are answerable. Counting arrangements with everything distinguishable tends to give a formula; counting them up to symmetry tends to give a sequence. Burnside’s average is the tool for the second case and it turns a hard count into an average of easier ones rather than into a formula.

What it costs #

Generating every tree on n points by testing every set of n − 1 edges costs the number of such subsets, which is a binomial coefficient and grows fast: 20 subsets at four points, 210 at five, 3,003 at six, 54,264 at eight. The figures stop at six for that reason, and the count they verify grows faster still.

Encoding is cheap. A careful implementation of the Prüfer code runs in time proportional to n, by keeping track of which points have become leaves rather than searching for the smallest each time — though the obvious implementation searches, and costs n² for no good reason.

The enumeration is also the reason these figures are drawn at all rather than asserted. A formula printed beside a picture of one tree is a claim; sixteen trees drawn from a search that took every three-edge subset and kept the acyclic ones is a measurement, and the two differ in exactly the way this site cares about. The same choice was made for the sixteen spheres that fill a cube and for the twenty-four syllogisms out of two hundred and fifty-six: where the whole space is small enough to walk, walking it is better evidence than any argument about it.

Generating a random labelled tree uniformly is where the code earns its keep in practice. Choosing a random tree by picking edges at random and rejecting cycles is fiddly and biased; choosing n − 2 labels at random and decoding is uniform by construction, because the correspondence is exact and every list is equally likely. That is the standard method, and it exists only because the bijection does.

What the picture cannot show #

Sixteen trees fit on a page and 1,296 do not. The figure showing every tree is drawn at four points because that is the largest case a reader can check by eye, and the claim being made is about every n.

The encoding figure shows one tree and one code. That the correspondence is one-to-one is a statement about all of them at once, and it is checked by enumeration rather than shown.

And nothing in these drawings distinguishes a labelled tree from a shape. The labels are printed on the points, but the visual difference between two trees that are the same shape with different labels is a matter of reading small numbers — which is exactly the distinction the whole count turns on, and the one a picture conveys worst.

The ladder from here #

Rungs above: the matrix-tree theorem, and the determinant that counts spanning trees of any graph. The multivariate refinement, where each tree is weighted by its edges and the determinant becomes a polynomial. Counting forests, and the trees on n points with a specified number of components. Unlabelled trees, where the counting needs a generating function and Pólya’s enumeration rather than a bijection. Random trees, and the shape a uniformly chosen large tree tends to have — its diameter grows like the square root of n, which is not what most people guess. Random graphs and the moment a giant connected piece appears. And the parking-function bijection, which counts the same objects a third way and connects them to a problem about cars and parking spaces.

The shape of the idea #

A formula with an exponent nobody expects usually means a correspondence nobody has found yet, and the search for the correspondence is more valuable than the formula.

Cayley published the count in 1889 with a proof by generating functions. Prüfer’s code arrived in 1918 and replaced an argument that verified the number with one that explains it: the trees on n points are lists of n − 2 labels, because a tree is a list of n − 2 labels once the right way of writing it down has been found. The formula stops being a coincidence at that moment.

The general lesson is one this site keeps meeting. Two collections have the same size for one of two reasons — either both have been counted and the answers agree, or a correspondence has been exhibited. The first is a fact and the second is an explanation, and the second usually comes with a data structure, an algorithm, or a refinement attached.