Rooted Tree


A rooted tree is a tree in which a special ("labeled") node is singled out. This node is called the "root" or (less commonly) "eve" of the tree. Rooted trees are equivalent to oriented trees (Knuth 1997, pp. 385-399). A tree which is not rooted is sometimes called a free tree, although the unqualified term "tree" generally refers to a free tree.

A rooted tree in which the root vertex has vertex degree 1 is known as a planted tree.

The numbers of rooted trees on n nodes for n=1, 2, ... are 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, ... (OEIS A000081). Denote the number of rooted trees with n nodes by T_n, then the generating function is


This power series satisfies


where t(x) is the generating function for unrooted trees. A generating function for T_n can be written using a product involving the sequence itself as


The number of rooted trees can also be calculated from the recurrence relation


with T_0=0 and T_1=1, where the second sum is over all d which divide j (Finch 2003).

As shown by Otter (1948),


(OEIS A051491; Odlyzko 1995; Knuth 1997, p. 396), where alpha is given by the unique positive root of


If T_n is the number of nonisomorphic rooted trees on n nodes, then an asymptotic series for T_n is given by


where the constants can be computed in terms of partial derivatives of the function


(Plotkin and Rosenthal 1994; Finch 2003).

See also

Free Tree, Ordered Tree, Planted Tree, Red-Black Tree, Rooted Graph, Tree, Weakly Binary Tree

Explore with Wolfram|Alpha


Borwein, J. and Bailey, D. Mathematics by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: A K Peters, p. 22, 2003.Finch, S. R. "Otter's Tree Enumeration Constants." §5.6 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 295-316, 2003.Finch, S. "Two Asymptotic Series." December 10, 2003., F. Graph Theory. Reading, MA: Addison-Wesley, pp. 187-190 and 232, 1994.Harary, F. and Palmer, E. M. "Rooted Trees." §3.1 in Graphical Enumeration. New York: Academic Press, pp. 51-54, 1973.Knuth, D. E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed. Reading, MA: Addison-Wesley, 1997.Nijenhuis, A. and Wilf, H. Combinatorial Algorithms for Computers and Calculators, 2nd ed. New York: Academic Press, 1978.Odlyzko, A. M. "Asymptotic Enumeration Methods." In Handbook of Combinatorics, Vol. 2 (Ed. R. L. Graham, M. Grötschel, and L. Lovász). Cambridge, MA: MIT Press, pp. 1063-1229, 1995., R. "The Number of Trees." Ann. Math. 49, 583-599, 1948.Plotkin, J. M. and Rosenthal, J. W. "How to Obtain an Asymptotic Expansion of a Sequence from an Analytic Identity Satisfied by Its Generating Function." J. Austral. Math. Soc. Ser. A 56, 131-143, 1994.Pólya, G. "On Picture-Writing." Amer. Math. Monthly 63, 689-697, 1956.Ruskey, F. "Information on Rooted Trees.", N. J. A. Sequences A000081/M1180 and A051491 in "The On-Line Encyclopedia of Integer Sequences."Wilf, H. S. Combinatorial Algorithms: An Update. Philadelphia, PA: SIAM, 1989.

Referenced on Wolfram|Alpha

Rooted Tree

Cite this as:

Weisstein, Eric W. "Rooted Tree." From MathWorld--A Wolfram Web Resource.

Subject classifications