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

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

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

Числа Каталана $C_n$$C_{n}$ для $n=0,1,2,\dots <!--\; \dots \; -->$$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-е число Каталана $C_n$$C_{n}$  можно определить несколькими эквивалентными способами, такими как:

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

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

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

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

СвойстваПравить

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

  $C_0=1$$C_{0}=1\quad$  и $C_n=\underset{i=0}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{C}_i{C}_{n-<!--\; -\; -->1-<!--\; -\; -->i}$$\quad C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i}$  для $n⩾<!--\; ⩾\; -->1$$n\geqslant 1$ .

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

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

$C_0=1$$C_{0}=1\quad$  и $C_n=(\genfrac{}{}{0ex}{}{2n}{n})-<!--\; -\; -->\underset{k=0}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{C}_k(\genfrac{}{}{0ex}{}{2n-<!--\; -\; -->2k-<!--\; -\; -->1}{n-<!--\; -\; -->k})$$\quad C_{n}={\binom {2n}{n}}-\sum _{k=0}^{n-1}C_{k}{\binom {2n-2k-1}{n-k}}$ .

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

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

Отсюда следует: $\underset{k=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}\frac{C_k}{4^k}=\underset{k=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{c}_k=2$$\sum \limits _{k=0}^{\infty }{{\frac {C_{k}}{4^{k}}}=}\sum \limits _{k=0}^{\infty }{c_{k}}=2$ .

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

  $C_0=1$$C_{0}=1\quad$  и $C_n=\frac{2(2n-<!--\; -\; -->1)}{n+1}{C}_{n-<!--\; -\; -->1}$$\quad C_{n}={\frac {2(2n-1)}{n+1}}C_{n-1}$ .

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

  $\underset{n=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{C}_n{z}^n=\frac{1-<!--\; -\; -->\sqrt{1-<!--\; -\; -->4z}}{2z}.$$\sum _{n=0}^{\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}={\frac {1}{n+1}}{2n \choose n}={\frac {1}{2n+1}}{2n+1 \choose n}={\binom {2n}{n}}-{\binom {2n}{n-1}}.$ 

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

• Асимптотически $C_n\sim <!--\; \sim \; -->\frac{4^n}{n^{3/2}\sqrt{\mathrm{\pi <!--\; \pi \; -->}}}.$$C_{n}\sim {\frac {4^{n}}{n^{{3/2}}{\sqrt {\pi }}}}.$ 

См. такжеПравить

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

СсылкиПравить

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