Числа Каталана в комбинаторике¶

Числа Каталана — последовательность натуральных чисел, широко применяемая в комбинаторике для подсчёта количества различных комбинаторных структур, обладающих рекурсивной природой. Названы в честь бельгийского математика Эжена Шарля Каталана, хотя были известны ещё Леонарду Эйлеру. Обозначаются обычно как \( C_n \), где \( n \) — неотрицательное целое число.

¶Определение и формула

Числа Каталана \( C_n \) можно определить несколькими эквивалентными способами. Наиболее распространённая формула через биномиальные коэффициенты:

\[ C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)!\,n!} \]

Также часто используется рекуррентное соотношение, отражающее комбинаторную природу этих чисел:

\[ C_0 = 1, \quad C_{n+1} = \sum_{i=0}^{n} C_i \cdot C_{n-i} \]

Первые несколько чисел последовательности: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862 и так далее.

¶Комбинаторные интерпретации

Числа Каталана возникают при подсчёте множества различных объектов. Среди наиболее известных интерпретаций:

• Правильные скобочные последовательности: количество способов расставить \( n \) пар круглых скобок так, чтобы они образовывали правильную скобочную запись (например, для \( n=3 \) существует 5 таких последовательностей: ((())), (()()), (())(), ()(()), ()()()).
• Триангуляции выпуклого многоугольника: число способов разбить выпуклый \( (n+2) \)-угольник непересекающимися диагоналями на треугольники.
• Бинарные деревья: количество различных полных бинарных деревьев с \( n+1 \) листьями (или с \( n \) внутренними вершинами).
• Монотонные пути: число путей на решётке \( n \times n \) из точки (0,0) в точку (n,n), не поднимающихся выше диагонали (пути Дика).
• Разбиения на непересекающиеся хорды: количество способов соединить \( 2n \) точек на окружности \( n \) непересекающимися хордами.
• Стек-сортировка: число перестановок длины \( n \), которые можно отсортировать с помощью одного стека (избегающих перестановок).

¶История

Впервые последовательность была описана Леонардом Эйлером в XVIII веке при подсчёте числа триангуляций многоугольника. Эжен Каталан в 1838 году независимо обнаружил эти числа в связи с задачей о скобочных выражениях. Широкое распространение термин «числа Каталана» получил благодаря американскому математику Джону Риордану в середине XX века.

¶Свойства

Числа Каталана обладают рядом важных свойств:

• Асимптотика: \( C_n \sim \frac{4^n}{n^{3/2} \sqrt{\pi}} \). Это следует из формулы Стирлинга.
• Производящая функция: \( C(x) = \frac{1 - \sqrt{1-4x}}{2x} \), которая удовлетворяет функциональному уравнению \( C(x) = 1 + x \cdot C(x)^2 \).
• Чётность: \( C_n \) нечётно тогда и только тогда, когда \( n = 2^k - 1 \) для некоторого неотрицательного целого \( k \).
• Целочисленность: хотя формула содержит деление, \( n+1 \) всегда делит \( \binom{2n}{n} \), что делает числа Каталана целыми.

¶Обобщения

Существует несколько обобщений чисел Каталана:

• Числа Фусса–Каталана: обобщение вида \( \frac{1}{kn+1} \binom{(k+1)n}{n} \), возникающее при подсчёте \( k \)-арных деревьев.
• Числа Шрёдера: учитывают также диагональные шаги в решётчатых путях.
• Многочлены Каталана: обобщение на случай, когда вместо чисел используются многочлены, что позволяет учитывать дополнительные параметры (например, число листьев в дереве).

¶Применение

Числа Каталана находят применение в различных областях математики и информатики:

• Алгоритмы и структуры данных: подсчёт числа возможных бинарных деревьев поиска, анализ стековых алгоритмов, динамическое программирование.
• Комбинаторная геометрия: перечисление триангуляций и ассоциэдров.
• Теория вероятностей: числа Каталана появляются в распределении максимумов случайных блужданий (принцип отражения).
• Теоретическая физика: в моделях решёточных путей и статистической механике.
• Биоинформатика: при анализе вторичной структуры РНК, где используется подсчёт непересекающихся спариваний оснований.

¶Источники

• Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. — М.: Мир, 1998.
• Стэнли Р. Перечислительная комбинаторика. — М.: Мир, 1990.
• Риордан Дж. Введение в комбинаторный анализ. — М.: ИЛ, 1963.