In graph theory, a recursive tree (i.e., unordered tree) is a non-planar labeled rooted tree. A size-n recursive tree is labeled by distinct integers 1, 2, ..., n, 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 node are not ordered. E.g. the following two size-three recursive trees are the same.
Contents
1 1 / \ = / \ / \ / \ 2 3 3 2Recursive trees also appear in literature under the name Increasing Cayley trees.
Properties
The number of size-n recursive trees is given by
Hence the exponential generating function T(z) of the sequence Tn is given by
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.
where
By translation of the formal description one obtains the differential equation for T(z)
with T(0) = 0.
Bijections
There are bijective correspondences between recursive trees of size n and permutations 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.