A random tree is one part in e leaves

Sixteen trees on four points counted the labelled trees on $n$ points, $n^{n-2}$ of them, with a code — Prüfer’s — that turns each tree into a list of $n - 2$ labels: strip the smallest leaf, write down its neighbour, repeat. Counting them is one question. Looking at a typical one is another. If a tree on a thousand points is chosen uniformly from all $1000^{998}$ of them, what does it look like? How many of its points are leaves? How many neighbours does a point usually have?

The Prüfer code answers these questions as easily as it answered the count, because it turns a uniformly random tree into a uniformly random list — $n - 2$ labels, each chosen independently and uniformly from $n$ — and a list is something probability knows how to handle.

A point’s degree is written in the Prüfer sequence #

The key fact is exact and small. When the sequence is built, a point’s label is written down once each time one of its neighbours is removed as a leaf — every neighbour but one, because the last edge of each point is either removed with the point itself or survives to the end. So a point’s degree is one more than the number of times its label appears in the Prüfer sequence. A leaf is a point whose label never appears; a point whose label appears three times has four neighbours.

For a random tree, the sequence is $n - 2$ independent uniform labels, so the number of times a particular label appears is a binomial count: $n - 2$ trials, each with chance $1/n$. The degree of a point in a random tree is therefore distributed exactly as

$$\Pr(\deg = k + 1) = \binom{n-2}{k}\left(\frac1n\right)^k\left(1 - \frac1n\right)^{n-2-k}.$$

For seven points the figure checks the formula against every tree there is — all $7^5 = 16{,}807$ of them, each visited through its code — and the counts agree with the binomial exactly. A point of a random tree on seven points is a leaf 46% of the time, has two neighbours 39% of the time, and three 13% of the time; more than four is rare, and six, the star’s centre, happens for 7 trees in 16,807.

One plus a Poisson count #

As $n$ grows, $n - 2$ trials with chance $1/n$ each is the textbook situation in which a binomial count becomes a Poisson count with mean $(n - 2)/n \to 1$ — many chances, each small, their expected total fixed. It is the approximation fourteen people within a day uses to count near-coincidences of birthdays, and it is accurate here for the same reason: the chance of any one label being drawn at any one position is tiny, and no single draw matters much. So in a large random tree,

$$\Pr(\deg = k + 1) \to \frac{e^{-1}}{k!}: \qquad \text{leaves } \tfrac1e \approx 36.8\%, \quad \text{degree 2 } \tfrac1e, \quad \text{degree 3 } \tfrac{1}{2e} \approx 18.4\%, \quad \text{degree 4 } \tfrac{1}{6e} \approx 6.1\%.$$

At two hundred points the binomial and Poisson bars are indistinguishable to the eye. The average degree is exactly $2(n - 1)/n$, a little under 2, because a tree on $n$ points has $n - 1$ edges; the distribution around that average is almost entirely made of ones, twos and threes, and a point of degree 10 in a large random tree is about a one-in-a-million event.

Leaves and points of degree two are equally common, $1/e$ each, which is the least expected feature of the list. A random tree is not bushy: nearly three quarters of its points have one or two neighbours, and a point with many branches is rare. It is closer to a tangle of long strands with short twigs than to the spreading canopy the word tree suggests. The largest degree in a random tree on $n$ points grows, but only like $\log n/\log\log n$ — five or six for a million points.

Sixteen thousand trees, sorted by leaves #

The number of leaves of the whole tree, rather than whether one point is a leaf, has an exact distribution too. A tree has $k$ leaves exactly when its code uses exactly $n - k$ different labels, and counting lists of length $n - 2$ that use exactly $m$ given labels is a classical problem: the answer involves the Stirling numbers of the second kind, $S(n - 2, m)$, which count the ways to split $n - 2$ positions into $m$ non-empty groups. Choosing which labels and assigning them to the groups gives Alfréd Rényi’s formula of 1959,

$$\#\{\text{trees on } n \text{ points with } k \text{ leaves}\} = \binom{n}{k}\,(n - k)!\,S(n - 2,\, n - k).$$

For seven points the figure runs through all 16,807 codes, sorts the trees by leaves, and checks each bar against the formula. The distribution is lopsided in an instructive way. Only 7 trees are stars, with six leaves, one for each choice of centre; 2,520 are paths, with two leaves, one for each ordering of the seven points up to reversal; and most of the mass sits at three and four leaves, around the mean of 3.24. That mean is $7 \times (6/7)^5$ exactly, since each point is a leaf with probability $(1 - 1/n)^{n-2}$ and expectation adds over points whatever the dependence between them.

Leaves are nearly independent #

Whether one point is a leaf and whether another is are not independent events — a tree on $n$ points has at least two leaves and at most $n - 1$, so knowing that most points are leaves says something about the rest. But the sequence makes the dependence small and exact. Two particular points are both leaves when neither label appears in the Prüfer sequence, which has probability $(1 - 2/n)^{n-2}$, tending to $e^{-2}$ — the product of the two separate chances. In a large random tree, leafhood is nearly independent from point to point, and that is why the leaf count behaves like a sum of independent coins.

The same holds for degrees in general. The counts of how often each label appears in a random list are the occupancy numbers of $n - 2$ balls thrown into $n$ boxes, and occupancy numbers are only weakly dependent: they must add up to $n - 2$, and that is essentially all that ties them together. The degree sequence of a random tree is, to a very good approximation, $n$ independent draws of one plus a Poisson count, constrained only to add to $2(n - 1)$. The Prüfer code turns a question about a connected structure into a question about balls in boxes, and balls in boxes is among the most thoroughly understood problems in probability.

Labelled trees are not unlabelled trees #

The count of seven-point trees by leaves contains a lesson about what “random tree” means. There are 2,520 labelled paths on seven points and only 7 labelled stars, yet as shapes there is one path and one star. The difference is symmetry. A star can be relabelled in $6! = 720$ ways that give back the same labelled tree, by permuting its leaves; a path has only its reversal. The number of labellings of a shape is $n!$ divided by its number of symmetries, so shapes with many symmetries are rare among labelled trees.

A uniformly random labelled tree is therefore not a uniformly random shape. It weighs each shape by how many ways it can be labelled, and the weighting favours long, irregular, asymmetric trees — which is exactly what the sixty-point tree in the first figure looks like. The number of unlabelled shapes on $n$ points has no formula as clean as $n^{n-2}$; Richard Otter showed in 1948 that it grows like a constant times $2.9558^n n^{-5/2}$, and counting it needs the symmetry-sensitive machinery of Pólya’s theory rather than a code. The labels are what make the problem easy, because they destroy the symmetries that make shapes hard to count.

The share of leaves, and where 1/e comes from #

The expected share of leaves is $(1 - 1/n)^{n-2}$: exactly one half for four points, 0.387 for ten, 0.370 for a hundred, and $1/e = 0.3679\ldots$ in the limit. The sampled trees at each size, 400 of them, sit on the curve.

The same constant appears in nobody gets their own hat, where the chance that a random shuffle of $n$ hats leaves no one with their own tends to $1/e$, and in the parking problem, where the chance that no car prefers the first space does. The mechanisms differ in detail — the hats are dependent draws, the sequence’s labels independent — but the shape is the same: $n$ opportunities, each with chance about $1/n$, all missed. Wherever something has $n$ chances of size $1/n$ and the question is whether it gets none, the answer is near $1/e$.

The share of leaves also concentrates. The number of leaves in a random tree on $n$ points has mean about $n/e$ and a standard deviation of order $\sqrt n$, so for a tree on a million points the leaf count is $367{,}879$ give or take a few hundred. Rényi proved that its distribution, suitably scaled, is normal — a random tree’s proportion of leaves is as predictable as a coin’s proportion of heads.

Other ways to grow a tree at random #

“Random tree” has other meanings, and the comparison shows how special the uniform one is. Grow a tree one point at a time, attaching each new point to an earlier point chosen uniformly at random: this random recursive tree is a model of how some family and citation trees grow. Its leaves make up half of its points in the limit, not $1/e$, because every newly attached point starts as a leaf and a point stays a leaf until something attaches to it — which, late in the growth, is unlikely.

Attach each new point instead to an earlier point chosen with probability proportional to its degree — the rich get richer — and the degrees develop a heavy tail: the share of points with degree $k$ falls only like $k^{-3}$, and a few points acquire enormous numbers of neighbours. That is the preferential attachment model proposed for the web and for citation networks, and its degree distribution is nothing like the uniform tree’s Poisson one, in which a point with ten neighbours is a one-in-a-million event.

The uniform labelled tree is the one with no history. It is not grown in any order; every tree is equally likely; and the absence of an order is what makes its degrees independent-looking and light-tailed. Growth processes remember who arrived first, and memory is what produces both the extra leaves of the recursive tree and the hubs of preferential attachment.

The Poisson counts here are the same Poisson counts that govern the moment a random graph joins up, where the number of isolated points in a sparse random graph tends to a Poisson law, and a room where nobody is alone, where the number of people without a birthday twin does. In each case many unlikely events, each of small probability and nearly independent of the others, add up to a Poisson count — and in the tree the events are the $n - 2$ draws of the sequence landing on one particular label.

The tree as a family #

There is a second way to see why the degree is one plus a Poisson count, and it explains more. A random labelled tree, with a root chosen and edges directed away from it, has the same distribution as a family tree in which each individual has a Poisson number of children with mean 1, conditioned to have exactly $n$ members in all. The root has a Poisson number of children; every other point has a parent and a Poisson number of children, so its degree is one more than a Poisson count — exactly the limit above.

This is the Galton–Watson process that the moment a giant appears uses to explore a sparse random graph, and it is critical: with mean exactly one child, the family neither grows nor shrinks on average, and conditioning it to reach size $n$ produces a long, thin tree. That is where the tree’s global shape comes from. A random labelled tree on $n$ points is tall — its height from a random root grows like $\sqrt{2\pi n}$, a result of Rényi and Szekeres from 1967 — and far from the balanced, logarithmic-height tree of a search structure, as the sixty-point tree in the first figure, eighteen layers deep, already shows.

What the counts and the samples cannot show #

The sixty-point tree is one sample. Its 25 leaves, 42% of its points, are a single draw from a distribution with mean $60 \times (59/60)^{58} \approx 22.6$ and a standard deviation of about 2.4; the figure shows what a random tree looks like, not its average.

The near-independence is argued from the sequence. The claim that two points are both leaves with probability $(1 - 2/n)^{n-2}$ follows from the sequence’s labels being independent; the figures check single-point probabilities and the whole leaf count exactly for seven points, and do not separately check the joint probabilities.

The Poisson limit is a limit. The degree distribution for finite $n$ is the binomial one, drawn exactly; the Poisson law is what it approaches, and the bars at 200 points show how close the approach is by then rather than proving it.

And the global shape is quoted. The height $\sqrt{2\pi n}$ and the family-tree description are results cited from the literature; the figures here concern degrees and leaves, the local shape, which the Prüfer code makes exact, and say nothing measured about height or diameter.

Still open: whether every tree is graceful #

Labelled trees carry one of the best-known open problems in graph theory, and it is about labelling rather than counting. Label the $n$ points of a tree with the numbers $0, 1, \ldots, n - 1$, each used once, and give each edge the absolute difference of its endpoints’ labels. The labelling is graceful if the $n - 1$ edges get the $n - 1$ different values $1, 2, \ldots, n - 1$. Paths are graceful — label them $0, n-1, 1, n-2, 2, \ldots$ along the path — and so are stars, caterpillars and many other families.

The graceful tree conjecture, posed by Ringel and Kotzig in the 1960s, says every tree is graceful, and it has been checked by computer for every tree on up to 35 points. It is not proved. A weaker statement it was introduced to attack — Ringel’s conjecture that the complete graph on $2n + 1$ points splits into copies of any fixed tree with $n$ edges — was proved for large $n$ by Montgomery, Pokrovskiy and Sudakov in 2020, by methods that give no hint of how to find the labelling the stronger conjecture asks for.

A tree seen through its code #

A uniformly random labelled tree is a uniformly random list in disguise, and its local shape is read off the list directly. A point’s degree is one more than its label’s count in the Prüfer sequence; a leaf is a label that never appears; and because the labels are independent and uniform, the degree is one plus a binomial count that becomes, for large trees, one plus a Poisson count with mean one. Leaves make up $1/e$ of a large random tree, points of degree two another $1/e$, and the few remaining points share the rest. The counting that sixteen trees on four points did exactly, tree by tree, becomes here a statement about proportions, and the proportions are the same whichever large tree is sampled.

The same code that proved Cayley’s formula is doing all of this work, which is the real point. A bijection is usually valued for the count it proves; this one is worth more for the probability it transfers, turning every question about the local structure of a random tree into a question about independent draws from a hat.

When a random object has a bijection with a random list, ask the list the question — here the question “how many neighbours?” became “how many times does this label appear?”, a question with a textbook answer, and the constant $1/e$ arrived as the chance that a label is never drawn.