Плоские деревья и числа Каталана

Cn – это число правильных расстановок n пар скобок.
Пример:
C0=1
C1=1 ( )
C2=2 (( )) ( )( )
C3=5 ((( ))) ( )( )( ) ( )(( )) (( ))( ) (( )( ))
Числа Каталана

C3 = 5
Число путей = Cn
Cn =
Пути в квадрате
((( )))
(( )( ))
(( ))( )
( )(( ))
( )( )( )

Дерево – связный граф без циклов
Двоичное дерево – это такое дерево, у каждой вершины которого не более двух потомков
Пример:
n=0, где n - количество вершин => 0 (пустое дерево)
n=1 => 1 дерево
n=2 => 2
n=3 => 5
Деревья на плоскости

(( ))( )(( ))
Взаимно однозначное
соответствие
Двоичные деревья

Посчитать количество строго двоичных деревьев с n+1 листами, при n=3
Строго двоичные деревья
Итого: количество деревьев с n+1 листами равно Cn
(( ))( )
( )( )( )
( )(( ))
((( )))
(( )( ))

Сколько существует троичных деревьев с n вершинами?
n=0 => 1 дерево (пустое)
n=1 => 1 дерево
n=2 => 3 дерева
n=3 => 12 деревьев
Троичные деревья

Сколько существует троичных деревьев с n вершинами?
n=4 => 55 деревьев
Троичные деревья

Сколько существует троичных деревьев с n вершинами?
Троичные деревья

Tn – всего троичных деревьев с n вершинами.
Троичные деревья

сn(p, r) =
Пример:
сn(2, 1) = = = сn
Теорема: Tn = сn(3, 1) =
Числа Фусса-Каталана

tn = сn(3, 1)
tn + 1 = , t0 = 1
Тn + 1 = , Т0 = 1
Доказательство теоремы

Доказательство теоремы
Тn + 1 =

Следствие : Число строго троичных деревьев с 2n+1 листьями равно сn
n=1 => 1 дерево
n=2 => 3 дерева
n=3 => 12
Строго троичные деревья