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

П.1. Выпуклый многоугольник с n сторонами можно разбить на треугольники диагоналями, которые пересекаются лишь в его вершинах. Вывести формулу для числа таких разбиений.

Определение: назовем правильным разбиением выпуклого n-угольника на треугольники диагоналями, пересекающимися только в вершинах n-угольника.

Пусть P₁ , P₂ , … ,P_n –вершины выпуклого n-угольника, А_n - число его правильных разбиений. Рассмотрим диагональ многоугольника P_i P_n .В каждом правильном разбиение P₁ P_n принадлежит какому-то треугольнику P₁ P_i P_n , где1<i<n. Следовательно, полагая i=2,3, … , n-1, мы получаем (n-2) группы правильных разбиений, включающие все возможные случаи.

Пусть i=2 – одна группа правильных разбиений, которая всегда содержит диагональ P₂ P_n .Число разбиений, входящих в эту группу совпадает с числом правильных разбиений (n-1) угольника P₂ P₃ …Pn, то есть равно А_n-1 .

Пусть i=3 – одна группа правильных разбиений, которая всегда содержит диагональ P₃ P₁ и P₃ P_{n .} Следовательно, число правильных разбиений, входящих в эту группу, совпадает с числом правильных разбиений (n-2)угольника P₃ P₄ …Pn, то есть равно А_n-2.

При i=4 среди треугольников разбиение непременно содержит треугольник P₁ P₄ P_n .К нему примыкают четырехугольник P₁ P₂ P₃ P₄ и (n-3)угольник P₄ P₅ …Pn.Число правильных разбиений четырехугольника равно A_4, число правильных разбиений (n-3) угольника равно

А_n-3. Следовательно, полное число правильных разбиений, содержащихся в этой группе, равно

А_n-3 A_4. Группы с i=4,5,6,… содержат А_n-4 A_5, А_n-5 A_6, … правильных разбиений.

При i=n-2 число правильных разбиений в группе совпадает с числом правильных разбиений в группе с i=2,то есть равно А_n-1.

Поскольку А₁ =А₂ =0, А₃ =1, A₄ =2 и т.к. n³ 3, то число правильных разбиений равно:

А _n= А _n-1 +А _n-2 +А _n-3 A₄ +А _n-4 A₅ + … + A ₅ А _n-4 + A₄ А _n-3 + А _n-2 + А _n-1.

Например:

A ₅ = A₄ + А₃ + A₄ =5

A₆ = A₅ + А₄ + А₄ + A₅ =14

A₇ = A₆ + А₅ + А_{4 *} А₄ +А₅ + A₆ =42

A₈ = A₇ + А₆ +А_5* А₄ + А_4* А₅ +А₆ + A₇ =132

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

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

Докажем предположение, что P¹ _n =А_n (n-3)

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

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

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

Докажем предположение, что P² _n =(n-4)А_{n ,} гдеn ≥ 5.

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

П.2.3. Разбиение n-угольника, в котором дополнительные диагонали пересекают главные k раз.

--> ЧИТАТЬ ПОЛНОСТЬЮ <--