Recursive tree

Recursive trees are non-planar labeled rooted trees. A size n tree recursive tree is labeled by distinct integers $1,2,\dots ,n$, where the labels are strictly increasing starting at the root labeled 1. Since recursive trees are non-planar there is no left to right order. E.g. the following two size three recursive trees are the same.

       1          1   
      / \   =    / \           
     /   \      /   \
    2     3    3     2

Properties

Let $T_{n}$ denote the number of size n recursive trees.

$T_{n}=(n-1)!.$

Hence the exponential generating function T(z) of the sequence T_n is given by

$T(z)=\sum _{n\geq 1}T_{n}{\frac {z^{n}}{n!}}=\log {\big (}{\frac {1}{1-z}}{\big )}.$

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 {1}{1!}}\cdot \circ \times F+{\frac {1}{2!}}\cdot \circ \times F*F+{\frac {1}{3!}}\cdot \circ \times F*F*F\dots =\circ \times \exp(F),$

where $\circ$ denotes the node labelled by 1, $\times$ the cartesian product and $*$ the partition product for labelled 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 correspondences between recursive trees of size n and permutations of size n-1.

Applications

Recursive Trees are used as simple models for epidemics.