Разбиения выпуклого многоугольника

  • Просмотров 1518
  • Скачиваний 179
  • Размер файла 61
    Кб

“Разбиения выпуклого многоугольника” Скращук Дмитрий ( г. Кобрин) П.1. Выпуклый многоугольник с n сторонами можно разбить на треугольники диагоналями, которые пересекаются лишь в его вершинах. Вывести формулу для числа таких разбиений. Определение: назовем правильным разбиением выпуклого n-угольника на треугольники диагоналями, пересекающимися только в вершинах n-угольника. P1, P2 , … ,Pn–вершины выпуклого n-угольника, Аn- число

его правильных разбиений. Рассмотрим диагональ многоугольника PiPn.В каждом правильном разбиени P1Pn принадлежит какому-то треугольнику P1PiPn, где1<i<n. Следовательно, полагая i=2,3, … , n-1, мы получаем (n-2) группы правильных разбиений, включающие все возможные случаи. Пусть i=2 – одна группа правильных разбиений, которая всегда содержит диагональ P2Pn .Число разбиений, входящих в эту группу совпадает с числом правильных разбиений (n-1)

угольника P2P3…Pn, то есть равно Аn-1. Пусть i=3 – одна группа правильных разбиений, которая всегда содержит диагональ P3P1 и P3Pn.Следовательно, число правильных разбиений, входящих в эту группу, совпадает с числом правильных разбиений (n-2)угольника P3P4…Pn, то есть равно Аn-2. При i=4 среди треугольников разбиение непременно содержит треугольник P1P4Pn.К нему примыкают четырехугольник P1P2P3P4 и (n-3)угольник P4P5 …Pn.Число правильных разбиений

четырехугольника равно A4, число правильных разбиений (n-3) угольника равно Аn-3.Следовательно, полное число правильных разбиений, содержащихся в этой группе, равно Аn-3A4.Группы с i=4,5,6,… содержат Аn-4A5, Аn-5A6, … правильных разбиений. При i=n-2 число правильных разбиений в группе совпадает с числом правильных разбиений в группе с i=2,то есть равно Аn-1. Поскольку А1=А2=0, А3=1, A4=2 и т.к. n ³ 3, то число правильных разбиений равно: Аn= Аn-1+Аn-2+Аn-3 A4+Аn-4 A5+

… + A 5Аn-4+ A4Аn-3+ Аn-2+ Аn-1. Например: A 5= A4+ А3+ A4=5 A6= A5+ А4+ А4+ A5=14 A7= A6+ А5+ А4 *А4+А5+ A6 =42 A8= A7+ А6+А5*А4+ А4*А5+А6+ A7 =132 П.2.1. Найдем количество во всех диагоналей правильных разбиениях, которые пересекают внутри только одну диагональ. Проверяя на частных случаях, пришли к предположению, что количество диагоналей в выпуклых n-угольниках равно произведению количества разбиений на (n-3) Докажем предположение, что P1n= Аn(n-3) n-угольник можно разбить на (n-2)