212
правок
Изменения
→Аналитическая формула
<tex dpi = 150> C_n = \frac{1}{n+1} \binom {2n} {n} </tex>
====Доказательство====
Правильной скобочной структуре из <tex dpi = 120>n</tex> открывающих и <tex dpi = 120>n</tex> закрывающих скобок мы поставим в соответствие путь в квадрате <tex dpi = 120>[0, n]×[0, n]</tex>. Путь начинается в точке <tex dpi = 120>(0,0)</tex> и заканчивается в точке <tex dpi = 120>(n, n)</tex>. Открывающей скобке мы сопоставляем горизонтальный отрезок длины 1, а закрывающей — вертикальный.
Если путь сопоставлен правильной структуре, то ни одна его точка не может лежать выше главной диагонали квадрата. Обратно, такому пути ("правильному пути") сопоставляется правильная скобочная структура.
Геометрическое представление правильных скобочных структур позволяет найти выражение для чисел Каталана.
Сместим правильный путь на 1 клетку вниз. Теперь правильный путь начинается в точке
<tex dpi = 120> (0, −1-1) </tex>, заканчивается в точке <tex dpi = 120> (n, n − -1) </tex> и не имеет общих точек с прямой <tex dpi = 120> y = x </tex> — биссектрисой первогоквадранта. Нам нужно найти количество правильных путей. Для этого мы найдем количество неправильных,и из общего числа путей вычтем количество неправильных.Мы рассматриваем пути из точки <tex fpi = 120> (0, −1-1) </tex> в точку <tex dpi = 120> (n, n − -1) </tex>. Длина такого пути равна <tex dpi = 120>2n </tex> и он содержит <tex dpi = 120>n</tex> вертикальных сегментов и <tex dpi = 120>n </tex> горизонтальных. Количество всех таких путей равно числу способов выбрать <tex dpi = 120>n</tex> вертикальных сегментов из общего числа <tex dpi = 120>2n </tex> сегментов, т.е. равно <tex dpi = 135> \binom {n2n}{2nn} </tex>. Рассмотрим неправильный путь и его первую точку на прямой <tex dpi = 120> y = x </tex> (точка A). Отрезок пути от точки<tex dpi = 120>(0, −1-1) </tex> до точки A заменим симметричным относительно прямой <tex dpi = 120>y = x</tex>. Мы получим путь длины <tex dpi = 120>2n</tex>, идущийиз точки <tex dpi = 120>(−1, 0) </tex> в точку <tex dpi = 120>(n, n − -1)</tex> (Смотри рис.).[[Файл:Каталан2.PNG|right]]Такой путь обязательно пересекает прямую <tex dpi = 120> y = x</tex>.Обратно, пусть нам дан путь длины <tex dpi = 120> 2n </tex> из точки <tex dpi = 120>(−1-1, 0) </tex> в точку <tex dpi = 120>(n, n − -1) </tex> и пусть A — первая точкаэтого пути, лежащая на прямой <tex dpi = 120>y = x</tex>. Заменив участок пути от точки <tex dpi = 120>(−1, 0) </tex> до точки A на симметричныйотносительно прямой <tex dpi = 120>y = x</tex>, мы получим неправильный путь из точки <tex dpi = 120>(0, −1) </tex> в точку <tex dpi = 120>(n, n − -1)</tex>. Следова-тельноСледовательно, неправильных путей из точки <tex dpi = 120>(0, −1-1) </tex> в точку <tex dpi = 120>(n, n − -1) </tex> столько же, сколько путей из точки <tex dpi = 120>(−1-1, 0) </tex> вточку <tex dpi = 120>(n, n−1n-1)</tex>. Такой путь длины содержит <tex dpi = 120>n+ 1 </tex> горизонтальных и n−1 <tex dpi = 120>n-1</tex> вертикальных участков. Поэтому,количество таких путей равно C n−1 <tex dpi = 135> \binom {2n}{n-1} </tex>. Значит, количество правильных путей (т.е. число Каталана Cn<tex dpi = 120>C_n</tex>) равно
<tex dpi = 150> C_n = \binom {2n} {n} - \binom {2n} {n-1} = \frac{1}{n+1} \binom {2n} {n} </tex>
