212
правок
Изменения
→Примеры
<tex dpi = 150> C_n = \binom {2n} {n} - \binom {2n} {n-1} = \frac{2n!}{n!n!} - \frac{2n!}{(n-1)!(n+1)!} = \frac{2n!}{n!} (\frac{1}{n!} - \frac{1}{(n-1)! (n+1)}) = \frac{2n!}{n!n!(n+1)} = \frac{1}{n+1} \binom {2n} {n} </tex>
==ПримерыЗадача разбиения выпуклого <tex dpi = 155 > n </tex>—угольника на треугольники не пересекающимися диагоналями==
===Задача разбиения выпуклого <tex dpi = 155 > n </tex>—угольника на треугольники не пересекающимися диагоналямиДоказательство===[[Файл:Vectorpaint.png|145px|right]]
Пусть <tex dpi = 120>t_n</tex> — число триангуляций <tex dpi = 120> (n + 2) </tex> -угольника при <tex dpi = 120> n \geqslant 1 </tex>; положим <tex dpi = 120> t_0 = 1 </tex>. Пронумеруем вершины многоугольника, начиная с произвольной против часовой стрелки. Рассмотрим произвольную триангуляцию и выделим треугольник, примыкающий к стороне 01 (см. рис.).
Пусть <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 = 1</tex>, последовательность чисел <tex dpi = 120>t_n</tex> совпадает с последовательностью Каталана.
===Пример===
[[Файл:Каталан.PNG|375px|thumb|right|Разбиение выпуклого шестиугольника]]
Ответ на задачу при <tex dpi = 120> n = 3 </tex> тривиален: никаких
<tex dpi = 120> 42 + 14 + 2 \cdot 5 + 5 \cdot 2 + 14 + 42 = 132 </tex>
способа.Такие вычисления можно проводить и дальше.
==Подсчет чисел Каталана==
