Числа Каталана

Числа Каталана — числовая последовательность, встречающаяся в удивительном числе комбинаторных задач.

Эта последовательность названа в честь бельгийского математика Каталана (Catalan), жившего в 19 веке, хотя на самом деле она была известна ещё Эйлеру (Euler), жившему за век до Каталана.

Последовательность

Первые несколько чисел Каталана $C_n$ (начиная с нулевого):

$1,\ 1,\ 2,\ 5,\ 14,\ 42,\ 132,\ 429,\ 1430,\ \ldo[...]$

Числа Каталана встречаются в большом количестве задач комбинаторики. $n$ -ое число Каталана — это:

Количество корректных скобочных последовательностей, состоящих из $n$ открывающих и $n$ закрывающих скобок.
Количество корневых бинарных деревьев с $n+1$ листьями (вершины не пронумерованы).
Количество способов полностью разделить скобками $n+1$ множитель.
Количество триангуляций выпуклого $n+2$ -угольника (т.е. количество разбиений многоугольника непересекающимися диагоналями на треугольники).
Количество способов соединить $2n$ точек на окружности $n$ непересекающимися хордами.
Количество неизоморфных полных бинарных деревьев с $n$ внутренними вершинами (т.е. имеющими хотя бы одного сына).
Количество монотонных путей из точки $(0,0)$ в точку $(n,n)$ в квадратной решётке размером $n \times n$ , не поднимающихся над главной диагональю.
Количество перестановок длины $n$ , которые можно отсортировать стеком (можно показать, что перестановка является сортируемой стеком тогда и только тогда, когда нет таких индексов $i<j<k$ , что $a_k<a_i<a_j$ ).
Количество непрерывных разбиений множества из $n$ элементов (т.е. разбиений на непрерывные блоки).
Количество способов покрыть лесенку $1 \ldots n$ с помощью $n$ прямоугольников (имеется в виду фигура, состоящая из $n$ столбцов, $i$ -ый из которых имеет высоту $i$ ).

Вычисление

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

Рекуррентная формула

$C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k}$

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

Самой левой открывающей скобке l соответствует определённая закрывающая скобка r, которая разбивает формулу две части, каждая из которых в свою очередь является правильной скобочной последовательностью. Поэтому, если мы обозначим $k = r-l-1$ , то для любого фиксированного $r$ будет ровно $C_k C_{n-1-k}$ способов. Суммируя это по всем допустимым $k$ , мы и получаем рекуррентную зависимость на $C_n$ .

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

$C_n = \frac{1}{n+1} C_{2n}^{n}$

(здесь через $C_n^k$ обозначен, как обычно, биномиальный коэффициент).

Эту формулу проще всего вывести из задачи о монотонных путях. Общее количество монотонных путей в решётке размером $n \times n$ равно $C_{2n}^{n}$ . Теперь посчитаем количество монотонных путей, пересекающих диагональ. Рассмотрим какой-либо из таких путей, и найдём первое ребро, которое стоит выше диагонали. Отразим относительно диагонали весь путь, идущий после этого ребра. В результате получим монотонный путь в решётке $(n-1) \times (n+1)$ . Но, с другой стороны, любой монотонный путь в решётке $(n-1) \times (n+1)$ обязательно пересекает диагональ, следовательно, он получен как раз таким способом из какого-либо (причём единственного) монотонного пути, пересекающего диагональ, в решётке $n \times n$ . Монотонных путей в решётке $(n-1) \times (n+1)$ имеется $C_{2n}^{n-1}$ . В результате получаем формулу:

$C_n = C_{2n}^{n} - C_{2n}^{n-1} = \frac{1}{n+1} C[...]$