436
правок
Изменения
м
Unmarked trees cosmetics & additions
Описание всех используемых далее комбинаторных объектов можно найти в статье [[Конструирование комбинаторных объектов и их подсчёт|"конструирование комбинаторных объектов и их подсчёт"]].
= Непомеченные [[Дерево, эквивалентные определения|деревья]] =
== Подвешенные неполные двоичные Бинарные деревья ={{Утверждение|statement=Пусть Число непомеченных бинарных деревьев: <tex dpi>T(s) ="130">T_C_{n}</tex> {{---}} количество таких деревьев с (<tex dpi="130150">n</tex> вершинами-ое [[Числа Каталана|число Каталана]]). |proof=Устройство бинарного дерева в терминах комбинаторных классов выражается следующим образом <tex dpi="130">DT =Pair(\varepsilon + z\times T, \times T)</tex> {{---}} множество всех пар из данных деревьев. Чтобы получить двоичное дерево из <tex dpi="130"br>nВ терминах производящих функций эта конструкция выглядит следующим образом </tex> вершин, достаточно взять <tex dpiT(s) ="130">1+ s{T(s)}^2</tex> вершину и подвесить к ней левого и правого сына с суммарным количеством вершин .Решением данного уравнения будет <tex dpi>T(s) ="130">n\frac{1 -\sqrt{1- 4s}}{2s}</tex>. Тогда::<tex dpi="150">T_{n}=D_{Pair(T, T)}_{n-1}=\sum\limits_{i=0}^{n-1}T_{i}T_{n-i-1}=C_{n}</tex>, где <tex dpi="150">C_{n}</tex> {{---}} <tex dpi="150">n</tex>-ое [[Числа Каталана|число Каталана]].}} {{Утверждение|statement=Производящая функция числа непомеченных полных бинарных деревьев: <tex>T(s) = \frac{1 - \sqrt{1 - 4s^2}}{2s}</tex>.|proof=Устройство бинарного дерева в терминах комбинаторных классов выражается следующим образом <tex>T = z + z\times T\times T</tex>.<br>В терминах производящих функций эта конструкция выглядит следующим образом <tex>T(s) = s + s{T(s)}^2</tex>.Решением данного уравнения будет <tex>T(s) = \frac{1 - \sqrt{1 - 4s^2}}{2s}</tex>.}}
== Подвешенные непомеченные деревьея с порядком на детях ==
:<tex dpi="150">S_{n}=\sum\limits_{i=1}^{n} T_{i} S_{n-i}=\sum\limits_{i=1}^{n} S_{i-1} S_{n-i}=\sum\limits_{i=0}^{n-1} S_{i} S_{n-i-1}=C_{n}</tex>, где <tex dpi="150">C_{n}</tex> {{---}} <tex dpi="150">n</tex>-ое [[Числа Каталана|число Каталана]].
[[File:Sequence_of_rooted_Trees.png|750px550px]][[File:Ordered_Rooted_Trees.png|700px550px]]
== Подвешенные непомеченные деревья без порядка на детях ==
Пусть <tex dpi="130">T_{n}</tex> {{---}} количество таких деревьев с <tex dpi="130">n</tex> вершинами. <tex dpi="130">F=MSet(T)</tex> {{---}} множество всех лесов из данных деревьев, так как лес можно интерпретировать как мультимножество из деревьев. <tex dpi="130">F_{n}=f_{n,n}</tex> {{---}} количество лесов с суммарным количество вершин <tex dpi="130">n</tex>. <tex dpi="130">f_{n, k}</tex> {{---}} количество таких лесов из <tex dpi="130">n</tex> вершин, что деревья в них содержат не более чем <tex dpi="130">k</tex> вершин. Чтобы получить дерево из <tex dpi="130">n</tex> вершин, достаточно взять <tex dpi="130">1</tex> вершину и подвесить к ней лес деревьев с суммарным количеством вершин <tex dpi="130">n-1</tex>. Тогда:
:<tex dpi="150">f{n,k}=\sum\limits_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{T_{k}+i-1}{i} s_{n-ik, k-1}</tex>.
Количество таких деревьев с <tex dpi="130">n</tex> вершинами образуют последовательность <tex dpi="130"> 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, 87811, 235381, 634847 \ldots</tex> A000081<ref>[http://oeis.org/A000081 Number of unlabeled rooted trees with n node]</ref> .
[[File:Forests.png|670px550px]][[File:Rooted_Trees.png|700px550px]]
= Помеченные деревья =
