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

П.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) треугольника, из которых можно сложить (n-3) четырехугольника, причем каждый четырехугольник будет иметь диагональ. Но в четырехугольнике можно провести 2 диагонали, значит в

(n-3) четырехугольниках можно провести (n-3)

дополнительные диагонали. Значит, в каждом правильном разбиении можно провести (n-3) диагонали удовлетворяющих условию задачи.

   П.2.2.  Найдем количество во всех диагоналей правильных всех разбиениях, которые пересекают внутри только две диагонали.

     Проверяя на частных случаях, пришли к предположению, что количество диагоналей в выпуклых n-угольниках равно произведению количества разбиений на  (n-4), где n ≥ 5

Рекомендуем скачать другие рефераты по теме: отчет по производственной практике, образец титульный реферата.



1  2  3 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки