Числа Катала́на — числовая последовательность, встречающаяся во многих задачах комбинаторики. Последовательность названа в честь бельгийского математика Каталана, хотя была известна ещё Л. Эйлеру.
Первые несколько чисел Каталана: 1, 1, 2, 5, 14, 42, 132, 429, 1430 …
Определения
n-е число Каталана 
можно определить одним из следующих способов:
- Количество разбиений выпуклого (n+2)-угольника на треугольники непересекающимися диагоналями.
- Количество правильных скобочных последовательностей длины 2n, то есть таких последовательностей из n левых и n правых скобок, в которых количество открывающих скобок равно количеству закрывающих, и в любом её префиксе открывающих скобок не меньше, чем закрывающих.
- Например, для n=3 существует 5 таких последовательностей:
((())), ()(()), ()()(), (())(), (()())
- то есть
.
- Количество способов соединения 2n точек на окружности n непересекающимися хордами.
- Количество неизоморфных упорядоченных бинарных деревьев с корнем и n+1 листьями.
- Числа Каталана удовлетворяют рекуррентному соотношению:
и 
для 
- Это соотношение легко получается из того, что любая непустая правильная скобочная последовательность однозначно представима в виде w=(w1)w2, где w1, w2 — правильные скобочные последовательности.
- Производящая функция чисел Каталана равна:
- Числа Каталана можно выразить через биномиальные коэффициенты:
- Другими словами, число Каталана
равно разности центрального биномиального коэффициента и соседнего с ним в той же строке треугольника Паскаля.
- Асимптотически
Комбинаторные задачи и числах Каталана
Будем рассматривать расстановки круглых скобок. Назовем расстановку скобок правильной, если все скобки разбиты на пары, причем каждая пара состоит из открывающей и закрывающей скобок, причем закрывающая скобка расположена позднее соответствующей ей открывающей, а для любой скобки b, лежащей между открывающей скобкой a и парной ей закрывающей скобкой a’ парная скобка b’ также лежит между a и a’.
Задача 1. Сколько существует правильных расстановок n пар скобок для фиксированного натурального числа n ?
Пример. Расстановка скобок ( ( ) ( ) ) ( ) является правильной, а ( ) ) ( — неправильной, т.к. скобки, выделенные красным цветом не являются парными, у каждой из них нет пары.
Для небольших значений переменной n нетрудно посчитать ответ путем перебора: для одной пары существует одна расстановка скобок: ( ), для двух — две: ( ) ( ) и ( ( ) ), для трех — пять: ( ) ( ) ( ), ( ) ( ( ) ), ( ( ) ) ( ), ( ( ) ( ) ), ( ( ( ) ) ).
Перейдем теперь к другим задачам, на первый взгляд не похожим на первую.
Задача 2. Сколькими способами можно разбить выпуклый (n+2)–угольник на треугольники непересекающимися диагоналями?
Для этой задачи также нетрудно посчитать ответ для малых n: для треугольника (n=1) такой способ один, для четырехугольника (n=2) — два (можно выбрать любую из двух диагоналей, и она будет разбивать четырехугольник на два треугольника), для пятиугольника (n=3) — пять, для шестиугольника (n=4) — четырнадцать Все эти разбиения показаны на рис. 1.
Задача 3. У театральной кассы стоит очередь за билетами из 2n человек. Билет стоит пять рублей, а в наличии у каждого из стоящих в очереди есть ровно одна банкнота — либо пять, либо десять рублей, причем каждый из двух видов банкнот встречается ровно у n человек. У кассира в начальный момент нет пятирублевых банкнот. Каждый, стоящий в очереди, покупая билет, если дает десятирублевую банкноту, должен получить сдачу. Какова вероятность того, что на протяжении всей очереди у кассира всегда будет достаточный запас пятирублевых банкнот для сдачи, а в конце у него не останется пятирублевых купюр?
Легко видеть, что всего существует 
возможных ситуаций (ровно столько есть способов распределить среди 2n любителей театра n человек, у которых на руках десятирублевая купюра и n человек с пятирублевыми купюрами на руках). Следовательно, для решения задачи нужно посчитать, в скольких случаях у кассира на протяжении всей очереди будут иметься в достаточном количестве пятирублевые купюры, причем в последний момент они у него закончатся. Полученное число случаев нужно разделить число случаев на .
Подсчет таких случаев для малых значений числа n опять приводит нас к знакомой последовательности: при n=1 это число равно единице, при n=2 — двум, далее пяти, четырнадцати, и т.д. По ответам видно, что для этих задач прослеживается некоторая закономерность, которая связана с числами Каталана. При этом мы до сих пор не выяснили, по каким правилам вычисляются члены этой знаменитой последовательности.
Рекуррентная формула для чисел Каталана
В действительности числа Каталана C(n) определяются так: нулевое число Каталана равно единице. Число с номером n равно сумме следующих произведений: нулевого числа на (n-1)–е, первого числа на (n-2)–e, второго на (n-3)–е, …, (n-1)–го на нулевое, так чтобы сумма номеров двух перемножаемых чисел была равна n-1. Более строго это можно записать так:
Так, для малых значений n получаем:
