Rooted Tree (original) (raw)
Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology
Alphabetical Index New in MathWorld
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](http://mathworld.wolfram.com/images/equations/RootedTree/NumberedEquation5.svg) |
(11) |
|---|
(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
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.http://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. 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. Combinatorial Algorithms: An Update. Philadelphia, PA: SIAM, 1989.
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Rooted Tree." FromMathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/RootedTree.html