Drzewo rekurencyjne

W teorii grafów drzewo rekurencyjne (tj. drzewo nieuporządkowane) jest drzewem oznaczonym etykietą i ukorzenionym . Wierzchołki drzewa rekurencyjnego o rozmiarze n są oznaczone różnymi dodatnimi liczbami całkowitymi 1, 2, …, n , gdzie etykiety rosną ściśle począwszy od korzenia oznaczonego jako 1. Drzewa rekurencyjne są nieplanarne , co oznacza, że ​​dzieci danego wierzchołka nie są uporządkowane; na przykład następujące dwa drzewa rekurencyjne o rozmiarze 3 są równoważne: ₃ / ¹ \ ₂ = ₂ / ¹ \ ₃ .

Drzewa rekurencyjne pojawiają się także w literaturze pod nazwą Zwiększanie drzew Cayley.

Nieruchomości

Liczba drzew rekurencyjnych o rozmiarze n jest podana przez

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

Stąd wykładnicza funkcja tworząca T ( z ) ciągu T _n jest dana przez

${\ Displaystyle T (z) = \ suma _ {n \ geq 1} T_ {n} {\ Frac {z ^ {n}} {n!}} = \ log \ lewo ({\ Frac {1} -z}}\right).}$

Kombinatorycznie drzewo rekurencyjne można interpretować jako korzeń, po którym następuje nieuporządkowana sekwencja drzew rekurencyjnych. Niech F oznacza rodzinę drzew rekurencyjnych.

${\ Displaystyle F = \ circ + {\ Frac {1} {1!}} \ cdot \ circ \ razy F + {\ Frac {1} {2!}} \ cdot \ circ \ razy F * F + {\ Frac { 1}{3!}}\cdot \circ \times F*F*F*\cdots =\circ \times \exp(F),}$

gdzie oznacza $węzeł$ oznaczony jako 1, × iloczyn kartezjański i $dla$ oznaczonych obiektów.

Przez tłumaczenie opisu formalnego otrzymuje się równanie różniczkowe dla T ( z )

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

gdzie T (0) = 0.

Bijekcja

Istnieją bijektywne odpowiedniki między drzewami rekurencyjnymi o rozmiarze n i permutacjami o rozmiarze n - 1.

Aplikacje

Drzewa rekurencyjne można generować za pomocą prostego procesu stochastycznego. Takie losowe drzewa rekurencyjne są używane jako proste modele epidemii.

• Kombinatoryka analityczna , Philippe Flajolet i Robert Sedgewick, Cambridge University Press, 2008
• Odmiany rosnących drzew , Francois Bergeron, Philippe Flajolet i Bruno Salvy. W Proceedings of the 17th Colloquium on Trees in Algebra and Programming, Rennes, Francja, luty 1992. Materiały opublikowane w Lecture Notes in Computer Science tom. 581, J.-C. Raoult Ed., 1992, s. 24–48.
• Profil drzew losowych: korelacja i szerokość losowych drzew rekurencyjnych i drzew wyszukiwania binarnego Michael Drmota i Hsien-Kuei Hwang, Adv. Aplikacja Prawdopodobne, 37, 1-21, 2005.
• Profile drzew losowych: Twierdzenia graniczne dla losowych drzew rekurencyjnych i drzew wyszukiwania binarnego , Michael Fuchs, Hsien-Kuei Hwang, Ralph Neininger., Algorithmica, 46:3-4, 2006, 367-407, 2006.