числа на Каталан

    В много задачи по комбинаторика се среща последователност свързана с числа на Каталан (Catalan's numbers). Примерите за представяне на число на Каталан са много, част от тях са: а) разбиване на изпъкнал N-ъгълник чрез непресичащи се негови диагонали на отделни триъгълници; б) правилни последователности от скоби (отваряща и затваряща) с дължина 2N; в) брой свързвания на 2N точки, лежащи на една окръжност с N непресичащи се хорди

    Разглеждаме числата на Каталан като редица, която може да се зададе с рекурентната формула:  Cn = (2*n)!/((n+1)!*n!) при Cо = 1 ;

    Така първите числа на Каталан са: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790...

    Напишете изходен (сорс) код на програма, чрез която се въвежда естествено число N, представляващо пореден номер на елемент от числовия ред на Каталан. Чрез две аналогични функции (рекурсия и итерация) да се изчислят всички елементи до въведения номер. 

Пример: 9  Изход:  

    Триъгълникът на Каталан (Catalan's triangle)  е вид числов триъгълник, при който елементите могат да бъдат изчислени по формулата: 

    Съществува и друга рекурентна формула: C(r,k) = C(r,k-1) + C(r-1,k). Най-левият елемент от всеки ред е 1, а последните два десни елемента имат равни стойности и са съответно равни на число на Каталан.

    Напишете програма, чрез която се въвежда естествено число N, представляващо номер на ред и чрез две две аналогични функции  (рекурсия и итерация) се изчисляват и извеждат всички числа от триъгълника на Каталан до указания ред.

    Допълнителна информация за триъгълник на Каталан има на адреси: https://en.wikipedia.org/wiki/Catalan%27s_triangle; http://mathworld.wolfram.com/CatalansTriangle.html;  http://oeis.org/A009766.

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