Числа Каталана: как их считать и где они «выскакивают» в задачах?
Несколько раз на разборах слышал «это числа Каталана». Считал правильные скобочные последовательности, триангуляции многоугольника, монотонные пути под диагональю — и всё это оказывалось одним числом. Как понять, что в задаче именно Каталан, и как его быстро вычислить по модулю?
2 ответа
Число Каталана C_n считает огромный класс объектов, которые все приводятся к «балансу»: правильные скобочные последовательности из n пар, триангуляции выпуклого (n+2)-угольника, бинарные деревья с n внутренними вершинами, монотонные пути из (0,0) в (n,n), не поднимающиеся выше диагонали, способы расставить произведение из n+1 множителей скобками. Признак: есть объект, который рекурсивно делится на левую и правую части, и сумма по точке деления даёт свёртку.
Две рабочие формулы:
- Рекуррента (свёртка): C_0 = 1, C_{n+1} = Σ_{i=0}^{n} C_i · C_{n-i}. Это ДП за O(n^2).
- Замкнутая: C_n = C(2n, n) / (n+1) = C(2n,n) − C(2n,n+1).
По модулю удобнее замкнутая через предподсчитанные факториалы:
// fact, inv_fact уже предподсчитаны, MOD = 1e9+7
long long catalan(int n) {
long long c2n_n = fact[2*n] % MOD * inv_fact[n] % MOD * inv_fact[n] % MOD;
long long inv_np1 = power(n + 1, MOD - 2, MOD);
return c2n_n * inv_np1 % MOD;
}
Замкнутая формула даёт O(1) на запрос после O(n) предподсчёта. Рекуррента-свёртка — O(n^2), но полезна, когда нужны все C_0..C_n или модуль не простой.
Полезный частный приём (метод отражения / формула Андре): число путей от (0,0) до (n,n) шагами вправо/вверх, НЕ пересекающих диагональ, = C(2n,n) − C(2n,n−1) = C_n. Та же идея «отразить плохой путь» работает в задачах о голосовании (ballot problem) и о неотрицательных частичных суммах — если видишь ограничение «префикс не должен уйти ниже нуля», думай про отражение и Каталана.