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

Одна последовательность отвечает на десятки разных вопросов комбинаторики — от скобок до деревьев.

Числа Каталана — последовательность $1, 1, 2, 5, 14, 42, \dots$, считающая множество комбинаторных структур.

Сколькими способами правильно расставить $n$ пар скобок? На сколько треугольников можно разбить многоугольник? Сколько различных деревьев поиска из $n$ узлов? Удивительно, но все эти разные задачи дают один и тот же ответ — числа Каталана.

Формула чисел Каталана

$n$-е число Каталана выражается через биномиальный коэффициент:

$$C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!\,n!}.$$

Есть и рекуррентная формула, удобная для понимания: $C_{n+1} = \sum_{i=0}^{n} C_i \, C_{n-i}$. Например, $C_3 = 5$: ровно пять способов расставить три пары скобок — ((())), (()()), (())(), ()(()), ()()().

Считаем числа Каталана

from math import comb

def catalan(n):
    return comb(2 * n, n) // (n + 1)

print("Числа Каталана C_0..C_7:")
print([catalan(n) for n in range(8)])

# Проверим рекуррентную формулу для C_4
c = [catalan(n) for n in range(4)]
c4 = sum(c[i] * c[3 - i] for i in range(4))
print("C_4 по рекурренте:", c4, "| по формуле:", catalan(4))

Вывод:

Числа Каталана C_0..C_7:
[1, 1, 2, 5, 14, 42, 132, 429]
C_4 по рекурренте: 14 | по формуле: 14

Как работает под капотом

Деление на $n+1$ в формуле — не случайность. Среди всех $\binom{2n}{n}$ путей по решётке ровно доля $\frac{1}{n+1}$ остаётся «правильной» (не пересекающей диагональ) — это так называемый принцип отражения. Рекуррентная формула $C_{n+1} = \sum C_i C_{n-i}$ отражает структуру скобок: первая открывающая скобка закрывается где-то в середине, разбивая выражение на внутреннюю часть (из $i$ пар) и оставшуюся (из $n-i$ пар). Перебрав все способы разбиения, складываем произведения — отсюда сумма. Целочисленное деление // здесь безопасно: $\binom{2n}{n}$ всегда делится на $n+1$ нацело.

Частые ошибки

Не забывайте множитель $\frac{1}{n+1}$ — без него получится просто центральный биномиальный коэффициент, который вдвое-втрое больше. Не путайте нумерацию: $C_0 = 1$ (пустое выражение — тоже способ). И помните, что многие задачи, на вид несвязанные, сводятся к Каталану — это сигнал поискать биекцию между ними.

Итог

Числа Каталана: $1, 1, 2, 5, 14, 42, \dots$
Формула: $C_n = \dfrac{1}{n+1}\binom{2n}{n}$.
Считают скобки, триангуляции, деревья и многое другое.
Рекуррента: $C_{n+1} = \sum_i C_i C_{n-i}$.