Калькулятор числа Каталана

Что считает число Каталана

Несколько разных бинарных деревьев, которые подсчитывают числа Каталана

Число Каталана Cₙ считает структуры, которые строятся по одному правилу вложенности или непересечения. К ним относятся правильные скобочные последовательности из n пар, полные упорядоченные бинарные деревья с n внутренними вершинами, триангуляции выпуклого многоугольника и пути Дика. Одинаковый ответ возникает потому, что между этими объектами можно построить взаимно однозначные соответствия.

Закрытая формула использует центральный биномиальный коэффициент:

\displaystyle C_n=\frac{1}{n+1}\binom{2n}{n}=\frac{(2n)!}{n!(n+1)!}

Индекс начинается с нуля: C₀ = 1. Пустая скобочная строка, пустой путь и дерево без внутренних вершин считаются одной допустимой структурой. Такое соглашение сохраняет рекуррентные формулы без отдельной дыры в начале последовательности.

Справочник NIST DLMF приводит ту же формулу, таблицу первых значений и связь с решётчатыми путями. Калькулятор вычисляет Cₙ последовательной точной рекурсией:

\displaystyle C_{i+1}=C_i\cdot\frac{2(2i+1)}{i+2},\qquad C_0=1

На каждом шаге деление выполняется без остатка. Все промежуточные значения хранятся как BigInt, поэтому C₂₀ равно ровно 6 564 120 420, а не приближённой записи 6,56412e9.

Почему скобки, деревья и многоугольники дают один ряд

Правильная скобочная последовательность никогда не закрывает больше скобок, чем уже открыто, и к концу закрывает их все. Её можно читать как путь Дика: открывающая скобка поднимает путь на один шаг, закрывающая опускает. Условие правильности означает, что путь длиной 2n не уходит ниже начального уровня и возвращается на него в конце.

Та же вложенность превращается в полное бинарное дерево. У каждой внутренней вершины есть левое и правое поддерево, а разбиение по корню даёт сумму произведений CₖCₙ₋ₖ. Поэтому выполняется ещё одна рекурсия: Cₙ₊₁ = C₀Cₙ + C₁Cₙ₋₁ + ... + CₙC₀.

В выпуклом многоугольнике выбирают одну сторону и смотрят, к какой третьей вершине примыкает треугольник около неё. Диагонали делят оставшуюся фигуру на два независимых многоугольника. Их варианты перемножаются, а выбор третьей вершины суммирует эти произведения. Получается та же рекуррентная схема.

Как использовать Cₙ в разных задачах

🫙 Пустая структура при n = 0. Калькулятор возвращает C₀ = 1. В программе это один способ ничего не добавить, а не отсутствие способов. Нулевое значение особенно важно в динамическом программировании, потому что оно служит нейтральной базой для произведений подзадач.

🧩 Три пары скобок. При n = 3 существует C₃ = 5 правильных последовательностей: ((())), (()()), (())(), ()(()) и ()()(). Если строка начинается с закрывающей скобки или в любой точке закрытий становится больше, такой вариант не считается.

🌳 Деревья с четырьмя внутренними вершинами. Полных упорядоченных бинарных деревьев существует C₄ = 14. «Упорядоченных» означает, что левое и правое поддеревья различаются. Если поменять их местами, в общем случае получится другой вариант.

📐 Триангуляция семиугольника. Выпуклый многоугольник с n + 2 вершинами имеет Cₙ триангуляций непересекающимися диагоналями. Для семиугольника n = 5, поэтому вариантов C₅ = 42. Если многоугольник невыпуклый, это правило применять нельзя без дополнительных условий.

⛰️ Пути Дика полудлины 10. Путь содержит 10 подъёмов и 10 спусков, не опускается ниже стартовой линии и заканчивается на ней. Таких путей C₁₀ = 16 796. Этот пример переводит задачу со скобками в геометрическую форму, удобную для доказательств и визуальной проверки.

💻 Разные расстановки операций при n = 20. Для 21 объекта существует C₂₀ = 6 564 120 420 способов полностью расставить бинарные скобки, сохраняя исходный порядок объектов. Значение уже не помещается в 32-битное целое со знаком, поэтому тип данных нужно выбирать до запуска перебора.

📚 Предельный ввод n = 10 000. C₁₀₀₀₀ содержит 6 015 цифр. Перечислить столько структур невозможно, но точное количество можно получить за 10 000 целочисленных шагов. Практический вывод простой: формула считает пространство вариантов, а не обещает построить каждый вариант.

Как интерпретировать рост результата

Числа Каталана растут примерно как 4ⁿ, но делятся на поправку порядка n^3/2. Поэтому переход от C₁₀ = 16 796 к C₂₀ = 6 564 120 420 намного резче, чем обычное удвоение индекса. Даже умеренная вложенная задача быстро становится непригодной для полного перебора.

Точная асимптотическая оценка выглядит так:

\displaystyle C_n\sim\frac{4^n}{\sqrt{\pi}\,n^{3/2}}

Знак означает приближение при больших n, а не точное равенство. Оценка помогает заранее понять порядок памяти и времени, но для количества скобочных строк или деревьев нужно целое Cₙ. Калькулятор поэтому не использует число π и вычисления с плавающей точкой.

Пробелы в длинном ответе разделяют цифры на группы по десять знаков. Они облегчают визуальную сверку и не входят в копируемое значение. Счётчик под результатом показывает длину исходной целой записи. Это полезнее, чем пытаться воспринимать шеститысячезначное число как обычную величину.

Частые ошибки в задачах с числами Каталана

Первая ошибка связана с индексом. Cₙ считает скобочные строки из n пар, деревья с n внутренними вершинами и триангуляции многоугольника с n + 2 вершинами. Один и тот же геометрический объект поэтому требует сдвига индекса. Для пятиугольника берут C₃ = 5, а не C₅ = 42.

Вторая ошибка состоит в подмене ограниченной структуры произвольной перестановкой. Числа Каталана сохраняют порядок, вложенность или условие непересечения. Если нужно выбрать любые k элементов из n, используйте число сочетаний. Если требуется переставить все разные объекты, нужен факториал.

Третья ошибка появляется при преждевременном делении или округлении. В формуле Cₙ = (2n)! / (n!(n + 1)!) итог всегда целый, но отдельное вычисление факториалов создаёт огромные промежуточные значения. Пошаговая рекурсия сразу сокращает выражение и после каждого шага оставляет точный BigInt.

Вопросы о числах Каталана

Один индекс описывает несколько семейств объектов, но их размеры переводятся в n по-разному. Ответы ниже помогают выбрать индекс и не перепутать ограниченную вложенность с обычным перебором.

Чему равно C₀ и почему?

C₀ = 1. Пустая скобочная последовательность, пустой путь и дерево без внутренних вершин считаются одним допустимым объектом. Это базовое значение сохраняет рекуррентные формулы.

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

Их количество равно Cₙ. Например, для трёх пар получается C₃ = 5, а для десяти пар C₁₀ = 16 796.

Какие бинарные деревья считает Cₙ?

Cₙ считает полные упорядоченные бинарные деревья с n внутренними вершинами. У каждой внутренней вершины есть два потомка, а левое и правое поддеревья различаются.

Как найти число триангуляций многоугольника?

У выпуклого многоугольника с m вершинами число триангуляций равно Cₘ₋₂. Например, пятиугольнику соответствует C₃ = 5, семиугольнику C₅ = 42.

Что такое путь Дика?

Это путь из подъёмов и спусков, который начинается и заканчивается на одном уровне и никогда не опускается ниже старта. Путей с n подъёмами и n спусками существует Cₙ.

Почему формула с делением всегда даёт целое число?

Центральный биномиальный коэффициент делится на n + 1 в этой комбинации. Комбинаторное объяснение ещё нагляднее: формула считает конечное количество конкретных структур, поэтому результат целый.

Можно ли вычислить число Каталана для отрицательного n?

Классическая последовательность A000108 определена для неотрицательных индексов. Калькулятор принимает n от 0 до 10 000 и не смешивает её с аналитическими продолжениями формулы.

Округляется ли C₁₀₀₀₀?

Нет. Расчёт использует BigInt и возвращает все 6 015 цифр. Пробелы видны только как группировка и удаляются при копировании.

Есть что добавить?

Напишите своё мнение, комментарий или предложение.