In graph theory, a recursive tree (i.e., unordered tree) is a labeled, rooted tree. A size- recursive tree's vertices are labeled by distinct positive integers, 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.
The number of size-n recursive trees is given by
Tn=(n-1)!.
Hence the exponential generating function T(z) of the sequence Tn is given by
T(z)=\sumn\geTn
| zn | =log\left( | |
| n! |
| 1 | |
| 1-z |
\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+
| 1 | |
| 1! |
⋅ \circ x F +
| 1 | |
| 2! |
⋅ \circ x F*F +
| 1 | |
| 3! |
⋅ \circ x F*F*F* … =\circ x \exp(F),
where
\circ
*
By translation of the formal description one obtains the differential equation for T(z)
T'(z)=\exp(T(z)),
with T(0) = 0.
There are bijective correspondences between recursive trees of size n and permutations of size n - 1.
Recursive trees can be generated using a simple stochastic process. Such random recursive trees are used as simple models for epidemics.