==Числа Каталана==
<wikitex>
{{Определение
</wikitex>
==Некоторые задачи на числа Каталана== ===Задача разбиения выпуклого n-угольника на треугольники не пересекающимися диагоналями===
<wikitex>
Ответ на задачу при $n$ = 3 тривиален: никаких
</wikitex>
===Задача расстановки скобок===
<wikitex>
Рассмотрим какое-нибудь арифметическое выражение и сотрём всё, кроме скобок.
==Рекуррентная формула чисел Каталана==
<wikitex>
<tex dpi = "170"wikitex> $C_n = \fracsum_{i = 0}^{(2nn -2)!1}C_i C_{n!(- 1 - i}$ Рекуррентную формулу легко вывести из задачи о правильных скобочных последовательностях. Самой левой открывающей скобке $l$ соответствует определённая закрывающая скобка $r$, которая разбивает формулу на две части, каждая из которых в свою очередь является правильной скобочной последовательностью. Поэтому, если мы обозначим $i = r - l - 1$, то для любого фиксированного $r$ будет ровно $C_i C_{n-1)!-i} $ способов. Суммируя это по всем допустимым i, мы и получаем рекуррентную зависимость на $C_n$.</texwikitex>===Аналитическая формула===<wikitex>$ C_n = \frac{1}{n+1} C_{2n}^{n} $
===Доказательство формулы===(здесь через $C_n^k$ обозначен, как обычно, биномиальный коэффициент).
При доказательстве будем использовать производящие функцииЭту формулу проще всего вывести из задачи о монотонных путях. Идея состоит Общее количество монотонных путей в томрешётке размером $n \times n$ равно $C_{2n}^{n}$. Теперь посчитаем количество монотонных путей, пересекающих диагональ. Рассмотрим какой-либо из таких путей, чтобы "запаковать"всю бесконечную последовательность и найдём первое ребро, которое стоит выше диагонали. Отразим относительно диагонали весь путь, идущий после этого ребра. В результате получим монотонный путь в одно выражение. Производящая функция для последовательности Каталана решётке $(n - 1, ) \times (n + 1)$. Но, 2с другой стороны, 5любой монотонный путь в решётке $(n - 1) \times (n + 1)$ обязательно пересекает диагональ, 14следовательно, 42он получен как раз таким способом из какого-либо (причём единственного) монотонного пути, 132пересекающего диагональ, в решётке $n \times n$.Монотонных путей в решётке $(n - 1) \times (n + 1)$ имеется $C_{2n}^{n-1}$.. - это функцияВ результате получаем формулу:
<tex dpi = "140"> f (x) $ C_n = 1 + C_{x2n} + ^{xn}^2 + 2- C_{x2n}^3 + 5{xn-1}^4 + 14= \frac{x1}^5 + 42{x}^6 n+ 132{x1}^7 + 429C_{x2n}^8 + 1430{xn}^9 + ...$</texwikitex>
При этом нас даже не интересует, для каких $x$ этот степенной ряд сходится, так как мы рассматриваем только формальный степенной ряд . Возведем его в квадрат и получим:
<tex dpi = "140"> f (x)*f (x) = </tex>
</wikitex>
