الشجرة المتكررة

في نظرية المخططات ، الشجرة المتكررة (أي الشجرة غير المرتبة) هي شجرة ذات جذر مُعَلَّم . تُعَلَّم رؤوس الشجرة المتكررة ذات الحجم n بأعداد صحيحة موجبة مختلفة 1، 2، ...، n ، حيث تكون التسميات متزايدة تمامًا بدءًا من الجذر المُعَلَّم بـ 1. الأشجار المتكررة غير مستوية ، مما يعني أن أبناء رأس معين غير مُرتبين؛ على سبيل المثال، الشجرتان المتكررتان التاليتان بحجم 3 متكافئتان: ₃ / ¹ \ ₂ = ₂ / ¹ \ ₃ .

تظهر الأشجار المتكررة أيضًا في الأدبيات تحت اسم أشجار كايلي المتزايدة .

يُعطى عدد الأشجار المتكررة ذات الحجم n بالصيغة التالية:

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

وبالتالي، فإن الدالة المولدة الأسية T ( z ) للمتتالية Tn تُعطى بالصيغة التالية _:

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

من الناحية التوافقية، يمكن تفسير الشجرة المتكررة على أنها جذر متبوع بتسلسل غير مرتب من الأشجار المتكررة. لنرمز بـ 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),}$

أين${\displaystyle \circ }$يشير إلى العقدة التي تحمل الرقم 1، و × إلى حاصل الضرب الديكارتي و${\displaystyle *}$ناتج التقسيم للكائنات المصنفة.

من خلال ترجمة الوصف الرسمي، نحصل على المعادلة التفاضلية لـ T ( z )

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

مع T (0) = 0.

توجد علاقات تقابلية بين الأشجار المتكررة ذات الحجم n والتباديل ذات الحجم n − 1.  

يمكن توليد الأشجار المتكررة باستخدام عملية عشوائية بسيطة . وتُستخدم هذه الأشجار العشوائية المتكررة كنماذج بسيطة للأوبئة.

• التوافقية التحليلية ، فيليب فلاجويه وروبرت سيدجويك، مطبعة جامعة كامبريدج، 2008.
• أنواع الأشجار المتزايدة ، فرانسوا بيرجيرون، فيليب فلاجو، وبرونو سالفي. في وقائع الندوة السابعة عشرة حول الأشجار في الجبر والبرمجة، رين، فرنسا، فبراير 1992. نُشرت الوقائع في سلسلة محاضرات في علوم الحاسوب، المجلد 581، تحرير جيه-سي راؤول، 1992، الصفحات  24-48.
• ملف تعريف الأشجار العشوائية: الارتباط وعرض الأشجار العشوائية المتكررة وأشجار البحث الثنائية ، مايكل درموتا وهسين-كوي هوانغ، 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.