Labeled Tree

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).

REFERENCES

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.