Leaf — where it appears
Named by 2 essays across one field — each of them below, with the objects they name alongside it.
Also named here as prufer code — the same set of essays touches all of them, so they are one junction rather than several.
Sixteen trees on four points
How many ways are there to connect n labelled points into a single tree? The answer is n to the power n minus two, which is a strange enough formula to demand an explanation — and the explanation is a code that turns every tree into a short list of numbers, and every short list of numbers back into a tree.
A random tree is one part in e leaves
Choose a labelled tree on n points uniformly at random. A point is a leaf exactly when its label never appears in the tree's Prüfer code, so the share of leaves is (1 − 1/n)^(n − 2) — half the points for a tree on four, 36.8% for a large one, the reciprocal of e. The whole degree distribution follows the same way: one plus a Poisson count with mean one.
Named alongside it
The objects these essays reach for when they reach for this one.
Labelled treePrufer codeBijectionCatalan numbersCayleys formulaCounting argumente, the numberEncodingExhaustive searchExpectationGraphPoisson approximation