Concept

Cayleys formula

The count n^(n−2) of trees that can be drawn on n labelled points. It was stated by Cayley in 1889 and has many proofs, including Prüfer's code and a bijection with parking functions.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

All 16 trees on 4 labelled points. Every tree on 4 labelled points, drawn one by one. There are 16 of them, which is 4 to the power 2.

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.

discrete · Labelled trees

Pollak's circle: one rotation in every n + 1 parks on the line. Several circles of numbered spots, each showing where cars park when every preference in a list is rotated by a fixed amount, with the one rotation that leaves the last spot empty highlighted.

Cars that park, and trees that grow

Three cars arrive at a one-way street with three spaces; each has a favourite space, drives to it, and takes the first free one from there on. Of the 27 lists of favourites, exactly 16 let every car park — the same 16 as the labelled trees on four points. The reason is a circular street with one extra space, on which every list parks and exactly one rotation of it leaves the extra space empty.

discrete · Labelled trees

Named alongside it

The objects these essays reach for when they reach for this one.

Bijection Counting argument Labelled tree Catalan numbers Encoding Exhaustive search Graph Leaf Permutation Prufer code Rotation Spanning tree

All concepts