Árbol recursivo

En teoría de grafos , un árbol recursivo (es decir, un árbol no ordenado) es un árbol etiquetado y con raíz . Los vértices de un árbol recursivo de tamaño n están etiquetados con enteros positivos distintos 1, 2, …, n , donde las etiquetas son estrictamente crecientes comenzando en la raíz etiquetada como 1. Los árboles recursivos no son planares , lo que significa que los hijos de un vértice en particular no están ordenados; por ejemplo, los siguientes dos árboles recursivos de tamaño 3 son equivalentes: ₃ / ¹ \ ₂ = ₂ / ¹ \ ₃ .

Los árboles recursivos también aparecen en la literatura bajo el nombre de árboles de Cayley crecientes .

El número de árboles recursivos de tamaño n viene dado por

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

Por lo tanto, la función generadora exponencial T ( z ) de la secuencia T _n viene dada por

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

Combinatoriamente, un árbol recursivo puede interpretarse como una raíz seguida de una secuencia no ordenada de árboles recursivos. Sea F la familia de árboles recursivos. Entonces

${\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),}$

dónde${\displaystyle \circ }$denota el nodo etiquetado por 1, × el producto cartesiano y${\displaystyle *}$el producto de partición para objetos etiquetados.

Mediante la traducción de la descripción formal se obtiene la ecuación diferencial para T ( z ).

${\displaystyle T'(z)=\exp(T(z)),}$

con T (0) = 0.

Existen correspondencias biyectivas entre árboles recursivos de tamaño n y permutaciones de tamaño n − 1.  

Los árboles recursivos se pueden generar mediante un proceso estocástico simple . Estos árboles recursivos aleatorios se utilizan como modelos simples para epidemias.

• Combinatoria analítica , Philippe Flajolet y Robert Sedgewick, Cambridge University Press, 2008.
• Variedades de árboles crecientes , Francois Bergeron, Philippe Flajolet y Bruno Salvy. En Actas del 17.º Coloquio sobre Árboles en Álgebra y Programación, Rennes, Francia, febrero de 1992. Actas publicadas en Lecture Notes in Computer Science, vol. 581, J.-C. Raoult (ed.), 1992, pp.  24-48.
• Perfil de árboles aleatorios: correlación y amplitud de árboles recursivos aleatorios y árboles de búsqueda binaria , Michael Drmota y Hsien-Kuei Hwang, Adv. Appl. Prob., 37, 1–21, 2005.
• Perfiles de árboles aleatorios: Teoremas límite para árboles recursivos aleatorios y árboles de búsqueda binaria , Michael Fuchs, Hsien-Kuei Hwang, Ralph Neininger, Algorithmica, 46, 367–407, 2006.