1632
правки
Изменения
м
[[File<gallery mode="packed-hover" widths=400px heights=300px>Image:Forests.png|550px]]''Последовательность леса''[[FileImage:Rooted_Trees.png|550px]]''Последовательность корневых деревьев''</gallery>
Заметим, что в данной ситуации не получится простого соответствия, как в случае с деревьями с порядком на детях.<br>В случае порядка на детях не было нетривиальных автоморфизмов, предыдущем пункте порядок на детях однозначно задавал, как будут располагаться поддервевья.Если порядка на детях нетподдеревья, ситуация становится теперь же подсчёт оказывается сложнее:[[File:Marked_trees_no_order_example.jpg|250px|centerleft]]<br><br>
rollbackEdits.php mass rollback
{{Утверждение
|id=unmarked_bin
|statement=Число непомеченных бинарных деревьев: <tex>T_n = </tex> равно <tex>C_{n}</tex> (<tex dpi="150">n</tex>-ое [[Числа Каталана|число Каталана]]).
|proof=
Устройство бинарного дерева в терминах комбинаторных классов выражается следующим образом <tex>T = \varepsilon + z\times T\times T</tex>.<br>
:<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>-ое [[Числа Каталана|число Каталана]].
<gallery mode="packed-hover" widths=550px 400px heights=350px300px>
Image:Sequence_of_rooted_Trees.png|''Последовательность корневых деревьев''
Image:Ordered_Rooted_Trees.png|''Последовательность помеченных корневых деревьев''
Количество таких деревьев с <tex dpi="130">n</tex> вершинами образуют последовательность A000081<ref>[http://oeis.org/A000081 Number of unlabeled rooted trees with n node]</ref>.
= Помеченные деревья =
Производящая функция будет иметь вид: <tex>T(s) = s\cdot e^{T(s)}</tex><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>
= См.также =
