Математика / Графы, логика

Числа Каталана: правильные скобочные последовательности

Число Каталана Cₙ считает правильные последовательности из n пар скобок одного вида. В каждом начальном фрагменте открывающих скобок должно быть не меньше закрывающих, а в полной записи их количества равны.

Опубликовано: 16 октября 2026 г.Обновлено: 16 октября 2026 г.

Формула

C_n=\frac{1}{n+1}\binom{2n}{n}

Схема Пять правильных строк из трёх пар

Все пять путей соответствуют C₃=5 и не пересекают нижнюю границу.

Обозначения

$Cₙ$: число правильных скобочных последовательностей, безразмерная величина
$n$: число пар скобок, безразмерная величина
$2n$: общая длина последовательности, безразмерная величина
$C(2n,n)$: число всех записей с равным количеством скобок, безразмерная величина

Условия применения

Используется один вид скобок и целое n≥0. Любой начальный фрагмент содержит не меньше открывающих скобок, чем закрывающих; вся строка сбалансирована. Для пустой последовательности принято C₀=1. Дополнительных ограничений на глубину вложения нет.

Ограничения

Одинаковое число открывающих и закрывающих скобок ещё не означает правильную запись. Ограничение максимальной глубины, несколько типов скобок или запрет соседних пар меняют подсчёт. Для произведения m множителей индекс равен m−1, а не m: внутренних операций всего m−1.

Подробное объяснение

Всего строк из n открывающих и n закрывающих скобок имеется C(2n,n): выбираются позиции одного вида. Однако часть строк начинается с закрывающей скобки или имеет отрицательный баланс в другом начальном фрагменте. Такие строки нужно исключить.

Сопоставим открывающей скобке шаг вверх, закрывающей — шаг вниз. Правильная строка начинается на нулевой высоте, возвращается к ней через 2n шагов и ни разу не опускается ниже. Именно это условие отличает число Каталана от обычного биномиального коэффициента.

Принцип отражения переводит неправильные пути во взаимно однозначное соответствие с путями, содержащими n+1 шаг вверх и n−1 шаг вниз: меняют направление шагов до первого достижения высоты −1. Их число C(2n,n−1). Вычитание C(2n,n)−C(2n,n−1) сокращается до C(2n,n)/(n+1).

Другой подсчёт выделяет пару, закрывающую самую первую скобку. Внутри неё и после неё остаются две независимые правильные строки. Это даёт рекурсию Cₙ=ΣCⱼCₙ₋₁₋ⱼ для j от 0 до n−1. Она служит независимой проверкой факториальной формулы.

Числа начинаются с 1, 1, 2, 5, 14, 42. Они быстро растут, но всегда целые. Деление на n+1 здесь не усреднение вероятностей: это результат точного исключения путей, нарушающих условие баланса.

Как пользоваться формулой

Определите число пар n; не подставляйте в формулу полную длину строки, которая составляет 2n символов.
Проверьте, что используется один вид скобок и нет дополнительного ограничения на глубину вложения.
Найдите C(2n,n) через сокращение факториалов, затем разделите на n+1 без промежуточного округления.
Для малого n перечислите допустимые строки или используйте рекурсию разбиения по первой паре скобок.

Историческая справка

Последовательность названа в честь Эжена Каталана, но история задачи не ограничивается одним математиком. Университетский исторический очерк MacTutor связывает её раннее изучение с Эйлером в 1751 году и альтернативным вычислением Сегнера в 1758 году; позднее Каталан исследовал связанные комбинаторные постановки. Поэтому имя последовательности не означает, что все её интерпретации впервые появились одновременно. Современный справочник NIST DLMF определяет числа через пути, не пересекающие диагональ, и приводит замкнутую формулу, рекурсии и таблицу. Скобочные слова переводятся в такие пути заменой скобок шагами. Эта связь показывает, как задачи о структуре выражений, геометрических маршрутах и рекурсивных объектах объединились в одну комбинаторную последовательность.

Историческая линия формулы

Название «числа Каталана» общепринято, однако ранняя история последовательности включает Эйлера и Сегнера. Скобочная интерпретация на странице — современная модель подсчёта; именование не следует превращать в утверждение о единственном первооткрывателе всех равносильных задач.

Пример

Найдём число правильных записей из трёх пар скобок. n=3, поэтому C₃=C(6,3)/4=20/4=5. Перечисление даёт ((())), (()()), (())(), ()(()) и ()()(). Все пять имеют нулевой итоговый баланс, а при чтении слева направо баланс ни разу не отрицателен. Например, строка )(()() тоже содержит три открывающие и три закрывающие скобки, но неверна уже на первом символе и в ответ не входит. Проверка рекурсией использует C₀=1, C₁=1, C₂=2: C₃=C₀C₂+C₁C₁+C₂C₀=2+1+2=5. Ответ безразмерен и считает строки, а не глубину их вложенности.

Частая ошибка

Не используйте C(2n,n) без деления: он включает неправильные префиксы. Не подставляйте 2n вместо n. Не требуйте строго положительного баланса: он может возвращаться к нулю до конца строки. В задаче о расстановке скобок у m множителей берите Cₘ₋₁, иначе получите сдвиг индекса.

Практика

Задачи с решением

Четыре пары

Условие. Сколько правильных скобочных последовательностей длины 8?

Решение. Длина 2n=8, значит n=4. C₄=C(8,4)/5=70/5=14.

Ответ. 14 последовательностей

Шесть множителей

Условие. Сколькими способами можно полностью расставить бинарные скобки в произведении шести множителей без изменения их порядка?

Решение. Внутренних бинарных операций 6−1=5. Ответ C₅=C(10,5)/6=252/6=42.

Ответ. 42 способа

Дополнительные источники

https://dlmf.nist.gov/26.5
https://mathshistory.st-andrews.ac.uk/Strick/catalan.pdf

Связанные формулы

Математика

Число сочетаний без повторений

$C_n^k=\binom nk=\frac{n!}{k!(n-k)!}$

Формула описывает прием «неупорядоченный выбор» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.

Математика

Рекуррентная формула чисел Фибоначчи

$F_0=0,\quad F_1=1,\quad F_n=F_{n-1}+F_{n-2}$

Формула описывает прием «рекуррентное сложение» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.

Математика

Правило произведения в комбинаторике

$N=m_1m_2\cdots m_k$

Формула описывает прием «умножение последовательных шагов» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.