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


' FB 1.05.0 Win64
 
Function factorial(n As UInteger) As UInteger
  If n = 0 Then Return 1
  Return n * factorial(n - 1)
End Function
 
Function catalan1(n As UInteger) As UInteger
  Dim prod As UInteger = 1
  For i As UInteger = n + 2 To 2 * n
     prod *= i
  Next
  Return prod / factorial(n)
End Function
 
Function catalan2(n As UInteger) As UInteger
  If n = 0 Then Return 1
  Dim sum As UInteger = 0
  For i As UInteger = 0 To n - 1
    sum += catalan2(i) * catalan2(n - 1 - i)
  Next
  Return sum
End Function
 
Function catalan3(n As UInteger) As UInteger
  If n = 0 Then Return 1
  Return catalan3(n - 1) * 2 * (2 * n - 1) \ (n + 1)
End Function 
 
Print "n", "First", "Second", "Third"
Print "-", "-----", "------", "-----"
Print
For i As UInteger = 0 To 15
  Print i,  catalan1(i), catalan2(i), catalan3(i)
Next
Print
Print "Press any key to quit"
Sleep