оцветяване върхове на триъгълник

Задачата за оцветяване върхове на триъгълник е начин за оцветяване на върховете на изпъкнал многоъгълник, така че да няма два съседни върха с еднакъв цвят. Тривиалният случай е брой начини за оцветяване на върховете на триъгълник с <= n цветове, като са позволени само завъртания. Редицата се представя с рекурентната формула: a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4), и/или с експлицитна:  a(n) = (n^3 + 2*n)/3.  Началните елементи в редицата са: 0, 1,4,11,24,45,76...

Друга интерпретация на стойностите е броя различно оцветени кубове, образувани чрез разрязване на куб. Друга интересна задача е свързана с оцветяване на страни и диагонали в правилен многоъгълник. При оцветяването се използват само два цвята, а разликата между броя различно оцветени отсечки е най-много 1. Търси се доказателство за съществуване на определен брой монохромни триъгълника.

Да се състави програма, чрез която се въвежда естествено число N и се извеждат съответния брой начини за оцветяване върхове на триъгълник. Програмата да използва две подобни функции - рекурсия и итерация.

Допълнително описание за оцветяване върхове на триъгълник и граф може да намерите и на следните адреси:  https://en.wikipedia.org/wiki/Graph_coloring,   https://math.stackexchange.com,  https://en.wikipedia.org/wiki/Burnside%27s_lemma, https://oeis.org/A006527.

Плътността на редицата бързо намалява с нарастване индекса на поредния елемент. Числови редици, даващи възможност за представяне на елементите с повече от една формула, са разгледани във формули в числова редица.

Разгледайте други основни типове примерни задачи, в чието решение се използват рекурсивни функции при работа с рекурентни редици. Потърсете допълнителен материал за: хроматично число, числа на Tetranacci, формули в числова редица.