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


Module Module1
 
    Function Factorial(n As Double) As Double
        If n < 1 Then
            Return 1
        End If
 
        Dim result = 1.0
        For i = 1 To n
            result = result * i
        Next
 
        Return result
    End Function
 
    Function FirstOption(n As Double) As Double
        Return Factorial(2 * n) / (Factorial(n + 1) * Factorial(n))
    End Function
 
    Function SecondOption(n As Double) As Double
        If n = 0 Then
            Return 1
        End If
 
        Dim sum = 0
        For i = 0 To n - 1
            sum = sum + SecondOption(i) * SecondOption((n - 1) - i)
        Next
        Return sum
    End Function
 
    Function ThirdOption(n As Double) As Double
        If n = 0 Then
            Return 1
        End If
 
        Return ((2 * (2 * n - 1)) / (n + 1)) * ThirdOption(n - 1)
    End Function
 
    Sub Main()
        Const MaxCatalanNumber = 15
 
        Dim initial As DateTime
        Dim final As DateTime
        Dim ts As TimeSpan
 
        initial = DateTime.Now
        For i = 0 To MaxCatalanNumber
            Console.WriteLine("CatalanNumber({0}:{1})", i, FirstOption(i))
        Next
        final = DateTime.Now
        ts = final - initial
        Console.WriteLine("It took {0}.{1} to execute", ts.Seconds, ts.Milliseconds)
        Console.WriteLine()
 
        initial = DateTime.Now
        For i = 0 To MaxCatalanNumber
            Console.WriteLine("CatalanNumber({0}:{1})", i, SecondOption(i))
        Next
        final = DateTime.Now
        ts = final - initial
        Console.WriteLine("It took {0}.{1} to execute", ts.Seconds, ts.Milliseconds)
        Console.WriteLine()
 
        initial = DateTime.Now
        For i = 0 To MaxCatalanNumber
            Console.WriteLine("CatalanNumber({0}:{1})", i, ThirdOption(i))
        Next
        final = DateTime.Now
        ts = final - initial
        Console.WriteLine("It took {0}.{1} to execute", ts.Seconds, ts.Milliseconds)
    End Sub
 
End Module