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

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

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

Числа Каталана $C_n$ для $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, … (Шаблон:OEIS)

Определения

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

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

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

    то есть $C_3=5$.

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

Свойства

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

  $C_0=1$ и $C_n=\sum _{i=0}^{n-1}{C}_i{C}_{n-1-i}$ для $n⩾1$.

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

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

$C_0=1$ и $C_n=(\genfrac{}{}{0ex}{}{2n}{n})-\sum _{k=0}^{n-1}{C}_k(\genfrac{}{}{0ex}{}{2n-2k-1}{n-k})$.

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

$C_0=1$ и $(n+1)C_n=4^n-\frac{1}{2}\sum _{k=0}^{n-1}{4}^{n-k}{C}_k$. Если положить $c_n=\frac{C_n}{4^n}$, то получается удобная для вычислений рекурсия $c_0=1$, $c_n=\frac{1}{n+1}-\frac{1}{2(n+1)}\sum _{k=0}^{n-1}{c}_k$.

Отсюда следует: $\sum _{k=0}^{\mathrm{\infty }}\frac{C_k}{4^k}=\sum _{k=0}^{\mathrm{\infty }}{c}_k=2$.

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

  $C_0=1$ и $C_n=\frac{2(2n-1)}{n+1}{C}_{n-1}$.

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

  $\sum _{n=0}^{\mathrm{\infty }}{C}_n{z}^n=\frac{1-\sqrt{1-4z}}{2z}.$

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

  $C_n=\frac{1}{n+1}(\genfrac{}{}{0ex}{}{2n}{n})=\frac{1}{2n+1}(\genfrac{}{}{0ex}{}{2n+1}{n})=(\genfrac{}{}{0ex}{}{2n}{n})-(\genfrac{}{}{0ex}{}{2n}{n-1}).$

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

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

См. также

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

Ссылки

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Citation
• Шаблон:Mathworld