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