числа на Motzkin

Числата на Motzkin (Motzkin numbers) са цели числа, представящи броя различни непресичащи хорди между n броя точки от кръг. Не е задължително всички точки едновременно да са краища на хорда. Редицата е представена в числа от редицата http://oeis.org/A001006 с рекурентна формула a(n+2) - a(n+1) = a(0)*a(n) + a(1)*a(n-1) + ... + a(n)*a(0). Числата на Motzkin могат да бъдат представени чрез биномни коефициенти или чрез числа на Каталан.

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

Подробно описание за числа на Motzkin може да намерите на следните адреси: https://en.wikipedia.org/wiki/Motzkin_number; http://mathworld.wolfram.com/MotzkinNumber.html.

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