Числа Каталана

Материал из Algocode wiki
Версия от 10:35, 30 октября 2019; Глеб (обсуждение | вклад) (Новая страница: «Посчитаем количество правильных скобочных последовательностей (ПСП). Интуитивно понятн...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Посчитаем количество правильных скобочных последовательностей (ПСП). Интуитивно понятно, что это, но формально они определятюся так: - Пустая последовательность является ПСП - Если $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