212
правок
Изменения
→Задача разбиения выпуклого n-угольника на треугольники не пересекающимися диагоналями
==Некоторые задачи на числа Каталана==
===Задача разбиения выпуклого <tex dpi = 155 > n-угольника </tex>—угольника на треугольники не пересекающимися диагоналями===
<wikitex>
Ответ на задачу при $<tex dpi = 120> n$ = 3 </tex> тривиален: никакихдиагоналей проводить не надо. В четырёх угольнике четырёхугольнике можно провести любую из
двух диагоналей, так что способов два. В пятиугольнике — из любой вершины две
диагонали, <tex dpi = 120> 5 </tex> способов. При $<tex dpi = 120> n$ = 6 </tex> — первый не вполне очевидный ответ: <tex dpi = 120> 14 </tex> способов (см. рис.); чтобы
не запутаться, сторона BC выделена и отдельно нарисованы разрезания, в которых
к ней примыкают соответственно треугольники $BCA$, $BCF$, $BCE$ и $BCD$.
[[Файл:Каталан.PNG|400px|thumb|right|Разбиение выпуклого шестиугольника]]
Для семиугольника можно выделить одну из сторон и расклассифицировать разрезания в зависимости от того, какой треугольник к этой стороне примыкает. Имеем 5 разных случаев. В первом и последнем из них количество разбиений равно 14,
случаях при вырезании треугольника семиугольник распадается на треугольник и
пятиугольник. В третьем случае семиугольник распадается на два четырёхугольника. Поскольку каждый из них можно разбить двумя способами, получаем
варианта. Итак, семиугольник можно разбить всего
способами. Рассматривая восьмиугольник, аналогично получаем
способа.Такие вычисления можно проводить и дальше.
</wikitex>
