Числа Каталана: рекуррентность, формула и задачи с собеседований
Числа Каталана простыми словами: рекуррентность и формула через биномиальный коэффициент, Unique BSTs, скобочные последовательности, триангуляции и вычисление по модулю 10⁹+7 на Python.
Коротко
| Что | Суть |
|---|---|
| Последовательность | 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, … |
| Рекуррентность | , — DP за |
| Явная формула | — за |
| Где встречаются | Unique BSTs, правильные скобочные последовательности, триангуляции, пути Дика |
| Как узнать на интервью | Объект режется на «левую» и «правую» независимые части, ответ 1, 2, 5, 14 для малых |
| По модулю | Факториалы и обратные по простому модулю, для составного — DP за |
Главная мысль: числа Каталана — не отдельная задача, а ответ на целое семейство задач. Если умеете разглядеть рекуррентность «выбрали корень — посчитали лево и право — перемножили», половина работы сделана.
Откуда берётся рекуррентность
Начнём с задачи, которую почти наверняка встречали: LeetCode 96, Unique Binary Search Trees. Сколько различных бинарных деревьев поиска можно построить из ключей ?
Для ответ 5. Попробуем не перебирать деревья, а разрезать задачу.
Зафиксируем корень . По свойству BST в левом поддереве окажутся ключи , а в правом — . Поддеревья строятся независимо: любое левое сочетается с любым правым. Поэтому количество деревьев с корнем равно произведению
где — число BST из ключей. Важно, что ответ зависит только от количества ключей, а не от их значений: ключи дают столько же деревьев, сколько .
Суммируем по всем корням:
Это и есть рекуррентность Каталана. Если сдвинуть индекс, получится каноническая запись: .
— не формальность. Пустое поддерево — это ровно один вариант, а не ноль. Если поставить ноль, все произведения с пустой стороной обнулятся, и ответ развалится.
DP за O(n²)
def num_trees(n: int) -> int: dp = [1] + [0] * n for nodes in range(1, n + 1): for root in range(1, nodes + 1): dp[nodes] += dp[root - 1] * dp[nodes - root] return dp[n] print(num_trees(3)) # 5 print(num_trees(19)) # 1767263190
Время , память . На собеседовании это решение принимают как основное: оно выводится из структуры задачи, а не из памяти. Тот же цикл в общем виде даёт сразу всю таблицу:
def catalan_dp(n: int) -> list[int]: c = [0] * (n + 1) c[0] = 1 for m in range(1, n + 1): for i in range(m): c[m] += c[i] * c[m - 1 - i] return c print(catalan_dp(10)) # [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796]
Это частный случай ДП, где состояние — размер подзадачи, а переход — перебор точки разреза. Если хочется копнуть глубже, посмотрите динамику по отрезкам: там тот же перебор разреза, только с минимумом вместо суммы.
Формула через биномиальный коэффициент
У рекуррентности есть закрытая форма:
Запомнить её легко, а вот почему она верна, полезно понимать хотя бы на уровне идеи — на сильных собеседованиях спрашивают.
Пути по сетке и отражение
Возьмём сетку и будем идти из в шагами вправо и вверх. Всего таких путей : из шагов выбираем, какие будут вверх. Это ровно задача Unique Paths для квадрата — обычные сочетания.
Теперь запретим подниматься выше диагонали . Такие пути называются путями Дика. Если шаг вправо — это (, а шаг вверх — ), то путь Дика превращается в правильную скобочную последовательность: в любом префиксе открывающих не меньше, чем закрывающих.
Посчитаем «плохие» пути — те, что хотя бы раз задевают прямую . Возьмём первую точку касания и отразим относительно этой прямой весь хвост пути после неё: шаги вправо станут шагами вверх и наоборот. Конечная точка перейдёт в . Это отражение — биекция между плохими путями и всеми путями в , которых .
Отсюда
Последнее равенство — простая арифметика с факториалами. Приём называется принципом отражения (его обычно связывают с именем Дезире Андре), и он работает для многих задач «путь не должен пересекать черту».
Код
from math import comb def catalan(n: int) -> int: return comb(2 * n, n) // (n + 1) print([catalan(n) for n in range(11)])
[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796]
print(all(comb(2 * n, n) - comb(2 * n, n + 1) == catalan(n) for n in range(50)))
True
В Python целые числа длинные, так что `//` здесь честное: $\binom{2n}{n}$ всегда делится на $n + 1$ нацело.
### Линейная рекуррентность
Из формулы легко получить переход от $C_n$ к $C_{n+1}$:
$$
C_{n+1} = C_n \cdot \frac{2(2n + 1)}{n + 2}.
$$
Это даёт всю таблицу за $O(n)$ без вложенного цикла:
```python
def catalan_linear(n: int) -> list[int]:
c = [1] * (n + 1)
for i in range(n):
c[i + 1] = c[i] * 2 * (2 * i + 1) // (i + 2)
return c
print(catalan_linear(10))
# [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796]
Порядок операций важен: сначала умножаем, потом делим. Произведение делится на нацело, а вот само по себе — нет. Если поделить раньше, получите мусор.
Как быстро они растут
Асимптотика:
Уже при это больше шести миллиардов. Практические границы, которые стоит помнить:
| Тип | Последнее , которое влезает | Значение |
|---|---|---|
int32 (знаковый) | 19 | 1 767 263 190 |
int64 (знаковый) | 35 | 3 116 285 494 907 301 262 |
Number в JS (точно) | 30 | 3 814 986 502 092 304 |
В LeetCode 96 ограничение выбрано как раз так, чтобы ответ влез в 32-битный int. В JavaScript точность Number заканчивается на , дальше нужен BigInt:
function catalanBig(n) { let c = 1n for (let i = 0n; i < BigInt(n); i++) { c = (c * 2n * (2n * i + 1n)) / (i + 2n) } return c } console.log(catalanBig(35)) // 3116285494907301262n
Рост — ещё и аргумент в разговоре о сложности. Если задача просит перечислить все объекты Каталана (все скобочные последовательности, все деревья), то быстрее, чем за , это сделать нельзя — только выписать ответ стоит столько.
Где числа Каталана прячутся на собеседованиях
Ниже — задачи, у которых ответ или выражается через него. Во всех одна и та же схема: выбираем «опорный» элемент, он делит объект на две независимые части меньшего размера.
Unique Binary Search Trees (LeetCode 96, 95)
Разобрали выше: опорный элемент — корень. Версия II (LeetCode 95) просит не посчитать, а построить все деревья. Рекурсия та же, но вместо умножения чисел перебираются пары поддеревьев. Деревьев , так что при их уже 1430 — дальше ограничения задачи и не заходят.
Правильные скобочные последовательности
Число правильных скобочных последовательностей из пар — . Опорный элемент — первая открывающая скобка и парная ей закрывающая. Любая последовательность однозначно записывается как (A)B, где A и B — правильные последовательности, причём если в A пар, то в B — . Получаем ту же сумму произведений.
Отсюда растут две задачи:
- Valid Parentheses — проверить, что строка правильная. Это стек или счётчик баланса, к Каталану отношения не имеет, но это нижняя ступенька темы.
- Generate Parentheses (LeetCode 22) — сгенерировать все правильные последовательности. Ответов ровно . Подробный разбор с бэктрекингом и честной оценкой сложности — в статье про Generate Parentheses.
Проверить связь можно грубым перебором — это полезная привычка, когда сомневаетесь в формуле:
from itertools import product def is_balanced(s: str) -> bool: balance = 0 for ch in s: balance += 1 if ch == '(' else -1 if balance < 0: return False return balance == 0 print([sum(is_balanced(s) for s in product('()', repeat=2 * n)) for n in range(8)]) # [1, 1, 2, 5, 14, 42, 132, 429]
Триангуляции выпуклого многоугольника
Сколькими способами можно разрезать выпуклый -угольник непересекающимися диагоналями на треугольники? Ответ — : у треугольника 1 способ, у четырёхугольника 2, у пятиугольника 5.
Опорный элемент — фиксированная сторона, например . В любой триангуляции она входит ровно в один треугольник с какой-то третьей вершиной . Этот треугольник отрезает два меньших многоугольника: на вершинах и . Их триангулируем независимо.
from functools import lru_cache @lru_cache(maxsize=None) def triangulations(k: int) -> int: """Число триангуляций выпуклого k-угольника (k >= 2).""" if k <= 3: return 1 # отрезок (вырожденный случай) и треугольник return sum(triangulations(j + 1) * triangulations(k - j) for j in range(1, k - 1)) print([triangulations(k) for k in range(3, 11)]) # [1, 2, 5, 14, 42, 132, 429, 1430]
На собеседованиях чаще встречается не подсчёт, а оптимизация: Minimum Score Triangulation of Polygon (LeetCode 1039). Там нужно не сложить варианты, а выбрать лучший — та же структура разреза, но с min вместо суммы произведений. Это классическое ДП по отрезкам.
Расстановка скобок в произведении
Сколькими способами можно расставить скобки в произведении , чтобы порядок вычислений был однозначным? Ответ — . Опорный элемент — последнее умножение. Именно поэтому в задаче о цепочке матриц полный перебор безнадёжен: вариантов экспоненциально много, и спасает только ДП.
Полные бинарные деревья (LeetCode 894)
All Possible Full Binary Trees: у каждого узла 0 или 2 ребёнка, всего узлов. Для чётного ответ пустой, для нечётного деревьев . Причина: у такого дерева внутренних узлов, и если убрать листья, остаётся произвольное бинарное дерево из внутренних узлов.
Непересекающиеся рукопожатия
человек сидят за круглым столом и одновременно жмут руки парами так, чтобы руки не перекрещивались. Число способов — . Опорный элемент — партнёр человека с номером 0: он делит стол на две дуги, и на каждой должно оказаться чётное число людей. В LeetCode эта задача известна как Handshakes That Don't Cross (1259), ответ там просят по модулю .
Стековые перестановки
Числа подаются по порядку; каждое можно положить в стек, а вершину стека — в любой момент снять в выход. Сколько разных выходных перестановок возможно? . Последовательность операций push/pop — это скобочная последовательность. Отсюда же популярная задача Validate Stack Sequences (LeetCode 946): проверить, можно ли получить заданный порядок, — она решается простой симуляцией стека.
Как распознать Каталана в незнакомой задаче
- Посчитайте руками для маленьких . Если вышло 1, 1, 2, 5 или 1, 2, 5, 14 — почти наверняка Каталан. Если нет уверенности, напишите перебор и сравните до –8.
- Ищите опорный элемент. Корень, первая скобка и её пара, сторона многоугольника, последняя операция. Он делит объект на две части, суммарный размер которых на 1 меньше исходного.
- Проверьте независимость частей. Если левую и правую половину можно выбирать как угодно и они не влияют друг на друга, ответ — сумма произведений.
- Следите за сдвигом индекса. -угольник, множителей, людей — все дают , но параметр задачи каждый раз свой. Ошибиться на единицу здесь проще всего.
Если части не независимы или есть дополнительное ограничение (высота дерева, глубина скобок, запрещённые элементы), формула уже не работает, но DP по той же схеме разреза обычно остаётся правильным решением.
Вычисление по модулю
Когда ответ большой, его просят по модулю, чаще всего . Подробно про остатки и обратные элементы — в статье о модульной арифметике, здесь — то, что нужно именно для Каталана.
Почему нельзя просто поделить
from math import factorial MOD = 10**9 + 7 n = 30 wrong = (factorial(2 * n) % MOD) // ((factorial(n) ** 2 * (n + 1)) % MOD) print(wrong) # 0, а правильный ответ 475387402
После взятия остатка делимость теряется. Деление по модулю — это умножение на обратный элемент, а для простого его даёт малая теорема Ферма: . В Python это pow(a, p - 2, p), быстрое возведение в степень уже встроено.
Одно значение за O(n)
MOD = 10**9 + 7 def catalan_mod(n: int) -> int: num = den = 1 for i in range(n + 2, 2 * n + 1): num = num * i % MOD for i in range(1, n + 1): den = den * i % MOD return num * pow(den, MOD - 2, MOD) % MOD print(catalan_mod(10)) # 16796 print(catalan_mod(1000)) # 110961515
Одно возведение в степень вместо деления на каждом шаге — так быстрее и меньше мест для ошибки.
Много значений: факториалы и обратные факториалы
Если запросов много, предподсчитайте факториалы до и обратные факториалы обратным проходом. После этого каждое — несколько умножений.
MOD = 10**9 + 7 def catalan_table_mod(n: int) -> list[int]: size = 2 * n + 2 # нужны факториалы до max(2n, n + 1) fact = [1] * size for i in range(1, size): fact[i] = fact[i - 1] * i % MOD inv_fact = [1] * size inv_fact[-1] = pow(fact[-1], MOD - 2, MOD) for i in range(size - 1, 0, -1): inv_fact[i - 1] = inv_fact[i] * i % MOD # C_k = (2k)! / (k! * (k+1)!) return [ fact[2 * k] * inv_fact[k] % MOD * inv_fact[k + 1] % MOD for k in range(n + 1) ] print(catalan_table_mod(10)) # [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796]
Предподсчёт — , плюс один pow за . Это тот же приём, что и для биномиальных коэффициентов по модулю.
Составной модуль
Если модуль не простой (например, или ), обратного к может не существовать, и формула с делением ломается. Тогда честный путь — исходная рекуррентность: в ней только сложения и умножения, а они с остатками дружат всегда.
def catalan_dp_mod(n: int, mod: int) -> int: c = [1] + [0] * n for m in range(1, n + 1): s = 0 for i in range(m): s += c[i] * c[m - 1 - i] c[m] = s % mod return c[n] print(catalan_dp_mod(100, 10**9)) # 745909320
для до нескольких тысяч — нормально. Для огромных и составного модуля нужны тяжёлые приёмы (разложение модуля на простые степени, китайская теорема об остатках), на обычных собеседованиях до этого не доходит.
Отдельный крайний случай: если , факториал по модулю равен нулю и формула тоже не работает. При это недостижимо в реальных ограничениях, но для маленьких простых модулей (скажем, ) понадобится теорема Люка.
Типичные ошибки
- вместо 1. Пустое дерево, пустая скобочная последовательность — это один объект. С нулём все произведения на границах обнуляются.
- Сдвиг индекса. Для -угольника ответ , для множителей — , для узлов полного бинарного дерева — . Проверяйте на самом маленьком примере.
- Деление до умножения в линейной формуле
c * 2 * (2 * i + 1) // (i + 2). Порядок важен. - Целочисленное деление после взятия остатка. По модулю делят только через обратный элемент.
- Переполнение. В Java/C++
intпереполняется на ,long— на . В JSNumberтеряет точность после . - Формула там, где части зависимы. Если у задачи есть дополнительное ограничение, Каталан не подойдёт, а DP по разрезу — скорее всего, да.
Вопросы, которые задают на собеседовании
- «Почему DP, а не перебор?» — Перебор деревьев или скобок стоит , а для подсчёта достаточно знать количества для меньших размеров: .
- «Можно быстрее, чем ?» — Да, по формуле или линейной рекуррентности.
- «Откуда формула?» — Принцип отражения: все пути минус пути, задевающие запретную прямую.
- «А если ответ по модулю?» — Для простого модуля факториалы и обратные через Ферма, для составного — исходная рекуррентность.
- «Перечислите, а не посчитайте» — Бэктрекинг или рекурсия с мемоизацией по размеру; сложность определяется размером ответа .
Что запомнить
- Первые члены: 1, 1, 2, 5, 14, 42, 132, 429, 1430. Если видите их — это Каталан.
- Рекуррентность: выбрали опорный элемент, перемножили количества для двух независимых частей, сложили по всем вариантам.
- Формула: .
- Классические «маски»: BST из ключей, скобки из пар, триангуляции -угольника, пути Дика, непересекающиеся рукопожатия людей, стековые перестановки.
- По модулю: простой — факториалы и
pow(x, p - 2, p), составной — DP за . - Растут как : в
intпомещается до , вlong— до .