MAXimal | |
добавлено: 11 Jun 2008 11:16 Содержание [скрыть] Числа КаталанаЧисла Каталана — числовая последовательность, встречающаяся в удивительном числе комбинаторных задач. Эта последовательность названа в честь бельгийского математика Каталана (Catalan), жившего в 19 веке, хотя на самом деле она была известна ещё Эйлеру (Euler), жившему за век до Каталана. ПоследовательностьПервые несколько чисел Каталана (начиная с нулевого): Числа Каталана встречаются в большом количестве задач комбинаторики. -ое число Каталана — это:
ВычислениеИмеется две формулы для чисел Каталана: рекуррентная и аналитическая. Поскольку мы считаем, что все приведённые выше задачи эквивалентны, то для доказательства формул мы будем выбирать ту задачу, с помощью которой это сделать проще всего. Рекуррентная формулаРекуррентную формулу легко вывести из задачи о правильных скобочных последовательностях. Самой левой открывающей скобке l соответствует определённая закрывающая скобка r, которая разбивает формулу две части, каждая из которых в свою очередь является правильной скобочной последовательностью. Поэтому, если мы обозначим , то для любого фиксированного будет ровно способов. Суммируя это по всем допустимым , мы и получаем рекуррентную зависимость на . Аналитическая формула(здесь через обозначен, как обычно, биномиальный коэффициент). Эту формулу проще всего вывести из задачи о монотонных путях. Общее количество монотонных путей в решётке размером равно . Теперь посчитаем количество монотонных путей, пересекающих диагональ. Рассмотрим какой-либо из таких путей, и найдём первое ребро, которое стоит выше диагонали. Отразим относительно диагонали весь путь, идущий после этого ребра. В результате получим монотонный путь в решётке . Но, с другой стороны, любой монотонный путь в решётке обязательно пересекает диагональ, следовательно, он получен как раз таким способом из какого-либо (причём единственного) монотонного пути, пересекающего диагональ, в решётке . Монотонных путей в решётке имеется . В результате получаем формулу:
|