Изменения

<wikitextex dpi = 150>$C_n = \sum_{i = 0}^{n - 1} C_i C_{n - 1 - i}$</tex>====Доказательство====

Самой левой открывающей скобке $<tex dpi = 110> l$ </tex> соответствует определённая закрывающая скобка $<tex dpi = 110> r$</tex>, которая разбивает формулу на две части, каждая из которых в свою очередь является правильной скобочной последовательностью. Поэтому, если мы обозначим $<tex dpi = 110> i = r - l - 1$</tex>, то для любого фиксированного $<tex dpi = 110> r$ </tex> будет ровно $<tex dpi = 135> C_i C_{n-1-i}$ </tex> способов. Суммируя это по всем допустимым <tex dpi = 110> i</tex>, мы и получаем рекуррентную зависимость на $<tex dpi = 135> C_n$</tex>.

$ <tex dpi = 150> C_n = \frac{1}{n+1} C_{2n}^{n} $</tex>====Доказательство====(здесь через $<tex dpi = 135> C_n^k$ </tex> обозначен, как обычно, биномиальный коэффициент). Эту формулу проще всего вывести из задачи о монотонных путях. Общее количество монотонных путей в решётке размером $n \times n$ равно $C_{2n}^{n}$. Теперь посчитаем количество монотонных путей, пересекающих диагональ. Рассмотрим какой-либо из таких путей, и найдём первое ребро, которое стоит выше диагонали. Отразим относительно диагонали весь путь, идущий после этого ребра. В результате получим монотонный путь в решётке $(n - 1) \times (n + 1)$. Но, с другой стороны, любой монотонный путь в решётке $(n - 1) \times (n + 1)$ обязательно пересекает диагональ, следовательно, он получен как раз таким способом из какого-либо (причём единственного) монотонного пути, пересекающего диагональ, в решётке $n \times n$. Монотонных путей в решётке $(n - 1) \times (n + 1)$ имеется $C_{2n}^{n-1}$. В результате получаем формулу: $ C_n = C_{2n}^{n} - C_{2n}^{n-1} = \frac{1}{n+1} C_{2n}^{n}$</wikitex>