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

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

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

1 , 1 , 2 , 5 , 14 , 42 , 132 , , 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, … (последовательность в OEIS )

Определения

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

• Количество разбиений выпуклого ( n +2)-угольника на треугольники непересекающимися диагоналями .
• Количество способов соединения 2 n точек на окружности n непересекающимися хордами .
• Количество правильных скобочных последовательностей длины 2 n , то есть таких последовательностей из 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).

Свойства

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

  ${\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 }}}}.}$

См. также

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

Примечания

Ссылки

• С. К. Ландо. . — МЦНМО , 1994.
• А. Шень. Разделы 2.6 и 2.7 // . — M.: МЦНМО , 2017.
• Stanley, Richard P. (2013), (PDF)
• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .