212
правок
Изменения
→Доказательство
Эту формулу проще всего вывести из задачи о монотонных путях. Общее количество монотонных путей в решётке размером <tex dpi = 120> n \times n </tex> равно <tex dpi = 135> \binom {n}{2n} </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> \binom {n-1} {2n} </tex>. В результате получаем формулу:
Сместим правильный путь на 1 клетку вниз. Теперь правильный путь начинается в точке
<tex dpi = 120> (0, −1) </tex>, заканчивается в точке <tex dpi = 120> (n, n − 1) </tex> и не имеет общих точек с прямой <tex dpi = 120> y = x </tex> — биссектрисой первого
квадранта. Нам нужно найти количество правильных путей. Для этого мы найдем количество неправильных,
и из общего числа путей вычтем количество неправильных.
Мы рассматриваем пути из точки <tex fpi = 120> (0, −1) </tex> в точку <tex dpi = 120> (n, n − 1) </tex>. Длина такого пути равна 2n и он содержит n
вертикальных сегментов и n горизонтальных. Количество всех таких путей равно числу способов выбрать n
вертикальных сегментов из общего числа 2n сегментов, т.е. равно <tex dpi = 135> \binom {n}{2n} </tex>.
Рассмотрим неправильный путь и его первую точку на прямой <tex dpi = 120> y = x </tex> (точка A). Отрезок пути от точки
(0, −1) до точки A заменим симметричным относительно прямой y = x. Мы получим путь длины 2n, идущий
из точки (−1, 0) в точку (n, n − 1).
Такой путь обязательно пересекает прямую y = x.
Обратно, пусть нам дан путь длины 2n из точки (−1, 0) в точку (n, n − 1) и пусть A — первая точка
этого пути, лежащая на прямой y = x. Заменив участок пути от точки (−1, 0) до точки A на симметричный
относительно прямой y = x, мы получим неправильный путь из точки (0, −1) в точку (n, n − 1). Следова-
тельно, неправильных путей из точки (0, −1) в точку (n, n − 1) столько же, сколько путей из точки (−1, 0) в
точку (n, n−1). Такой путь длины содержит n+ 1 горизонтальных и n−1 вертикальных участков. Поэтому,
количество таких путей равно C n−1 2n. Значит, количество правильных путей (т.е. число Каталана Cn) равно
<tex dpi = 150> C_n = \binom {n} {2n} - \binom {n-1} {2n} = \frac{1}{n+1} \binom {n} {2n} </tex>
