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

			(1)
			(2)

This power series satisfies

			(3)
			(4)

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

			(7)
			(8)

(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

(11)

(Plotkin and Rosenthal 1994; Finch 2003).