числа на Delannoy

Числата на Delannoy (автор Henri–Auguste Delannoy) дават броя различни пътища за преминаване в квадратна мрежа от югозападния ъгъл в североизточния ъгъл. Допустими са само единични стъпки (по възлите на мрежата) и само в посоките север, североизток или изток. Числовата редица е представена в https://oeis.org/A001850 с рекурентната формула n*a(n) = 3*(2*n-1)*a(n-1) - (n-1)*a(n-2).

Частта от възможните пътища, които не преминават над диагонала Юг-Запад: Север-Изток, се представят чрез големи числа на Schroeder.

Централните числа на Delannoy могат да се видят и в числовия триъгълник на Delannoy описан в https://oeis.org/A008288 с рекурентната формула D(n, k) = D(n, k-1) + D(n-1, k-1) + D(n-1, k), като крайните елементи D(n,0) = D(n,n) =1.

Съществува друга фигура с числа свързана с числата на Delannoy, която също е свързана с разстояние в  Манхатън (Manhattan distance) - разстоянието между два възела в квадратна мрежа се изчислява по броя страни на съставящите квадратчета. Преминаване по диагонал не е позволено.

Броят възли на n-мерната решетка от хиперкуба се дава в числовия триъгълник с числа на Delannoy, представен в https://oeis.org/A266213 с формулата: D(n, k) = D(n, k-1) + D(n-1, k-1) + D(n-1, k) за n >= 0 и D(n, 0) = 1.

Съставете програма, чрез която се въвежда естествено число N от интервала [1..31] и се извеждат последователните редове от триъгълник числа на Delannoy. Програмата да използва две аналогични функции - рекурсия и итерация.

Подробно описание за редицата числа на Delannoy може да намерите и на следните адреси: https://en.wikipedia.org/wiki/Delannoy_number, http://mathworld.wolfram.com/DelannoyNumber.html.

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