Encyclopedia

Recursive tree

Tree graph with nodes numbered in order of distance from the root

Wikipedia contributorsAdapted for Fathomly · View authors

1 min read
Source updated April 16, 2025

In graph theory, a recursive tree (i.e., unordered tree) is a labeled, rooted tree. A size-n recursive tree's vertices are labeled by distinct positive 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 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.

01Properties

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 _{n\geq 1}T_{n}{\frac {z^{n}}{n!}}=\log \left({\frac {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 +{\frac {1}{1!}}\cdot \circ \times F+{\frac {1}{2!}}\cdot \circ \times F*F+{\frac {1}{3!}}\cdot \circ \times F*F*F*\cdots =\circ \times \exp(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'(z)=\exp(T(z)),$

with T(0) = 0.

02Bijections

There are bijective correspondences between recursive trees of size n and permutations of size n − 1.

03Applications

Recursive trees can be generated using a simple stochastic process. Such random recursive trees are used as simple models for epidemics.

Watch videos about Recursive treeExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Recursive tree”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.