Recursive tree

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

1 1 / = / / / 2 3 3 2

Properties

The number of size-"n" recursive trees is given by

:$T\_n=\; (n-1)!.\; ,$

Hence the exponential generating function "T"("z") of the sequence "T"_"n" is given by

:$T(z)=\; sum\_\{nge\; 1\}\; T\_n\; frac\{z^n\}\{n!\}=logleft(frac\{1\}\{1-z\}\; ight).$

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\; imes\; F\; +\; frac\{1\}\{2!\}cdot\; circ\; imes\; F*\; F+\; frac\{1\}\{3!\}cdot\; circ\; imes\; F*\; F*\; F\; *\; cdots=\; circ\; imesexp(F),$

where $circ$ 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"("z")

:$T\text{'}(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.

References