Числа Каталана
Посчитаем количество правильных скобочных последовательностей (ПСП). Интуитивно понятно, что это, но формально они определятюся так: - Пустая последовательность является ПСП - Если $A$ является ПСП, то $(A)$ является ПСП - Если $A$ и $B$ являются ПСП, то $AB$ является ПСП.
Теперь, посчитаем количество ПСП с $2n$ скобками. Это называется числами Каталана и обозначается $C_n$. Рассмотрим первое место, где разность количества открывающих и закрывающих скобок впервые становится равна 0 и часть ПСП до этого места обозначим $(A)$, а часть после обозначим $B$. Понятно, что $A$ и $B$ являются ПСП меньшего размера (возможно, пустыми).
Теперь $C_n$ посчитать легко, перебирая размер $A$.
$C_0=1$
$C_n=C_0C_{n-1}+C_1C_{n-2}+\ldots+C_{n-1}C_0$
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin