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


CATALAN  CSECT        08/09/2015
         USING  CATALAN,R15
         LA     R7,1               c=1
         LA     R6,1               i=1
LOOPI    CH     R6,=H'15'          do i=1 to 15 
         BH     ELOOPI
         XDECO  R6,PG              edit i
         LR     R5,R6              i
         SLA    R5,1               *2
         BCTR   R5,0               -1
         SLA    R5,1               *2
         MR     R4,R7              *c
         LA     R6,1(R6)           i=i+1
         DR     R4,R6              /i
         LR     R7,R5              c=2*(2*i-1)*c/(i+1)
         XDECO  R7,PG+12           edit c
         XPRNT  PG,24              print
         B      LOOPI              next i
ELOOPI   BR     R14
PG       DS     CL24
         YREGS 
         END    CATALAN