числа на Davenport-Schinzel

Числата на Davenport-Schinzel (Davenport-Schinzel numbers) са естествени и образуват редица, така че няма редуваща се последователност с дължина по-голяма от определената. Като такива редици се описват редицата на естествените числа, на нечетните числа и др. Една от редиците с числа на Davenport-Schinzel е представена в http://oeis.org/A005004 с формула a(2*n) = 6 * n - 4 и a(2*n+1) = 6 * n - 5 за n > 3. Пак там се цитира дисертацията на Simon Plouffe (1992) за формула: a(n) = (z**3-z**2+z+1)*(z**2+z+1)/(1+z)/(z-1)**2. Реализираното приложение ползва формула близка до тази за изчисляване на Фибоначи.

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

Редиците на Davenport-Schinzel са дефинирани първоначално през 1965 г. от Harold Davenport и Andrzej Schinzel при анализ на линейни диференциални уравнения. Намират приложение в анализа на геометрични алгоритми. Допълнително описание за числа на Davenport-Schinzel може да намерите и на следните адреси: https://en.wikipedia.org/wiki/Davenport–Schinzel_sequence; http://mathworld.wolfram.com/Davenport-SchinzelSequence.html.

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