Rekursivt träd

I grafteorin är ett rekursivt träd (dvs. oordnat träd) ett märkt , rotat träd . Ett rekursivt träds hörn av storlek n är märkta med distinkta positiva heltal 1, 2, …, n , där etiketterna ökar strikt med början vid roten märkt 1. Rekursiva träd är icke-plana , vilket betyder att barnen i en viss vertex är inte beställda; till exempel är följande två storlek-3 rekursiva träd ekvivalenta: ₃ / ¹ \ ₂ = ₂ / ¹ \ ₃ .

Rekursiva träd förekommer också i litteraturen under namnet Increasing Cayley trees.

Egenskaper

Antalet storlek- n rekursiva träd ges av

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

ges den exponentiella genererande funktionen T ( z ) för sekvensen Tn _av

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

Kombinatoriskt kan ett rekursivt träd tolkas som en rot följt av en oordnad sekvens av rekursiva träd. Låt F beteckna familjen av rekursiva träd.

$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är $\circ$ anger noden märkt med 1, × den kartesiska produkten och $*$ partitionsprodukten för märkta objekt.

Genom att översätta den formella beskrivningen får man differentialekvationen för T ( z )

$T'(z)=\exp(T(z)),$

med T (0) = 0.

Bijektioner

Det finns bijektiva överensstämmelser mellan rekursiva träd av storlek n och permutationer av storlek n - 1.

Ansökningar

Rekursiva träd kan genereras med en enkel stokastisk process. Sådana slumpmässiga rekursiva träd används som enkla modeller för epidemier.

• Analytic Combinatorics , Philippe Flajolet och Robert Sedgewick, Cambridge University Press, 2008
• Variationer av växande träd , Francois Bergeron, Philippe Flajolet och Bruno Salvy. I Proceedings of the 17th Colloquium on Trees in Algebra and Programming, Rennes, Frankrike, februari 1992. Proceedings publicerade i Lecture Notes in Computer Science vol. 581, J.-C. Raoult Ed., 1992, s. 24–48.
• Profil av slumpmässiga träd: korrelation och bredd av slumpmässiga rekursiva träd och binära sökträd Michael Drmota och Hsien-Kuei Hwang, Adv. Appl. Prob., 37, 1-21, 2005.
• Profiler av slumpmässiga träd: Gränssatser för slumpmässiga rekursiva träd och binära sökträd, Michael Fuchs, Hsien-Kuei Hwang, Ralph Neininger., Algorithmica, 46:3-4, 2006, 367-407, 2006.