пермутации на Baxter

Този вид пермутации са въведени от Glen E. Baxter в контекста на математическия анализ. Пермутация на Baxter е тази, която избягва двата вида прекъснати модела 2-41-3 и 3-14-2. Числовата редица представяща брой пермутации на Baxter е представена в https://oeis.org/A001181 с рекурентната формула: (n+2)*(n+3)*a(n) = (7n^2+7n-2)*a(n-1) + 8*(n-1)*(n-2)*a(n-2). Тази формула напомня за числа на Фибоначи. Описана е и друга формула използваща изчисляване на комбинации. Броят алтернативни пермутации на Baxter с дължина 2*n е квадрат на числа на Каталан със същия индекс.

Съставете програма, чрез която се въвежда естествено число N от интервала [5..101] и се извежда съответния брой пермутации на Baxter. Програмата да използва две аналогични функции - рекурсия и итерация.

Допълнителна информация за брой пермутации на Baxter може да намерите на адреси: https://en.wikipedia.org/wiki/Baxter_permutation.

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