212
правок
Изменения
Нет описания правки
<tex dpi = 120> 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, ... </tex>
==Рекуррентная формула чисел Каталана==
<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 = 150> C_n = \frac{1}{n+1} \binom {2n} {n} </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 {2n} {n} - \binom {2n} {n-1} = \frac{1}{n+1} \binom {2n} {n} </tex>
==Примеры==
<tex dpi = 120> 42 + 14 + 2 \cdot 5 + 5 \cdot 2 + 14 + 42 = 132 </tex>
способа.Такие вычисления можно проводить и дальше.
====Доказательство====
Пусть <tex dpi = 120>t_n</tex> — число триангуляций <tex dpi = 120> (n + 2) </tex> угольника при <tex dpi = 120> n >= 1 </tex>; положим <tex dpi = 120> t_0 </tex> = 1. Рассмотрим произвольную триангуляцию и выделим треугольник, примыкающий к стороне 01 (см. рис.).
[[Файл:Каталан1.PNG]]
Пусть <tex dpi = 120>k</tex> — номер третьей вершины этого треугольника. Выделенный треугольник разбивает <tex dpi = 120>(n + 2)</tex>-угольник на <tex dpi = 120>k</tex>-угольник и <tex dpi = 120>(n-k+3)</tex>-угольник, каждый из которых триангулирован диагоналями. Перенумеруем вершины этих многоугольников против часовой стрелки так, чтобы нумерация вершин в каждом из них начиналась с 0. В результате получим пару триангуляций <tex dpi = 120>k</tex>-угольника и <tex dpi = 120>(n-k+3)</tex>-угольника. Наоборот, каждая пара триангуляций <tex dpi = 120>k</tex>-угольника и <tex dpi = 120>(n-k+3)</tex>-угольника
определяет триангуляцию исходного многоугольника. Поэтому
<tex dpi = 120>t_{n+1} = t_0 t_n + t_1 t_{n-1} + \cdot \cdot \cdot + t_n t_0 </tex>
и поскольку <tex dpi = 120>t_0</tex> = 1, последовательность чисел <tex dpi = 120>t_n</tex> совпадает с последовательностью Каталана.
===Задача расстановки скобок===
способа. Следуя такому походу, можно вычислять количество правильных скобочных последовательностей дальше.
==Рекуррентная формула чисел КаталанаСмотри также== <tex dpi = 150>C_n = \sum_{i = 0}^{n - 1} C_i C_{n - 1 - i} </texwikitex>====Доказательство====Рекуррентную формулу легко вывести из задачи о правильных скобочных последовательностях. Самой левой открывающей скобке <tex dpi = 110> l <*[http:/tex> соответствует определённая закрывающая скобка <tex dpi = 110> r </tex>, которая разбивает формулу на две части, каждая из которых в свою очередь является правильной скобочной последовательностьюneerc.ifmo. Поэтому, если мы обозначим <tex dpi = 110> i = r - l - 1 </tex>, то для любого фиксированного <tex dpi = 110> r <ru/tex> будет ровно <tex dpi = 135> C_i C_{n-1-i} <wiki/tex> способовindex. Суммируя это по всем допустимым <tex dpi php?title= 110> i </tex>%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0, мы и получаем рекуррентную зависимость на <tex dpi = 135> C_n </tex>. ===Аналитическая формула=== <tex dpi = 150> C_n = \frac{1}{n+1} \binom {n} {2n} </tex>====Доказательство====_%D0%BD%D0%B0%D0%B8%D0%B2%D0%BD%D0%B0%D1%8F_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F Двоичное дерево поиска] Эту формулу проще всего вывести из задачи о монотонных путях. Общее количество монотонных путей в решётке размером <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>. В результате получаем формулу*[http: Сместим правильный путь на 1 клетку вниз. Теперь правильный путь начинается в точке<tex dpi = 120> (0, −1) </tex>, заканчивается в точке <tex dpi = 120> (n, n − 1) </tex> и не имеет общих точек с прямой <tex dpi = 120> y = x </tex> — биссектрисой первогоквадранта. Нам нужно найти количество правильных путейneerc. Для этого мы найдем количество неправильных,и из общего числа путей вычтем количество неправильныхifmo.Мы рассматриваем пути из точки <tex fpi = 120> (0, −1) <ru/tex> в точку <tex dpi = 120> (n, n − 1) <wiki/tex>index. Длина такого пути равна 2n и он содержит nвертикальных сегментов и n горизонтальных. Количество всех таких путей равно числу способов выбрать nвертикальных сегментов из общего числа 2n сегментов, т.е. равно <tex dpi php?title= 135> \binom {n}{2n} </tex>.Рассмотрим неправильный путь и его первую точку на прямой <tex dpi = 120> y = x </tex> %D0%A2%D1%80%D0%B8%D0%B0%D0%BD%D0%B3%D1%83%D0%BB%D1%8F%D1%86%D0%B8%D1%8F_%D0%BF%D0%BE%D0%BB%D0%B8%D0%B3%D0%BE%D0%BD%D0%BE%D0%B2_(точка A%D1%83%D1%88%D0%BD%D0%B0%D1%8F_%2B_%D0%BC%D0%BE%D0%BD%D0%BE%D1%82%D0%BE%D0%BD%D0%BD%D0%B0%D1%8F). Отрезок пути от точки(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} </texwikitex>
==Источники==
<wikitex>
*[http://kvant.mccme.ru/1978/07/chisla_katalana.htm Журнал "Квант"]
*[http://desolt.ru/karimova.html Глава 5. Комбинаторика]
</wikitex>
