Числа Катала́на — числовая последовательность, встречающаяся во многих задачах комбинаторики.
Последовательность названа в честь бельгийского математика Эжена Шарля Каталана, хотя была известна ещё Леонарду Эйлеру.
Числа Каталана для образуют последовательность: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, … ()
Определения n-е число Каталана можно определить несколькими эквивалентными способами, такими как:
Количество разбиений выпуклого (n+2)-угольника на треугольники непересекающимися диагоналями. Количество способов соединения 2n точек на окружности n непересекающимися хордами. Количество правильных скобочных последовательностей длины 2n, то есть таких последовательностей из n левых и n правых скобок, в которых количество открывающих скобок равно количеству закрывающих, и в любом её префиксе открывающих скобок не меньше, чем закрывающих. Например, для n = 3 существует 5 таких последовательностей: ((())), ()(()), ()()(), (())(), (()())
то есть .
Количество кортежей из n натуральных чисел, таких, что и при . Количество неизоморфных упорядоченных бинарных деревьев с корнем и n + 1 листьями. Количество всевозможных способов линеаризации декартова произведения 2 линейных упорядоченных множеств: из 2 и из n элементов. Количество путей Дика из точки(0,0) в точку (n, n).Диаграммы Юнга, пути на решётке и метод отражений М. А. Берштейн (ИТФ им. Ландау, ИППИ им. Харкевича, НМУ), Г. А. Мерзон (МЦНМО). 2014 (статья со списком литературы)
Свойства Числа Каталана удовлетворяют рекуррентному соотношению: и для . Это соотношение легко получается из того, что любая непустая правильная скобочная последовательность однозначно представима в виде w = (w1)w2, где w1, w2 — правильные скобочные последовательности.
Есть ещё одно рекуррентное соотношение:
и .
Ещё одна рекуррентная формула:
и . Если положить , то получается удобная для вычислений рекурсия , . Отсюда следует: .
Также существует более простое рекуррентное соотношение: и .
Производящая функция чисел Каталана равна:
Числа Каталана можно выразить через биномиальные коэффициенты:
Другими словами, число Каталана равно разности центрального биномиального коэффициента и соседнего с ним в той же строке треугольника Паскаля.
Асимптотически
См. также Размещение Сочетание Перестановка
Примечания
Ссылки
Категория:Целочисленные последовательности Категория:Комбинаторика