MAXimal

добавлено: 11 Jun 2008 11:16
редактировано: 2 May 2009 17:24

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

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

Эта последовательность названа в честь бельгийского математика Каталана (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[...]