212
правок
Изменения
→Рекуррентная формула чисел Каталана
==Рекуррентная формула чисел Каталана==
<tex 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 = 120> n \times n </tex> равно <tex dpi = 135> C_\binom {2nn}^{n2n} </tex>. Теперь посчитаем количество монотонных путей, пересекающих диагональ. Рассмотрим какой-либо из таких путей, и найдём первое ребро, которое стоит выше диагонали. Отразим относительно диагонали весь путь, идущий после этого ребра. В результате получим монотонный путь в решётке <tex dpi = 110> (n - 1) \times (n + 1) </tex>. Но, с другой стороны, любой монотонный путь в решётке <tex dpi = 110> (n - 1) \times (n + 1) </tex> обязательно пересекает диагональ, следовательно, он получен как раз таким способом из какого-либо (причём единственного) монотонного пути, пересекающего диагональ, в решётке <tex dpi = 120> n \times n</tex>. Монотонных путей в решётке <tex dpi = 110>(n - 1) \times (n + 1)</tex> имеется <tex dpi = 135>C_{2n}^\binom {n-1} {2n} </tex>. В результате получаем формулу: <tex dpi = 150> C_n = \binom {n} {2n} - \binom {n-1} {2n} = \frac{1}{n+1} \binom {n} {2n} </tex>
==Источники==
<wikitex>
