Разбиения выпуклого многоугольникаВывести формулу для числа таких разбиений. Определение: назовем правильным разбиением выпуклого n -угольника на треугольники диагоналями, пересекающимися только в вершинах n -угольника. Рассмотрим диагональ многоугольника P i P n .В каждом правильном разбиени P 1 P n принадлежит какому-то треугольнику P 1 P i P n , где1 i n . Следовательно, полагая i =2,3, … , n -1, мы получаем ( n -2) группы правильных разбиений, включающие все возможные случаи. Пусть i =2 – одна группа правильных разбиений, которая всегда содержит диагональ P 2 P n .Число разбиений, входящих в эту группу совпадает с числом правильных разбиений ( n -1) угольника P 2 P 3 … Pn , то есть равно А n -1 . Пусть i =3 – одна группа правильных разбиений, которая всегда содержит диагональ P 3 P 1 и P 3 P n . Следовательно, число правильных разбиений, входящих в эту группу, совпадает с числом правильных разбиений ( n -2)угольника P 3 P 4 … Pn , то есть равно А n -2. При i =4 среди треугольников разбиение непременно содержит треугольник P 1 P 4 P n .К нему примыкают четырехугольник P 1 P 2 P 3 P 4 и ( n -3)угольник P 4 P 5 … 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. Поскольку А 1 =А 2 =0, А 3 =1, A 4 =2 и т.к. n ³ 3, то число правильных разбиений равно: А n= А n-1 + А n-2 + А n-3 A 4 + А n-4 A 5 + … + A 5 А n-4 + A 4 А n-3 + А n-2 + А n-1. Например: A 5 = A 4 + А 3 + A 4 =5 Проверяя на частных случаях, пришли к предположению, что количество диагоналей в выпуклых n -угольниках равно произведению количества разбиений на ( n -3) Докажем предположение, что P 1 n = А n ( n -3) Значит, в каждом правильном разбиении можно провести ( n -3) диагонали удовлетворяющих условию задачи. П.2.2. Найдем количество во всех диагоналей правильных всех разбиениях, которые пересекают внутри только две диагонали. Проверяя на частных случаях, пришли к предположению, что количество диагоналей в выпуклых n -угольниках равно произведению количества разбиений на ( n -4), где n 5 Докажем предположение, что P 2 n = ( n -4)А n , где n 5. Значит, найдется третья диагональ, которая пересекает две другие. Так как имеется ( n -4) пятиугольника, значит, существует ( n -4) дополнительные диагонали удовлетворяющих условию задачи. П.2.3. Разбиение n -угольника, в котором дополнительные диагонали пересекают главные k раз. Определение 1:Главными диагоналями выпуклого n -угольника называются диагонали, которые разбивают его на треугольники, пересекаясь при этом только в вершинах n -угольника. Замечание: их существует ( n -3). Определение 2:Дополнительными диагоналями выпуклого n -угольника называются диагонали, которые в данном разбиении пересекают главные диагонали. Замечание: их существует менее ( n -3). I . Определение k :
Выделение ведется до тех пор, пока не получится четырехугольник или треугольник ( r = 4 или r = 3 ( r – остаточный коэффициент)). Назовем каждое такое выделение циклом и введем величину, которая будет “считать” их ( d ). Для каждого d существует 2 d +1 многоугольников, первый многоугольник для данного d ,будет (2 d +1 +1)-угольником. Для первой половины (для данного d ) многоугольников r = 3, для второй - r = 4. Последним многоугольником, для которого r = 3 будет (3 2 d )-угольником. Окончательно получаем: r = 3, если n [2 d +1 +1; 3 2 d ], в противном случае r = 4. За каждый цикл, если проводить дополнительные диагонали, будет добавляться по 2 пересечения и через d циклов число пересечений достигнет максимума в полученном данным способом разбиении. Обозначим это число буквой k . Итак, за 1 цикл 2 пересечения, за 2 цикла – 4, за 3 – 6, очевидна арифметическая прогрессия с разностью 2, a 1=2 и количество членов равным d ; значит k =2+2( d -1)=2 d – только в том случае, если конечной фигурой окажется треугольник. В противном случае k =2 d +1, так как четырехугольник имеет собственную диагональ. Рассчитаем d : т.к.: d =1, n |