436
правок
Изменения
Image formatting fixed
Описание всех используемых далее комбинаторных объектов можно найти в статье [[Конструирование комбинаторных объектов и их подсчёт|"конструирование комбинаторных объектов и их подсчёт"]].
= Непомеченные [[Дерево, эквивалентные определения|деревья]] =
Решением данного уравнения будет <tex>T(s) = \frac{1 - \sqrt{1 - 4s}}{2s}</tex>.
Тогда:
:<tex dpi="150">T_{n}={Pair(T, \; 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>-ое [[Числа Каталана|число Каталана]].
}}
:<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>-ое [[Числа Каталана|число Каталана]].
== Подвешенные непомеченные деревья без порядка на детях ==
Пусть <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">T_{n}=F_{n-1}</tex>.
:<tex dpi="150">F_{n}=f_{n, n}</tex>.
:<tex dpi="150">ff_{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> вершинами образуют последовательность A000081<ref>[http://oeis.org/A000081 Number of unlabeled rooted trees with n node]</ref>.
= Помеченные деревья =
{{Определение
|definition=
'''Помеченное дерево''' порядка c <tex>n </tex> вершинами - дерево порядка c <mathtex>n</mathtex>вершинами, вершинам которого взаимно однозначно соответствуют числа от 1 до n.
}}
''Первый способ.''
: Так как между помеченными деревьями порядка c <tex>n</tex> вершинами и последовательностями длины <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex> существует биекция ([[Коды Прюфера|Код Прюфера]]), то количество помеченных деревьев совпадает с количеством последовательностей длины <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n = n^{n - 2}</tex>.
''Второй способ.''
: С помощью [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа |матрицы Кирхгофа]] для полного графа на <tex>n</tex> вершинах. Число помеченных деревьев порядка c <tex>n</tex>вершинами, очевидно, равно числу остовов в полном графе <tex>K_n</tex>, которое есть <tex>n^{n-2}</tex> по следствию теоремы Кирхгофа.
}}
В случае порядка на детях не было нетривиальных автоморфизмов, порядок на детях однозначно задавал, как будут располагаться поддервевья.
Если порядка на детях нет, ситуация становится сложнее:
[[File:Marked_trees_no_order_example.jpg|250px|centerleft]]<br><br>
В данном примере в А два представленных дерева {{---}} одинаковые, а в B {{---}} разные.<br>
Для <tex>T(s)</tex> нет однозначно выражаемой формулы. Однако, <tex>T_n</tex> можно получить, раскрыв экспоненту до <tex>n</tex>-ого члена, а именно <tex>e^{T(s)} = \sum\limits_{k = 0}^{n}\dfrac{(T(s))^k}{k!}</tex><br>Более подробное объяснение происходящего можно посмотреть в лекции<ref>Станкевич А.С. Лекции по дискретной математике // Помеченные объекты и экспоненциальные ПФ, 2020. URL: https://youtu.be/6qQQj6G8-tA?t=4391</ref>.<br><br><br><br><br>
= См.также =
*[[Конструирование комбинаторных объектов и их подсчёт]]
= Литература =
[[Категория: Дискретная математика]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Подсчёт числа объектов]]
[[Категория: Комбинаторные объекты]]
[[Категория: Свойства комбинаторных объектов]]
