graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, 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, e.g., including only woody plants with secondary growth, only ...

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

positive integer In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positiv ...

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 representation of an infinite sequence of numbers as the coefficients of a formal power series. Generating functions are often expressed in closed form (rather than as a series), by some expression invo ...

''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. Then :

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 In mathematics, specifically set theory, the Cartesian product of two sets and , denoted , is the set of all ordered pairs where is an element of and is an element of . In terms of set-builder notation, that is A\times B = \. A table c ...

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, bijective function, or one-to-one correspondence is a function between two sets such that each element of the second set (the codomain) is the image of exactly one element of the first set (the domain). Equival ...

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

permutation In mathematics, a permutation of a set can mean one of two different things: * an arrangement of its members in a sequence or linear order, or * the act or process of changing the linear order of an ordered set. An example of the first mean ...

s of size ''n'' − 1.

Applications

Recursive trees can be generated using a simple

stochastic process In probability theory and related fields, a stochastic () or random process is a mathematical object usually defined as a family of random variables in a probability space, where the index of the family often has the interpretation of time. Sto ...

. Such random recursive trees are used as simple models for epidemics.

References

*''

Analytic Combinatorics Analytic combinatorics uses techniques from complex analysis to solve problems in enumerative combinatorics, specifically to find asymptotic estimates for the coefficients of generating functions. History One of the earliest uses of analyti ...

'', 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, 367–407, 2006. Trees (graph theory)