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

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

Последовательность названа в честь бельгийского математика Эжена Шарля Каталана, хотя была известна ещё Леонарду Эйлеру.

Числа Каталана ${\displaystyle C_{n}}$ для ${\displaystyle n=0,1,2,\dots }$ образуют последовательность:

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, … (последовательность A000108 в OEIS)

Определения

n-е число Каталана ${\displaystyle C_{n}}$ можно определить несколькими эквивалентными способами, такими как^[1]:

• Количество разбиений выпуклого (n+2)-угольника на треугольники непересекающимися диагоналями.
• Количество способов соединения 2n точек на окружности n непересекающимися хордами.
• Количество правильных скобочных последовательностей длины 2n, то есть таких последовательностей из n левых и n правых скобок, в которых количество открывающих скобок равно количеству закрывающих, и в любом её префиксе открывающих скобок не меньше, чем закрывающих.
  • Например, для n = 3 существует 5 таких последовательностей:

    ((())), ()(()), ()()(), (())(), (()())

    то есть ${\displaystyle C_{3}=5}$.

• Количество кортежей ${\displaystyle (x_{1},x_{2},\ldots ,x_{n})}$ из n натуральных чисел, таких, что ${\displaystyle x_{1}=1}$ и ${\displaystyle x_{i}\leqslant x_{i-1}+1}$ при ${\displaystyle 2\leqslant i\leqslant n}$.
• Количество неизоморфных упорядоченных бинарных деревьев с корнем и n + 1 листьями.
• Количество всевозможных способов линеаризации декартова произведения 2 линейных упорядоченных множеств: из 2 и из n элементов.
• Количество путей Дика из точки(0,0) в точку (n, n).^[2]

Свойства

• Числа Каталана удовлетворяют рекуррентному соотношению:

  ${\displaystyle C_{0}=1\quad }$ и ${\displaystyle \quad C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i}}$ для ${\displaystyle n\geqslant 1}$.

Это соотношение легко получается из того, что любая непустая правильная скобочная последовательность однозначно представима в виде w = (w₁)w₂, где w₁, w₂ — правильные скобочные последовательности.

• Есть ещё одно рекуррентное соотношение:

${\displaystyle C_{0}=1\quad }$ и ${\displaystyle \quad C_{n}={\binom {2n}{n}}-\sum _{k=0}^{n-1}C_{k}{\binom {2n-2k-1}{n-k}}}$.

• Ещё одна рекуррентная формула:

${\displaystyle C_{0}=1\quad }$ и ${\displaystyle \left(n+1\right){{C}_{n}}={{4}^{n}}-{\frac {1}{2}}\sum \limits _{k=0}^{n-1}{{{4}^{n-k}}{{C}_{k}}}}$. Если положить ${\displaystyle c_{n}={\frac {C_{n}}{4^{n}}}}$, то получается удобная для вычислений рекурсия ${\displaystyle c_{0}=1}$, ${\displaystyle c_{n}={\frac {1}{n+1}}-{\frac {1}{2\left(n+1\right)}}\sum \limits _{k=0}^{n-1}{c_{k}}}$.

Отсюда следует: ${\displaystyle \sum \limits _{k=0}^{\infty }{{\frac {C_{k}}{4^{k}}}=}\sum \limits _{k=0}^{\infty }{c_{k}}=2}$.

• Также существует более простое рекуррентное соотношение:

  ${\displaystyle C_{0}=1\quad }$ и ${\displaystyle \quad C_{n}={\frac {2(2n-1)}{n+1}}C_{n-1}}$.

• Производящая функция чисел Каталана равна:

  ${\displaystyle \sum _{n=0}^{\infty }C_{n}z^{n}={\frac {1-{\sqrt {1-4z}}}{2z}}.}$

• Числа Каталана можно выразить через биномиальные коэффициенты:

  ${\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {1}{2n+1}}{2n+1 \choose n}={\binom {2n}{n}}-{\binom {2n}{n-1}}.}$

Другими словами, число Каталана ${\displaystyle C_{n}}$ равно разности центрального биномиального коэффициента и соседнего с ним в той же строке треугольника Паскаля.

• Асимптотически ${\displaystyle C_{n}\sim {\frac {4^{n}}{n^{3/2}{\sqrt {\pi }}}}.}$

См. также

• Размещение
• Сочетание
• Перестановка

Примечания

1. А. Спивак. Числа Каталана. — МЦНМО.
2. Диаграммы Юнга, пути на решётке и метод отражений Архивная копия от 24 июня 2021 на Wayback Machine М. А. Берштейн (ИТФ им. Ландау, ИППИ им. Харкевича, НМУ), Г. А. Мерзон (МЦНМО). 2014 (статья со списком литературы)

Ссылки

• С. К. Ландо. Лекции по комбинаторике. — МЦНМО, 1994.
• А. Шень. Разделы 2.6 и 2.7 // Программирование: теоремы и задачи. — M.: МЦНМО, 2017.
• Stanley, Richard P. (2013), Catalan addendum to Enumerative Combinatorics, Volume 2 (PDF)
• Weisstein, Eric W. Catalan Number (англ.) на сайте Wolfram MathWorld.