Recursive tree

In graph theory, a recursive 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.

Properties

The number of size-n recursive trees is given by
Hence the exponential generating function T of the sequence T_n 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. Then
where 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
with T = 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.