Учитывая регулярный N-гон со всеми нарисованными диагоналями, сколько областей образуют диагонали?

Например, у правильного треугольника ровно 1, у квадрата ровно 4, у пятиугольника ровно 11, а у шестиугольника 24.

• оценка обратно пропорциональна количеству байтов в решении
• небольшие коэффициенты помадки могут быть добавлены к оценкам на основе их времени выполнения
• область, окружающая многоугольник, не учитывается

Mathematica 118

Несмотря на то, что существуют четко определенные процедуры для вычисления количества областей в обычном n-гоне со всеми нарисованными диагоналями , они довольно громоздки. Я подумал, что было бы забавно использовать подход к обработке изображений : если бы мы нарисовали n-gon с его диагоналями, было бы возможно подсчитать области из нарисованного изображения (точнее, из растеризованного и бинаризованного представления изображения как массив)?

Следующее создает и обрабатывает фактическое изображение многоугольника и определяет количество областей из растрового изображения.

Table[MorphologicalEulerNumber@Binarize@Rasterize@CompleteGraph[k, ImageSize->1200,EdgeStyle->Thickness[Large]],{k,3,14}]

{1, 3, 11, 24, 50, 80, 154, 220, 375, 444, 781, 952}

Это то, что можно назвать решением инженера. Он выполняет свою работу, но только в определенных условиях. (И это медленно: выполнение приведенного выше кода заняло 4,24 с.) Вышеприведенная процедура работает корректно, вплоть до 14-полного графика , показанного ниже. Я нахожу это удивительным, учитывая, что некоторые из 952 областей очень трудно увидеть, даже если изображение отображается с разрешением 1200 на 1200 пикселей.

Картинка ниже - это изображение перед растеризацией и бинаризацией.

Excel, 341 байт

Реализует формулу, приведенную на ссылке Woflram Mathworld в комментарии @ mob.

=A1*(A1^3-6*A1^2+23*A1-42)/24+1+(MOD(A1,2)=0)*(A1*(42*A1-5*A1^2-40)/48-1)-(MOD(A1,4)=0)*3*A1/4+(MOD(A1,6)=0)*A1*(310-53*A1)/12+(MOD(A1,12)=0)*49/2*A1+(MOD(A1,18)=0)*32*A1+(MOD(A1,24)=0)*19*A1-(MOD(A1,30)=0)*36*A1-(MOD(A1,42)=0)*50*A1-(MOD(A1,60)=0)*190*A1-(MOD(A1,84)=0)*78*A1-(MOD(A1,90)=0)*48*A1-(MOD(A1,120)=0)*78*A1-(MOD(A1,210)=0)*48*A1

Разгромил для ясности:

=A1*(A1^3-6*A1^2+23*A1-42)/24+1
+(MOD(A1,2)=0)  *(A1*(42*A1-5*A1^2-40)/48-1)
-(MOD(A1,4)=0)  *3*A1/4
+(MOD(A1,6)=0)  *A1*(310-53*A1)/12
+(MOD(A1,12)=0) *49/2*A1
+(MOD(A1,18)=0) *32*A1
+(MOD(A1,24)=0) *19*A1
-(MOD(A1,30)=0) *36*A1
-(MOD(A1,42)=0) *50*A1
-(MOD(A1,60)=0) *190*A1
-(MOD(A1,84)=0) *78*A1
-(MOD(A1,90)=0) *48*A1
-(MOD(A1,120)=0)*78*A1
-(MOD(A1,210)=0)*48*A1