Recursive trees

From Wikipedia, the free encyclopedia

This article is orphaned as few or no other articles link to it.
Please help introduce links in articles on related topics. (November 2006)

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

1 Properties
2 Bijections
3 Applications
4 References

[edit] 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\ge 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.

[edit] Bijections

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

[edit] Applications

Recursive Trees are used as simple models for epidemics.

[edit] References

This article does not cite any references or sources. (January 2007)
Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.