Где встречаются числа Каталана?
-Количество псп с заданным числом пар скобок
-Количество двоичных деревьев с заданным числом листьев
-Количество путей из левого нижнего угла в правый верхний в квадрате n * n, не касающихся диагонали
-Количество разбиений n-угольника на треугольники
Как считать?1) Формула n-ного числа Каталана:
2)
•Пусть у нас есть ПСП P длины 2n
•Очевидно, что она начинается с открывающейся скобки
•Значит, скажем, что P = (A)B, где А и В – тоже псп (причём А и В могут быть пустыми)
•Если длина А = 2k, то последовательность A можно составить Ck способами
•Тогда длина В = 2(n – k - 1) и В можно составить Cn-k-1 способами
•Видим формулу для дп: Cn = sum(Ck * Cn-k-1) для всех k < n
Используемые материалы:
