A tree with its nodes labeled. The number of labeled trees on nodes is , the first few values of which are 1, 1, 3, 16, 125,
1296, ... (OEIS A000272). Cayley (1889) provided
the first proof of the number of labeled trees (Skiena 1990, p. 151), and a
constructive proof was subsequently 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
an embedding 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).
Biggs, N. L.; Lloyd, E. K.; and Wilson, R. J. Graph
Theory 1736-1936. Oxford, England: Oxford University Press, p. 51, 1976.Cayley,
A. "A Theorem on Trees." Quart. J. Math.23, 376-378, 1889.Prüfer,
H. "Neuer Beweis eines Satzes über Permutationen." Arch. Math.
Phys.27, 742-744, 1918.Riordan, J. An
Introduction to Combinatorial Analysis. New York: Wiley, p. 128, 1980.Skiena,
S. Implementing
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading,
MA: Addison-Wesley, 1990.Sloane, N. J. A. Sequence A000272/M3027
in "The On-Line Encyclopedia of Integer Sequences."Szekeres,
G. Distribution of Labeled Trees by Diameter. New York: Springer-Verlag, pp. 392-397,
1983.van Lint, J. H. and Wilson, R. M. A
Course in Combinatorics. New York: Cambridge University Press, 1992.