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


with javascript_semantics 
-- returns inf/-nan for n>85, and needs the rounding for n>=14, accurate to n=29
function catalan1(integer n)
    return floor(factorial(2*n)/(factorial(n+1)*factorial(n))+0.5)
end function
 
-- returns inf for n>519, accurate to n=30:
function catalan2(integer n) -- NB: very slow!
atom res = not n
    n -= 1
    for i=0 to n do
        res += catalan2(i)*catalan2(n-i)
    end for
    return res
end function
 
-- returns inf for n>514, accurate to n=30:
function catalan3(integer n)
    if n=0 then return 1 end if
    return 2*(2*n-1)/(1+n)*catalan3(n-1)
end function 
 
sequence res = repeat(repeat(0,4),16),
         times = repeat(0,3)
for t=1 to 4 do
    atom t0 = time()
    for i=0 to 15 do
        switch t do
            case 1: res[i+1][2] = catalan1(i)
            case 2: res[i+1][3] = catalan2(i)
            case 3: res[i+1][4] = catalan3(i)
            case 4: res[i+1][1] = i; printf(1,"%2d: %10d %10d %10d\n",res[i+1])
        end switch
    end for
    if t=4 then exit end if
    times[t] = elapsed(time()-t0)
end for
printf(1,"times:%8s %10s %10s\n",times)
