TOPICS
Search

Rooted Tree


RootedTrees

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

T(x)=sum_(n=0)^(infty)T_nx^n
(1)
=x+x^2+2x^3+4x^4+9x^5+20x^6+48x^7+115x^8+286x^9+719x^(10)+....
(2)

This power series satisfies

T(x)=xexp[sum_(r=1)^(infty)1/rT(x^r)]
(3)
t(x)=T(x)-1/2[T^2(x)-T(x^2)],
(4)

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

 xproduct_(n=1)^infty1/((1-x^n)^(T_n))=sum_(n=1)^inftyT_nx^n.
(5)

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

 T_(i+1)=1/isum_(j=1)^i(sum_(d|j)T_dd)T_(i-j+1),
(6)

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

alpha=lim_(n->infty)(T_n)/(T_(n-1))
(7)
=2.955765...
(8)

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

 T(1/x)=1.
(9)

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

 T_n∼alpha^nn^(-3/2)(0.4399240125...+(0.0441699018...)/n+(0.2216928059...)/(n^2)+(0.8676554908...)/(n^3)+...),
(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
(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

Rooted Tree

Cite this as:

Weisstein, Eric W. "Rooted Tree." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/RootedTree.html

Subject classifications