Catalan numbers

You are encouraged to solve this task according to the task description, using any language you may know.


Catalan numbers are a sequence of numbers which can be defined directly:






C

n


=


1

n
+
1






(



2
n

n


)



=



(
2
n
)
!


(
n
+
1
)
!

n
!





 for 

n
≥
0.


{\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}\qquad {\mbox{ for }}n\geq 0.}


Or recursively:






C

0


=
1


and



C

n
+
1


=

∑

i
=
0


n



C

i




C

n
−
i




for 

n
≥
0
;


{\displaystyle C_{0}=1\quad {\mbox{and}}\quad C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}\quad {\text{for }}n\geq 0;}


Or alternatively (also recursive):






C

0


=
1


and



C

n


=



2
(
2
n
−
1
)


n
+
1




C

n
−
1


,


{\displaystyle C_{0}=1\quad {\mbox{and}}\quad C_{n}={\frac {2(2n-1)}{n+1}}C_{n-1},}




Task

Implement at least one of these algorithms and print out the first 15 Catalan numbers with each.

Memoization   is not required, but may be worth the effort when using the second method above.



Related tasks

Catalan numbers/Pascal's triangle
Evaluate binomial coefficients


/*REXX program calculates and displays  Catalan numbers  using  four different methods. */
parse arg LO HI .                                /*obtain optional arguments from the CL*/
if LO=='' | LO==","  then do;  HI=15; LO=0;  end /*No args? Then use a range of 0 ──► 15*/
if HI=='' | HI==","  then      HI=LO             /*No HI?   Then use  LO for the default*/
numeric digits max(20, 5*HI)                     /*this allows gihugic Catalan numbers. */
w=length(HI)                                     /*W:  is used for aligning the output. */
call hdr 1A;  do j=LO  to HI;  say '     Catalan'     right(j, w)": "      Cat1A(j);   end
call hdr 1B;  do j=LO  to HI;  say '     Catalan'     right(j, w)": "      Cat1B(j);   end
call hdr 2 ;  do j=LO  to HI;  say '     Catalan'     right(j, w)": "      Cat2(j) ;   end
call hdr 3 ;  do j=LO  to HI;  say '     Catalan'     right(j, w)": "      Cat3(j) ;   end
exit                                             /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
!:     arg z; if !.z\==. then return !.z; !=1;  do k=2  to z; !=!*k; end;  !.z=!; return !
Cat1A: procedure expose !.;  parse arg n;     return comb(n+n, n)    %  (n+1)
Cat1B: procedure expose !.;  parse arg n;     return !(n+n) % ((n+1) * !(n)**2)
Cat3:  procedure expose c.;  arg n; if c.n==. then c.n=(4*n-2)*cat3(n-1)%(n+1); return c.n
comb:  procedure;            parse arg x,y;   return pFact(x-y+1, x) % pFact(2, y)
hdr:   !.=.; c.=.; c.0=1; say; say center('Catalan numbers, method' arg(1),79,'─'); return
pFact: procedure;            !=1;      do k=arg(1)  to arg(2);  !=!*k;  end;    return !
/*──────────────────────────────────────────────────────────────────────────────────────*/
Cat2:  procedure expose c.;  parse arg n;  $=0;         if c.n\==.  then return c.n
                                       do k=0  for n;   $=$ + Cat2(k) * Cat2(n-k-1);   end
                             c.n=$;           return $    /*use a memoization technique.*/