Русская Википедия:Числа Каталана
Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску
Числа Катала́на — числовая последовательность, встречающаяся во многих задачах комбинаторики.
Последовательность названа в честь бельгийского математика Эжена Шарля Каталана, хотя была известна ещё Леонарду Эйлеру.
Числа Каталана <math>C_n</math> для <math>n=0,1,2,\dots</math> образуют последовательность:
- 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-е число Каталана <math>C_n</math> можно определить несколькими эквивалентными способами, такими как[1]:
- Количество разбиений выпуклого (n+2)-угольника на треугольники непересекающимися диагоналями.
- Количество способов соединения 2n точек на окружности n непересекающимися хордами.
- Количество правильных скобочных последовательностей длины 2n, то есть таких последовательностей из n левых и n правых скобок, в которых количество открывающих скобок равно количеству закрывающих, и в любом её префиксе открывающих скобок не меньше, чем закрывающих.
- Например, для n = 3 существует 5 таких последовательностей:
((())), ()(()), ()()(), (())(), (()())- то есть <math>C_3=5</math>.
- Например, для n = 3 существует 5 таких последовательностей:
- Количество кортежей <math>(x_1, x_2, \ldots, x_n)</math> из n натуральных чисел, таких, что <math>x_1=1</math> и <math>x_i \leqslant x_{i-1}+1</math> при <math>2 \leqslant i \leqslant n</math>.
- Количество неизоморфных упорядоченных бинарных деревьев с корнем и n + 1 листьями.
- Количество всевозможных способов линеаризации декартова произведения 2 линейных упорядоченных множеств: из 2 и из n элементов.
- Количество путей Дика из точки(0,0) в точку (n, n).[2]
Свойства
- Числа Каталана удовлетворяют рекуррентному соотношению:
- <math>C_0 = 1 \quad</math> и <math>\quad C_n=\sum_{i=0}^{n-1}C_i C_{n-1-i}</math> для <math>n \geqslant 1</math>.
- Это соотношение легко получается из того, что любая непустая правильная скобочная последовательность однозначно представима в виде w = (w1)w2, где w1, w2 — правильные скобочные последовательности.
- Есть ещё одно рекуррентное соотношение:
- <math>C_0 = 1 \quad</math> и <math>\quad C_n = \binom{2n}{n} - \sum_{k=0}^{n-1}C_k \binom{2n-2k-1}{n-k}</math>.
- Ещё одна рекуррентная формула:
- <math>C_0 = 1 \quad</math> и <math>\left( n+1 \right){{C}_{n}}={{4}^{n}}-\frac{1}{2}\sum\limits_{k=0}^{n-1}{{{4}^{n-k}}{{C}_{k}}}</math>. Если положить <math>c_{n}=\frac{C_{n}}{4^{n}}</math>, то получается удобная для вычислений рекурсия <math>c_0=1</math>, <math>c_n=\frac{1}{n+1}-\frac{1}{2\left(n+1\right)}\sum\limits_{k=0}^{n-1}{c_k} </math>.
- Отсюда следует: <math>\sum\limits_{k=0}^{\infty }{\frac{C_k}{4^k}=}\sum\limits_{k=0}^{\infty }{c_k}=2</math>.
- Также существует более простое рекуррентное соотношение:
- <math>C_0 = 1 \quad</math> и <math>\quad C_{n}=\frac{2(2n-1)}{n+1}C_{n-1}</math>.
- Производящая функция чисел Каталана равна:
- <math>\sum_{n=0}^{\infty} C_n z^n = \frac{1-\sqrt{1-4 z}}{2z}.</math>
- Числа Каталана можно выразить через биномиальные коэффициенты:
- <math>C_n = \frac{1}{n+1}{2 n \choose n} = \frac{1}{2 n+1}{2 n+1 \choose n} = \binom{2 n}{n} - \binom{2 n}{n-1}.</math>
- Другими словами, число Каталана <math>C_n</math> равно разности центрального биномиального коэффициента и соседнего с ним в той же строке треугольника Паскаля.
- Асимптотически <math>C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}.</math>
См. также
Примечания
Ссылки
- ↑ Шаблон:Книга
- ↑ Диаграммы Юнга, пути на решётке и метод отражений М. А. Берштейн (ИТФ им. Ландау, ИППИ им. Харкевича, НМУ), Г. А. Мерзон (МЦНМО). 2014 (статья со списком литературы)
