Изменения
→Подвешенные помеченные деревья без порядка на детях
{{Утверждение
|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>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>
= См.также =
