graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, a recursive tree (i.e., unordered tree) is a labeled, rooted

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...

. A size- recursive tree's vertices are labeled by distinct

positive integer In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''cardinal n ...

s , where the labels are strictly increasing starting at the root labeled 1. Recursive trees are non-planar, which means that the children of a particular vertex are not ordered; for example, the following two size-3 recursive trees are equivalent: . Recursive trees also appear in literature under the name Increasing Cayley trees.

Properties

The number of size-''n'' recursive trees is given by :

T_n= (n-1)!. \,

Hence the exponential

generating function In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary seri ...

''T''(''z'') of the sequence ''T''_''n'' is given by :

T(z)= \sum_ T_n \frac=\log\left(\frac\right).

Combinatorically a recursive tree can be interpreted as a root followed by an unordered sequence of recursive trees. Let ''F'' denote the family of recursive trees. :

F= \circ + \frac\cdot \circ \times F
+ \frac\cdot \circ \times F* F
+ \frac{3!}\cdot \circ \times F* F* F * \cdots
= \circ\times\exp(F),

where

\circ

denotes the node labeled by 1, × the Cartesian product and

*

the partition product for labeled objects. By translation of the formal description one obtains the differential equation for ''T''(''z'') :

T'(z)= \exp(T(z)),

with ''T''(0) = 0.

Bijections

There are

bijective In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...

correspondences between recursive trees of size ''n'' and

permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or proc ...

s of size ''n'' − 1.

Applications

Recursive trees can be generated using a simple stochastic process. Such random recursive trees are used as simple models for epidemics.

References

*''

Analytic Combinatorics In combinatorics, the symbolic method is a technique for counting combinatorial objects. It uses the internal structure of the objects to derive formulas for their generating functions. The method is mostly associated with Philippe Flajolet an ...

'', Philippe Flajolet and Robert Sedgewick, Cambridge University Press, 2008 *''Varieties of Increasing Trees'', Francois Bergeron, Philippe Flajolet, and Bruno Salvy. In Proceedings of the 17th Colloquium on Trees in Algebra and Programming, Rennes, France, February 1992. Proceedings published in Lecture Notes in Computer Science vol. 581, J.-C. Raoult Ed., 1992, pp. 24–48. *''Profile of random trees: correlation and width of random recursive trees and binary search trees'' Michael Drmota and Hsien-Kuei Hwang, Adv. Appl. Prob., 37, 1-21, 2005. *''Profiles of random trees: Limit theorems for random recursive trees and binary search trees'', Michael Fuchs, Hsien-Kuei Hwang, Ralph Neininger., Algorithmica, 46:3-4, 2006, 367-407, 2006. Trees (graph theory)