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
nodes for , 2, ... are 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842,
4766, ... (OEIS A000081). Denote the number
of rooted trees with
nodes by ,
then the generating function is
power series satisfies
is the generating function for unrooted trees. A generating function
for can be written using a product involving
the sequence itself as
The number of rooted trees can also be calculated from the
and , where the second sum is over all which divide (Finch 2003).
As shown by Otter (1948),
A051491; Odlyzko 1995; Knuth 1997, p. 396), where
is given by the unique positive root
is the number of nonisomorphic rooted
nodes, then an asymptotic series for 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
Weakly Binary Tree
Explore with Wolfram|Alpha
References Borwein, J. and Bailey, D. Wellesley, MA: A
K Peters, p. 22, 2003. Mathematics by Experiment: Plausible Reasoning in the 21st Century. Finch, S. R. "Otter's Tree Enumeration
Constants." §5.6 in Cambridge, England: Cambridge University Press, pp. 295-316,
Constants. Finch, S. "Two Asymptotic Series." December 10, 2003.
F. Reading, MA: Addison-Wesley, pp. 187-190 and 232, 1994. Graph
F. and Palmer, E. M. "Rooted Trees." §3.1 in New York: Academic Press, pp. 51-54, 1973. Graphical
Reading, MA: Addison-Wesley, 1997. The
Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed. Nijenhuis, A. and Wilf, H. New York: Academic Press,
Algorithms for Computers and Calculators, 2nd ed. Odlyzko, A. M. "Asymptotic Enumeration Methods."
In (Ed. R. L. Graham, M. Grötschel,
and L. Lovász). Cambridge, MA: MIT Press, pp. 1063-1229, 1995. Handbook
of Combinatorics, Vol. 2 http://www.dtc.umn.edu/~odlyzko/doc/asymptotic.enum.pdf. Otter,
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." http://www.theory.csc.uvic.ca/~cos/inf/tree/RootedTree.html. Sloane,
N. J. A. Sequences A000081/M1180
and A051491 in "The On-Line Encyclopedia
of Integer Sequences." Wilf, H. S. Philadelphia, PA: SIAM, 1989. Combinatorial
Algorithms: An Update. Referenced
on Wolfram|Alpha Rooted Tree
Cite this as:
Weisstein, Eric W. "Rooted Tree." From
--A Wolfram Web Resource. MathWorld https://mathworld.wolfram.com/RootedTree.html