436
правок
Изменения
м
Marked bin trees cosmetics
|statement=Число помеченных бинарных деревьев с <tex>n</tex> вершинами равно <tex>T_n = n!\cdot C_n</tex>.
|proof=
Как и в [[#unmarked_bin|случае]], с непомеченными бинарными деревьями]], получаем производящую функцию для помеченных бинарных деревьев: <tex>T(s) = \frac{1 - \sqrt{1 - 4s}}{2s}</tex>.<br>
Тогда:
:<tex>T_n = n!\cdot [s\hat{}]\left(\dfrac{1 - \sqrt{1 - 4s}}{2s}\right) = n!\cdot C_n</tex>
