Cayley's formula

Statement

Let $n \ge 2$ be an integer. Then the number of trees with vertex set $\{1, 2, \dots, n\}$ is $n^{n-2}$.

Remarks

The trees are labelled: two trees are the same only if they have the same edge set. Thus the formula counts the spanning trees of $K_n$. For $n = 3$ there are $3$ trees, and for $n = 4$ there are $16$. A proof uses the Prüfer sequence, a bijection between these trees and the sequences of length $n - 2$ over $\{1, \dots, n\}$.

History

Carl Wilhelm Borchardt found the formula in 1860. Arthur Cayley extended it in 1889, and the formula has his name.

Explanations

L1 human

Label $n$ points with the numbers $1$ to $n$ and count the ways to connect them by a tree. For $4$ points there are $4^2 = 16$ ways: $12$ paths and $4$ stars.