A labeled tree is a tree with its nodes labeled. The number of labeled trees on 
nodes is 
for 
, the first few values of which are 1, 1, 3, 16, 125,
1296, ... (OEIS A000272). This count is Cayley's
formula (Cayley 1889; Skiena 1990, p. 151). A constructive proof was provided
by Prüfer (1918). Prüfer's result gives an encoding for labeled trees known
as Prüfer code (indicated underneath the trees above, where the trees are depicted
using a graph drawing with root
at the node labeled 1).
The probability that a random labeled tree is centered is asymptotically equal to 1/2 (Szekeres 1983; Skiena 1990, p. 167).
