Misplaced Pages

Recursive tree

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Tree graph with nodes numbered in order of distance from the root
This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (July 2023) (Learn how and when to remove this message)

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: 3/\2 = 2/\3.

Recursive trees also appear in literature under the name Increasing Cayley trees.

Properties

The number of size-n recursive trees is given by

T n = ( n − 1 ) ! . {\displaystyle T_{n}=(n-1)!.\,}

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

T ( z ) = ∑ n ≥ 1 T n z n n ! = log ⁡ ( 1 1 − z ) . {\displaystyle 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 = ∘ + 1 1 ! ⋅ ∘ × F + 1 2 ! ⋅ ∘ × F ∗ F + 1 3 ! ⋅ ∘ × F ∗ F ∗ F ∗ ⋯ = ∘ × exp ⁡ ( F ) , {\displaystyle 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 ∘ {\displaystyle \circ } denotes the node labeled by 1, × the Cartesian product and ∗ {\displaystyle *} 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 ) ) , {\displaystyle 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 can be generated using a simple stochastic process. Such random recursive trees are used as simple models for epidemics.

References

  • Analytic Combinatorics, Philippe Flajolet and Robert Sedgewick, Cambridge University Press, 2008.
  • Varieties of Increasing Trees, Francois Bergeron, Philippe Flajolet, and Bruno Salvy. In Proceedings of the 17th Colloquium on Trees in Algebra and Programming, Rennes, France, February 1992. Proceedings published in Lecture Notes in Computer Science vol. 581, J.-C. Raoult Ed., 1992, pp. 24–48.
  • Profile of random trees: correlation and width of random recursive trees and binary search trees, Michael Drmota and Hsien-Kuei Hwang, Adv. Appl. Prob., 37, 1–21, 2005.
  • Profiles of random trees: Limit theorems for random recursive trees and binary search trees, Michael Fuchs, Hsien-Kuei Hwang, Ralph Neininger., Algorithmica, 46, 367–407, 2006.
Category: