436
правок
Изменения
Marked trees added
= Помеченные деревья =
{{Теорема
|author=Кэли
Обозначим через <tex>T_n</tex> число корневых помеченных деревьев с <tex>n</tex> вершинами, т.е. число помеченных деревьев, в которых одна из вершин выделена и названа корнем.<br>
Число корневых помеченных деревьев с <tex>n</tex> вершинами в <tex>n</tex> раз больше числа помеченных деревьев с <tex>n</tex> вершинами: в качестве корня можно выбрать любую из <tex>n</tex> различных вершин.
}}
== Подвешенные помеченные деревья с порядком на детях ==
{{Утверждение
|statement=Число помеченных корневых деревьев с <tex>n</tex> вершинами с порядком на детях есть <tex>T_n = n!\cdot C_n</tex>.
|proof=
Как и в непомеченном случае, структура объекта остается неизменной:<br>
: <tex>T = U\times Seq(T)</tex><br>
Производящая функция будет иметь вид:<br>
: <tex>T(s) = s\dfrac{1}{1 - T(s)} \iff T(s) = \sum\limits_{n=1}^{\infty} \dfrac{1 - \sqrt{1 - 4s}}{2} \iff T(s) = \sum\limits_{n=1}^{\infty} \dfrac{C_nn!}{n!}s^n</tex><br>
Таким образом, число помеченных корневых деревьев с <tex>n</tex> с порядком на детях вершинами есть <tex>T_n = n!\cdot C_n</tex>
}}
== Подвешенные помеченные деревья без порядка на детях ==
{{Утверждение
|statement=Как и в непомеченном случае, структура объекта остается неизменной: <tex>T = U\times Set(T)</tex>.<br>
Производящая функция будет иметь вид: <tex>T(s) = s\cdot e^{T(s)}</tex>
}}
