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


# calculate the first few catalan numbers, using LONG INT values        #
# (64-bit quantities in Algol 68G which can handle up to C23)           #
 
# returns n!/k!                                                         #
PROC factorial over factorial = ( INT n, k )LONG INT:
     IF      k > n THEN 0
     ELIF    k = n THEN 1
     ELSE #  k < n #
         LONG INT f := 1;
         FOR i FROM k + 1 TO n DO f *:= i OD;
         f
     FI # factorial over factorial # ;
 
# returns n!                                                             #
PROC factorial = ( INT n )LONG INT:
     BEGIN
         LONG INT f := 1;
         FOR i FROM 2 TO n DO f *:= i OD;
         f
     END # factorial # ;
 
# returnss the nth Catalan number using binomial coefficeients            #
# uses the factorial over factorial procedure for a slight optimisation   #
# note:     Cn = 1/(n+1)(2n n)                                            #
#              = (2n)!/((n+1)!n!)                                         #
#              = factorial over factorial( 2n, n+1 )/n!                   #
PROC catalan = ( INT n )LONG INT: IF n < 2 THEN 1 ELSE factorial over factorial( n + n, n + 1 ) OVER factorial( n ) FI; 
 
# show the first few catalan numbers                                      #
FOR i FROM 0 TO 15 DO
    print( ( whole( i, -2 ), ": ", whole( catalan( i ), 0 ), newline ) )
OD