imported>Sigwald: двух ссылок только тут не надо

2025-12-22T11:46:00Z

двух ссылок только тут не надо

Новая страница

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

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

Числа Каталана <math>C_n</math> для <math>n=0,1,2,\dots</math> образуют последовательность:
: [[1 (число)|1]], 1, [[2 (число)|2]], [[5 (число)|5]], [[14 (число)|14]], [[42 (число)|42]], [[132 (число)|132]], [[429 (число)|429]], 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, … ({{OEIS|A000108}})

== Определения ==
''n''-е число Каталана <math>C_n</math> можно определить несколькими эквивалентными способами, такими как<ref>{{Книга|автор = А. Спивак|заглавие = Числа Каталана|ответственный = |издание = |место = МЦНМО|издательство = |год = |страницы = |страниц = |isbn = }}</ref>:

* Количество [[Задача о триангуляции многоугольника|разбиений выпуклого (''n''+2)-угольника на треугольники непересекающимися диагоналями]].
* Количество способов соединения 2''n'' точек на окружности ''n'' непересекающимися [[Хорда (геометрия)|хордами]].
* Количество [[правильная скобочная последовательность|правильных скобочных последовательностей]] длины 2''n'', то есть таких последовательностей из ''n'' левых и ''n'' правых скобок, в которых количество открывающих скобок равно количеству закрывающих, и в любом её [[префикс (информатика)|префиксе]] открывающих скобок не меньше, чем закрывающих.
** Например, для ''n'' = 3 существует 5 таких последовательностей:
**:: <code> ((())), ()(()), ()()(), (())(), (()()) </code>
**::
**:: то есть <math>C_3=5</math>.

* Количество [[Кортеж (информатика)|кортежей]] <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).<ref>[https://dev.mccme.ru/~merzon/pscache/reflection_method.pdf Диаграммы Юнга, пути на решётке и метод отражений] {{Wayback|url=https://dev.mccme.ru/~merzon/pscache/reflection_method.pdf |date=20210624212351 }} М. А. Берштейн (ИТФ им. Ландау, ИППИ им. Харкевича, НМУ), Г. А. Мерзон (МЦНМО). 2014 ''(статья со списком литературы)''</ref>

== Свойства ==
* Числа Каталана удовлетворяют [[рекурсия|рекуррентному соотношению]]:
*: <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'' = (''w''1)''w''2, где ''w''1, ''w''2 — правильные скобочные последовательности.

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

: <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>

== См. также ==
* [[Размещение]]
* [[Сочетание]]
* [[Перестановка]]

== Примечания ==
{{примечания}}

== Ссылки ==
* {{книга |автор=С. К. Ландо |ссылка=http://www.mccme.ru/ium/ancient/combs93.html |заглавие=Лекции по комбинаторике |издательство=[[МЦНМО]] |год=1994}}
* {{книга |автор=А. Шень |ссылка=https://www.mccme.ru/free-books/shen/shen-progbook.pdf |заглавие=Программирование: теоремы и задачи |издание=|место=M. |издательство=[[МЦНМО]] |страницы=|страниц=|isbn=|ответственный=|год=2017 |часть=Разделы 2.6 и 2.7 }}
* {{citation|last=Stanley|first= Richard P.|url=http://www-math.mit.edu/~rstan/ec/catadd.pdf |title=Catalan addendum to Enumerative Combinatorics, Volume 2|year=2013}}
* {{mathworld|title=Catalan Number|urlname=CatalanNumber}}

[[Категория:Целочисленные последовательности]]
[[Категория:Комбинаторика]]

Числа Каталана - История изменений

imported>Sigwald: двух ссылок только тут не надо