Рекурсивное дерево

В теории графов ( рекурсивное дерево т. е. неупорядоченное дерево) — это помеченное корневое дерево . размера $n$ рекурсивного дерева Вершины помечены разными положительными целыми числами $1, 2, \dots, n$ , причем метки строго увеличиваются, начиная с корня, отмеченного 1. Рекурсивные деревья неплоские , что означает, что дочерние элементы конкретной вершины не заказаны; например, следующие два рекурсивных дерева размера 3 эквивалентны: $3 / 1 \ 2 = 2 / 1 \ 3$ .

Рекурсивные деревья также появляются в литературе под названием Возрастающие деревья Кэли .

Характеристики

Число рекурсивных деревьев размера n определяется выражением

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

Следовательно, экспоненциальная производящая функция T ( z ) последовательности T _n определяется выражением

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

Комбинаторно рекурсивное дерево можно интерпретировать как корень, за которым следует неупорядоченная последовательность рекурсивных деревьев. Обозначим через F семейство рекурсивных деревьев. Затем

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),

где $\circ$ обозначает узел, помеченный цифрой 1, × декартово произведение и $*$ продукт раздела для помеченных объектов.

Путем перевода формального описания получаем дифференциальное уравнение для T ( z )

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

при Т (0) = 0.

Биекции

- 1 существуют биективные Между рекурсивными деревьями размера n и перестановками размера n соответствия .

Приложения

Рекурсивные деревья можно генерировать с помощью простого стохастического процесса. Такие случайные рекурсивные деревья используются в качестве простых моделей эпидемий.

Ссылки

Аналитическая комбинаторика , Филипп Флажоле и Роберт Седжвик, издательство Кембриджского университета, 2008.
Разновидности растущих деревьев , Франсуа Бержерон, Филипп Флажоле и Бруно Сальви. В материалах 17-го коллоквиума по деревьям в алгебре и программировании, Ренн, Франция, февраль 1992 г. Материалы опубликованы в Lecture Notes in Computer Science vol. 581, Ж.-К. Рауль Эд., 1992, стр. 24–48.
Профиль случайных деревьев: корреляция и ширина случайных рекурсивных деревьев и деревьев двоичного поиска , Майкл Дрмота и Сянь-Куэй Хван, Adv. Прил. Проб., 37, 1–21, 2005.
Профили случайных деревьев: предельные теоремы для случайных рекурсивных деревьев и бинарных деревьев поиска , Майкл Фукс, Сянь-Куэй Хван, Ральф Найнингер., Algorithmica, 46, 367–407, 2006.