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 
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
This power series satisfies
where 
is the generating
function for unrooted trees. A generating
function for 
can be written using a product involving
the sequence itself as
 |
(5)
|
The number of rooted trees can also be calculated from the recurrence
relation
 |
(6)
|
with 
and 
, where the
second sum is over all 
which divide 
(Finch 2003).
As shown by Otter (1948),
(OEIS A051491; Odlyzko 1995; Knuth 1997, p. 396), where 
is given by the unique positive root of
 |
(9)
|
If 
is the number of nonisomorphic rooted trees on
nodes, then an asymptotic
series for 
is given by
 |
(10)
|
where the constants can be computed in terms of partial derivatives of the function
![F(x,y)=xexp[y+sum_(k=2)^infty(T(x^k))/k]-y](/images/equations/RootedTree/NumberedEquation5.gif) |
(11)
|
(Plotkin and Rosenthal 1994; Finch 2003).
SEE ALSO: Free Tree,
Ordered Tree,
Planted Tree,
Red-Black
Tree,
Rooted Graph,
Tree,
Weakly Binary Tree
REFERENCES:
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. https://algo.inria.fr/bsolve/.
Harary, 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. https://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." https://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. 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. https://mathworld.wolfram.com/RootedTree.html
![xexp[sum_(r=1)^(infty)1/rT(x^r)]](/images/equations/RootedTree/Inline13.gif)
![T(x)-1/2[T^2(x)-T(x^2)],](/images/equations/RootedTree/Inline16.gif)
Contact the MathWorld Team
(1+e)/2
