1. Введение: Что такое числа Каталана?

В мире математики и информатики мы часто наблюдаем красивое явление, когда несколько, казалось бы, совершенно разных задач на самом деле имеют абсолютно одинаковую внутреннюю структуру. Одним из ярких примеров являются числа Каталана.

Названная в честь бельгийского математика Эжена Шарля Каталана, эта последовательность начинается так:

Эта последовательность возникает как решение удивительно разнообразных комбинаторных задач. В этой статье мы представим четыре известных примера, связанных с числами Каталана (правильные скобочные последовательности, бинарные деревья, триангуляция многоугольника и пути Дика). Мы разберем их рекурсивную структуру, чтобы понять, почему все они сводятся к одной и той же последовательности. Кроме того, мы рассмотрим алгоритмы их вычисления с использованием динамического программирования (DP) и математический вывод через производящие функции.

2. Четыре конкретных примера чисел Каталана

Пример 1: Правильные скобочные последовательности

В программировании крайне важно убедиться, что скобки расставлены корректно. Количество «правильных скобочных последовательностей», которые можно составить, используя \(n\) пар скобок (), в точности равно числу Каталана \(C_n\).

Правильная скобочная последовательность — это такая строка, в которой при чтении слева направо количество закрывающих скобок ) ни в какой момент не превышает количество открывающих скобок (.

Давайте посмотрим на случай, когда \(n = 3\). Существует 5 правильных способов расположить 3 пары скобок. Это идеально совпадает с \(C_3 = 5\).

  graph TD
    Root["C_3 = 5"] --> P1["((()))"]
    Root --> P2["(()())"]
    Root --> P3["(())()"]
    Root --> P4["()(())"]
    Root --> P5["()()()"]

Пример 2: Структуры бинарных деревьев

Теперь рассмотрим бинарные деревья — хорошо известную структуру данных. Количество возможных форм бинарного дерева, имеющего \(n\) внутренних узлов, также равно числу Каталана \(C_n\).

Для \(n = 3\) существует 5 различных форм бинарных деревьев. Они различаются тем, прикреплены ли узлы к левому или правому поддереву.

  graph TD
    T1["Tree 1"] --> N1_1["Node"]
    N1_1 --> N1_2["Left"]
    N1_2 --> N1_3["Left"]

    T2["Tree 2"] --> N2_1["Node"]
    N2_1 --> N2_2["Left"]
    N2_2 --> N2_3["Right"]

    T3["Tree 3"] --> N3_1["Node"]
    N3_1 --> N3_2["Left"]
    N3_1 --> N3_3["Right"]

    T4["Tree 4"] --> N4_1["Node"]
    N4_1 --> N4_2["Right"]
    N4_2 --> N4_3["Left"]

    T5["Tree 5"] --> N5_1["Node"]
    N5_1 --> N5_2["Right"]
    N5_2 --> N5_3["Right"]

Пример 3: Триангуляция многоугольника

Числа Каталана также встречаются в геометрии. Количество способов разбить выпуклый \((n+2)\)-угольник на \(n\) треугольников путем проведения непересекающихся диагоналей между вершинами в точности равно \(C_n\).

Например, когда \(n = 3\), мы рассматриваем способы триангуляции пятиугольника (\(3+2=5\)). Существует ровно 5 способов провести диагонали, чтобы образовать 3 треугольника. И снова мы видим число \(C_3 = 5\).

Пример 4: Пути Дика

Числа Каталана также появляются в задачах о путях на сетке. На сетке размером \(n \times n\) рассмотрим кратчайшие пути из левого нижнего угла \((0, 0)\) в правый верхний угол \((n, n)\), перемещаясь только вправо или вверх на одну единицу за шаг. Количество таких путей, которые никогда не пересекают диагональ \(y = x\) (что означает, что они всегда удовлетворяют условию \(y \le x\)), равно \(C_n\). Они называются путями Дика.

Если обозначить движение вправо как R, а вверх как U, то условие требует, чтобы в любом префиксе пути количество U никогда не превышало количество R. Это строго эквивалентно отношению между ( и ) в правильных скобочных последовательностях.

3. Почему они одинаковы? (Скрытая структура)

Почему все эти, казалось бы, не связанные между собой задачи приводят к одной и той же последовательности Каталана? Ответ кроется в том факте, что все они имеют абсолютно одинаковую рекурсивную структуру.

Число Каталана \(C_n\) определяется следующим рекуррентным соотношением:

Давайте интуитивно поймем, как выводится это рекуррентное соотношение, на примере «правильных скобок».

Рассмотрим произвольную правильную скобочную последовательность \(S\) длины \(2n\). \(S\) должна начинаться с открывающей скобки (. Где-то в строке должна существовать ровно одна парная ей закрывающая скобка ). Сосредоточив внимание на этой конкретной паре, строку \(S\) можно однозначно разбить на следующий вид:

Здесь \(A\) и \(B\) сами по себе являются правильными скобочными последовательностями (они могут быть и пустыми строками). Предположим, что подстрока \(A\), которая находится между начальной ( и соответствующей ей ), содержит \(i\) пар скобок \((0 \le i \le n-1)\). Поскольку во всей строке \(n\) пар, а 1 пара занята внешними ( ), оставшаяся подстрока \(B\) должна содержать \((n - 1 - i)\) пар.

• Количество способов сформировать \(A\) равно \(C_i\)
• Количество способов сформировать \(B\) равно \(C_{n-1-i}\)

Следовательно, для фиксированного значения \(i\) количество возможных строк равно \(C_i \times C_{n-1-i}\). Поскольку \(i\) может принимать любое значение от \(0\) до \(n-1\), суммирование всех этих возможностей дает \(C_n\). В этом и заключается смысл рекуррентного соотношения.

  graph LR
    S["S"] --> Split["( A ) B"]
    Split --> A["A : i пар"]
    Split --> B["B : n-1-i пар"]
    A --> CountA["C_i способов"]
    B --> CountB["C_{n-1-i} способов"]

Точно такое же разбиение работает и для «Бинарных деревьев». Если мы назначим один узел корнем и выделим \(i\) узлов левому поддереву, то правое поддерево должно забрать оставшиеся \(n-1-i\) узлов. Это дает идентичное рекуррентное соотношение.

4. Математический вывод явной формулы

Числа Каталана можно выразить очень простой явной формулой (Closed-form formula), используя комбинаторные обозначения:

Как выводится эта элегантная формула? Давайте рассмотрим два основных подхода.

4.1. Доказательство с помощью принципа отражения

Мы можем доказать эту формулу с помощью путей Дика. Общее количество кратчайших путей от \((0,0)\) до \((n,n)\) равно \(\binom{2n}{n}\), потому что из \(2n\) шагов всего мы должны выбрать \(n\) шагов для движения вправо.

Из этого мы должны вычесть пути, нарушающие условие (то есть те, которые пересекают прямую \(y = x\) и касаются прямой \(y = x + 1\)). Пусть \(P\) — первая точка, в которой нарушающий условие путь касается \(y = x + 1\). Мы отражаем часть пути от точки \(P\) до конечной точки \((n,n)\) относительно прямой \(y = x + 1\). Первоначальная конечная точка \((n,n)\) отражается в новую конечную точку \((n-1, n+1)\).

Удивительно, но существует идеальное взаимно-однозначное соответствие (биекция) между «неправильными путями из \((0,0)\) в \((n,n)\)» и «ВСЕМИ путями из \((0,0)\) в \((n-1, n+1)\)». Общее количество путей из \((0,0)\) в \((n-1, n+1)\) равно \(\binom{2n}{n-1}\).

Следовательно, количество правильных путей равно:

Мы можем алгебраически упростить это:

4.2. Подход через производящие функции

Пусть производящая функция для чисел Каталана \(C(x) = \sum_{n=0}^\infty C_n x^n\). Используя рекуррентное соотношение \(C_{n} = \sum_{i=0}^{n-1} C_i C_{n-1-i}\), мы находим, что производящая функция удовлетворяет следующему уравнению:

Это можно рассматривать как квадратное уравнение относительно \(C(x)\): \(x [C(x)]^2 - C(x) + 1 = 0\). Применяя формулу корней квадратного уравнения, получаем:

Чтобы удовлетворить условию \(C(0) = 1\) при \(x \to 0\), мы должны выбрать знак минус.

Разлагая \(\sqrt{1 - 4x} = (1 - 4x)^{1/2}\) с использованием обобщенного бинома Ньютона (ряд Тейлора) и приравнивая коэффициенты, мы приходим к \(C_n = \frac{1}{n+1} \binom{2n}{n}\).

5. Алгоритмы вычисления чисел Каталана

При программном вычислении чисел Каталана используются в основном три подхода.

5.1. Простая рекурсия (Naive Recursion)

Это предполагает прямую реализацию рекуррентного соотношения. Однако из-за того, что одни и те же значения вычисляются многократно, временная сложность растет экспоненциально, что делает этот метод непригодным для больших значений \(n\).

1
2
3
4
5
6
7
8
9

def catalan_recursive(n):
    # Базовый случай
    if n <= 1:
        return 1
    
    res = 0
    for i in range(n):
        res += catalan_recursive(i) * catalan_recursive(n - 1 - i)
    return res

5.2. Динамическое программирование

Используя мемоизацию (или динамическое программирование “снизу вверх”) для сохранения вычисленных результатов в массив, мы можем уменьшить временную сложность до \(O(n^2)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def catalan_dp(n):
    # Инициализация DP-таблицы. C_0 = 1
    dp = [0] * (n + 1)
    dp[0] = 1
    
    # Вычисление на основе рекуррентного соотношения
    for i in range(1, n + 1):
        for j in range(i):
            dp[i] += dp[j] * dp[i - 1 - j]
            
    return dp[n]

# Тест
for i in range(7):
    print(f"C_{i} =", catalan_dp(i))

5.3. Явная формула

Используя формулу, мы можем вычислить значение с временной сложностью \(O(n)\), просто выполняя вычисления факториалов.

1
2
3
4
5
6
7
8
9

import math

def catalan_formula(n):
    # C_n = (2n)! / ((n+1)! * n!)
    return math.comb(2 * n, n) // (n + 1)

# Тест
for i in range(7):
    print(f"C_{i} =", catalan_formula(i))

6. Заключение

Последовательность чисел Каталана \(C_n\) — это захватывающая последовательность, которая единообразно проявляется во множестве, казалось бы, разных задач, таких как правильные скобочные последовательности, формы бинарных деревьев, триангуляция многоугольников и пути Дика. Причина, по которой эти задачи дают одинаковое количество, заключается в том, что все они воплощают общую рекурсивную структуру: «разбиение целого на две подзадачи и их объединение».

При изучении алгоритмов и структур данных понимание математической подоплеки развивает способность видеть суть проблемы. Это также служит отличным упражнением по динамическому программированию, поэтому обязательно попробуйте написать код и поэкспериментировать самостоятельно!