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

Определение

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

Альтернативные формулы

$C_n = \frac{1}{n+1}{2 n \choose n} = \frac{1}{2 n+1}{2 n+1 \choose n} = \binom{2 n}{n} - \binom{2 n}{n-1}$

Другими словами, число Каталана $C_n$ равно разности центрального биномиального коэффициента и соседнего с ним в той же строке треугольника Паскаля.

---

Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin