триъгълник на Motzkin

Триъгълникът на Motzkin съдържа естествени числа. Най-левият елемент от всеки ред е 1, най-десният елемент е поредното число от редицата на Motzkin. Тя описва броя възможни непресичащи се хорди свързващи 2 различни точки от окръжност, като не е задължително всички точки да са свързани. Рекурентната формула за триъгълника е: T(n,k) = T(n-1,k-2) + T(n-1,k-1) + T(n-1,k). Триъгълникът на Motzkin е представен в http://oeis.org/A026300.

Съществува вариант на триъгълника на Motzkin, представен чрез формулата: T(n,k) = T(n,k-1) + T(n-1,k-1) + T(n-2,k-1), за n > k >= 2, като левите елементи имат стойност 0, а десните елементи са също число от редицата на Motzkin. Триъгълникът описва брой Dyck n-пътища и е представен в  http://oeis.org/A020474. Сумата от елементите на първите редове съвпада със стойностите на началните елементи от числовата редица суми на Motzkin.

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

Допълнителна информация за числа на Motzkin можете да намерите в: https://en.wikipedia.org/wiki/Motzkin_number.

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