Catalan numbers

This page uses content from Wikipedia. The original article was at Catalan numbers. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)

Catalan numbers are a sequence of numbers which can be defined directly:

{\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}\qquad {\mbox{ for }}n\geq 0.}

Or recursively:

{\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):

{\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

11l

V c = 1
L(n) 1..15
   print(c)
   c = 2 * (2 * n - 1) * c I/ (n + 1)

Output:

360 Assembly

Very compact version.

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

Output:

           1           1
           2           2
           3           5
           4          14
           5          42
           6         132
           7         429
           8        1430
           9        4862
          10       16796
          11       58786
          12      208012
          13      742900
          14     2674440
          15     9694845

ABAP

This works for ABAP Version 7.40 and above

report z_catalan_numbers.

class catalan_numbers definition.
  public section.
    class-methods:
      get_nth_number
        importing
          i_n                     type int4
        returning
          value(r_catalan_number) type int4.
endclass.

class catalan_numbers implementation.
  method get_nth_number.
    r_catalan_number = cond int4(
      when i_n eq 0
      then 1
      else reduce int4(
        init
          result = 1
          index = 1
        for position = 1 while position <= i_n
        next
          result = result * 2 * ( 2 * index - 1 ) div ( index + 1 )
          index = index + 1 ) ).
  endmethod.
endclass.

start-of-selection.
  do 15 times.
    write / |C({ sy-index - 1 }) = { catalan_numbers=>get_nth_number( sy-index - 1 ) }|.
  enddo.

Output:

C(0) = 1
C(1) = 1
C(2) = 2
C(3) = 5
C(4) = 14
C(5) = 42
C(6) = 132
C(7) = 429
C(8) = 1430
C(9) = 4862
C(10) = 16796
C(11) = 58786
C(12) = 208012
C(13) = 742900
C(14) = 2674440

Action!

Library: Action! Tool Kit

INCLUDE "D2:REAL.ACT" ;from the Action! Tool Ki

PROC Main()
  REAL c,rnom,rden
  BYTE n,nom,den

  Put(125) PutE() ;clear the screen
  IntToReal(1,c)
  
  FOR n=1 TO 15
  DO
    nom=(n LSH 1-1) LSH 1
    den=n+1
    IntToReal(nom,rnom)
    IntToReal(den,rden)
    RealMult(c,rnom,c)
    RealDiv(c,rden,c)
    PrintF("C(%B)=",n) PrintRE(c)
  OD
RETURN

Output:

Screenshot from Atari 8-bit computer

C(1)=1
C(2)=2
C(3)=5
C(4)=14
C(5)=42
C(6)=132
C(7)=429
C(8)=1430
C(9)=4862
C(10)=16796
C(11)=58786
C(12)=208012
C(13)=742900
C(14)=2674440
C(15)=9694845

Ada

with Ada.Text_IO;  use Ada.Text_IO;

procedure Test_Catalan is
   function Catalan (N : Natural) return Natural is
      Result : Positive := 1;
   begin
      for I in 1..N loop
         Result := Result * 2 * (2 * I - 1) / (I + 1);
      end loop;
      return Result;
   end Catalan;
begin
   for N in 0..15 loop
      Put_Line (Integer'Image (N) & " =" & Integer'Image (Catalan (N)));
   end loop;
end Test_Catalan;

Sample output:

 0 = 1
 1 = 1
 2 = 2
 3 = 5
 4 = 14
 5 = 42
 6 = 132
 7 = 429
 8 = 1430
 9 = 4862
 10 = 16796
 11 = 58786
 12 = 208012
 13 = 742900
 14 = 2674440
 15 = 9694845

ALGOL 68

# 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

Output:

 0: 1
 1: 1
 2: 2
 3: 5
 4: 14
 5: 42
 6: 132
 7: 429
 8: 1430
 9: 4862
10: 16796
11: 58786
12: 208012
13: 742900
14: 2674440
15: 9694845

ALGOL W

begin
    % print the catalan numbers up to C15 %
    integer Cprev;
    Cprev := 1; % C0 %
    write(     s_w := 0, i_w := 3, 0, ": ", i_w := 9, Cprev );
    for n := 1 until 15 do begin
        Cprev := round( ( ( ( 4 * n ) - 2 ) / ( n + 1 ) ) * Cprev );
        write( s_w := 0, i_w := 3, n, ": ", i_w := 9, Cprev );
    end for_n
end.

Output:

  0:         1
  1:         1
  2:         2
  3:         5
  4:        14
  5:        42
  6:       132
  7:       429
  8:      1430
  9:      4862
 10:     16796
 11:     58786
 12:    208012
 13:    742900
 14:   2674440
 15:   9694845

APL

      {(!2×⍵)÷(!⍵+1)×!⍵}(⍳15)-1

Output:

1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440

Arturo

catalan: function [n][
	if? n=0 -> 1
	else 	-> div (catalan n-1) * (4*n)-2 n+1
]
 
loop 0..15 [i][
	print [
		pad.right to :string i 5 
		pad.left to :string catalan i 20
	]
]

Output:

0                        1 
1                        1 
2                        2 
3                        5 
4                       14 
5                       42 
6                      132 
7                      429 
8                     1430 
9                     4862 
10                   16796 
11                   58786 
12                  208012 
13                  742900 
14                 2674440 
15                 9694845

AutoHotkey

As AutoHotkey has no BigInt, the formula had to be tweaked to prevent overflow. It still fails after n=22

Loop 15
   out .= "`n" Catalan(A_Index)
Msgbox % clipboard := SubStr(out, 2)
catalan( n ) {
; By [VxE]. Returns ((2n)! / ((n + 1)! * n!)) if 0 <= N <= 22 (higher than 22 results in overflow)
If ( n < 3 ) ; values less than 3 are handled specially
   Return n < 0 ? "" : n = 0 ? 1 : n

i := 1 ; initialize the accumulator to 1

Loop % n - 1 >> 1 ; build the numerator by multiplying odd values between 2N and N+1
   i *= 1 + ( n - A_Index << 1 )

i <<= ( n - 2 >> 1 ) ; multiply the numerator by powers of 2 according to N

Loop % n - 3 >> 1 ; finish up by (integer) dividing by each of the non-cancelling factors
   i //= A_Index + 2

Return i
}

Output:

AWK

# syntax: GAWK -f CATALAN_NUMBERS.AWK
BEGIN {
    for (i=0; i<=15; i++) {
      printf("%2d %10d\n",i,catalan(i))
    }
    exit(0)
}
function catalan(n,  ans) {
    if (n == 0) {
      ans = 1
    }
    else {
      ans = ((2*(2*n-1))/(n+1))*catalan(n-1)
    }
    return(ans)
}

Output:

 0          1
 1          1
 2          2
 3          5
 4         14
 5         42
 6        132
 7        429
 8       1430
 9       4862
10      16796
11      58786
12     208012
13     742900
14    2674440
15    9694845

BASIC

Works with: FreeBASIC

Works with: QuickBASIC version 4.5 (untested)

Use of REDIM PRESERVE means this will not work in QBasic (although that could be worked around if desired).

DECLARE FUNCTION catalan (n as INTEGER) AS SINGLE

REDIM SHARED results(0) AS SINGLE

FOR x% = 1 TO 15
    PRINT x%, catalan (x%)
NEXT

FUNCTION catalan (n as INTEGER) AS SINGLE
    IF UBOUND(results) < n THEN REDIM PRESERVE results(n)

    IF 0 = n THEN
    	results(0) = 1
    ELSE
    	results(n) = ((2 * ((2 * n) - 1)) / (n + 1)) * catalan(n - 1)
    END IF
    catalan = results(n)
END FUNCTION

Output:

1             1
2             2
3             5
4             14
5             42
6             132
7             429
8             1430
9             4862
10            16796
11            58786
12            208012
13            742900
14            2674440
15            9694845

Applesoft BASIC

Works with: Chipmunk Basic

Works with: QBasic

10 HOME : REM  10 CLS for Chipmunk Basic/QBasic
20 DIM c(15)
30 c(0) = 1
40 PRINT 0, c(0)
50 FOR n = 0 TO 14
60   c(n + 1) = 0
70   FOR i = 0 TO n
80     c(n + 1) = c(n + 1) + c(i) * c(n - i)
90   NEXT i
100   PRINT n + 1, c(n + 1)
110 NEXT n
120 END

BASIC256

Translation of: FreeBASIC

function factorial(n)
    if n = 0 then return 1
    return n * factorial(n - 1)
end function

function catalan1(n)
    prod = 1
    for i = n + 2 to 2 * n
        prod *= i
    next i
    return int(prod / factorial(n))
end function

function catalan2(n)
    if n = 0 then return 1
    sum = 0
    for i = 0 to n - 1
        sum += catalan2(i) * catalan2(n - 1 - i)
    next i
    return sum
end function

function catalan3(n)
    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 = 0 to 15
    print i,  catalan1(i), catalan2(i), catalan3(i)
next i

Output:

Same as FreeBASIC entry.

BBC BASIC

      10 FOR i% = 1 TO 15
      20   PRINT FNcatalan(i%)
      30 NEXT
      40 END
      50 DEF FNcatalan(n%)
      60   IF n% = 0 THEN = 1
      70   = 2 * (2 * n% - 1) * FNcatalan(n% - 1) / (n% + 1)

Output:

Chipmunk Basic

Works with: Chipmunk Basic version 3.6.4

Translation of: Run BASIC

10 FOR i = 1 TO 15
20   PRINT i;" ";catalan(i)
30 NEXT
40 END
50 SUB catalan(n)
60   catalan = 1
70   IF n <> 0 THEN catalan = ((2*((2*n)-1))/(n+1))*catalan(n-1)
80 END SUB

Craft Basic

dim c[16]

let c[0] = 1

for n = 0 to 15

	let p = n + 1
	let c[p] = 0

	for i = 0 to n

		let q = n - i
		let c[p] = c[p] + c[i] * c[q]

	next i

	print n, " ", c[n]

next n

Output:

0 1 1 1 2 2 3 5 4 14 5 42 6 132 7 429 8 1430 9 4862 10 16796 11 58786 12 208012 13 742900 14 2674440 15 9694845

FreeBASIC

' 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

Output:

n             First         Second        Third
-             -----         ------        -----

0             1             1             1
1             1             1             1
2             2             2             2
3             5             5             5
4             14            14            14
5             42            42            42
6             132           132           132
7             429           429           429
8             1430          1430          1430
9             4862          4862          4862
10            16796         16796         16796
11            58786         58786         58786
12            208012        208012        208012
13            742900        742900        742900
14            2674440       2674440       2674440
15            9694845       9694845       9694845

FutureBasic

Translation of: FreeBASIC

include "NSLog.incl"

local fn Factorial( n as NSInteger ) as UInt64
  UInt64 sum = 0
  
  if n = 0 then sum = 1 : exit fn
  sum = n * fn Factorial( n - 1 )
end fn = sum

local fn Catalan1( n as NSInteger ) as UInt64
  UInt64     product = 1, result
  NSUInteger i
  
  for i = n + 2 to 2 * n
    product = product * i
  next
  result = product / fn Factorial( n )
end fn = result

local fn Catalan2( n as NSInteger ) as UInt64
  UInt64     sum = 0
  NSUInteger i
  
  if n = 0 then sum = 1 : exit fn
  for i = 0 to n - 1
    sum += fn Catalan2(i) * fn Catalan2( n - 1 - i )
  next
end fn = sum

local fn Catalan3( n as NSInteger ) as UInt64
  UInt64 result
  
  if n = 0 then result = 1 : exit fn
  result = fn Catalan3( n - 1 ) * 2 * ( 2 * n - 1 ) / ( n + 1 )
end fn = result

NSUInteger i

for i = 0 to 19
  if( i < 16 )
    NSLog( @"%3d.\t\t%7llu\t\t%12llu\t\t%12llu", i, fn Catalan1( i ), fn Catalan2( i ), fn Catalan3( i ) )
  else
    NSLog( @"%3d.\t\t%@\t\t%12llu\t\t%12llu", i, @"[-err-]", fn Catalan2( i ), fn Catalan3( i ) )
  end if
next
  
HandleEvents

Output:

  0.		      1		           1		           1
  1.		      1		           1		           1
  2.		      2		           2		           2
  3.		      5		           5		           5
  4.		     14		          14		          14
  5.		     42		          42		          42
  6.		    132		         132		         132
  7.		    429		         429		         429
  8.		   1430		        1430		        1430
  9.		   4862		        4862		        4862
 10.		  16796		       16796		       16796
 11.		  58786		       58786		       58786
 12.		 208012		      208012		      208012
 13.		 742900		      742900		      742900
 14.		2674440		     2674440		     2674440
 15.		9694845		     9694845		     9694845
 16.		[-err-]		    35357670		    35357670
 17.		[-err-]		   129644790		   129644790
 18.		[-err-]		   477638700		   477638700
 19.		[-err-]		  1767263190		  1767263190

GW-BASIC

Works with: BASICA

100 REM Catalan numbers
110 DIM C(15)
120 C(0) = 1
130 PRINT 0, C(0)
140 FOR N = 0 TO 14
150  C(N + 1) = 0
160  FOR I = 0 TO N
170   C(N + 1) = C(N + 1) + C(I) * C(N - I)
180  NEXT I
190  PRINT N + 1, C(N + 1)
200 NEXT N
210 END

Output:

 0             1
 1             1
 2             2
 3             5
 4             14
 5             42
 6             132
 7             429
 8             1430
 9             4862
 10            16796
 11            58786
 12            208012
 13            742900
 14            2674440
 15            9694845

Liberty BASIC

Works with: Just BASIC

print "non-recursive version"
print catNonRec(5)
for i = 0 to 15
    print i;"   =   "; catNonRec(i)
next
print

print "recursive version"
print catRec(5)
for i = 0 to 15
    print i;"   =   "; catRec(i)
next
print

print "recursive with memoisation"
redim cats(20)  'clear the array
print catRecMemo(5)
for i = 0 to 15
    print i;"   =   "; catRecMemo(i)
next
print


wait

function catNonRec(n)   'non-recursive version
    catNonRec=1
    for i=1 to n
        catNonRec=((2*((2*i)-1))/(i+1))*catNonRec
    next
end function

function catRec(n)  'recursive version
    if n=0 then
        catRec=1
    else
        catRec=((2*((2*n)-1))/(n+1))*catRec(n-1)
    end if
end function

function catRecMemo(n)  'recursive version with memoisation
    if n=0 then
        catRecMemo=1
    else
        if cats(n-1)=0 then    'call it recursively only if not already calculated
            prev = catRecMemo(n-1)
        else
            prev = cats(n-1)
        end if
        catRecMemo=((2*((2*n)-1))/(n+1))*prev
    end if
    cats(n) = catRecMemo    'memoisation for future use
end function

Output:

non-recursive version
42
0   =   1
1   =   1
2   =   2
3   =   5
4   =   14
5   =   42
6   =   132
7   =   429
8   =   1430
9   =   4862
10   =   16796
11   =   58786
12   =   208012
13   =   742900
14   =   2674440
15   =   9694845

recursive version
42
0   =   1
1   =   1
2   =   2
3   =   5
4   =   14
5   =   42
6   =   132
7   =   429
8   =   1430
9   =   4862
10   =   16796
11   =   58786
12   =   208012
13   =   742900
14   =   2674440
15   =   9694845

recursive with memoisation
42
0   =   1
1   =   1
2   =   2
3   =   5
4   =   14
5   =   42
6   =   132
7   =   429
8   =   1430
9   =   4862
10   =   16796
11   =   58786
12   =   208012
13   =   742900
14   =   2674440
15   =   9694845

Minimal BASIC

Translation of: GW-BASIC

10 REM Catalan numbers
20 DIM C(15)
30 LET C(0) = 1
40 PRINT 0, C(0)
50 FOR N = 0 TO 14
60 LET C(N+1) = 0
70 FOR I = 0 TO N
80 LET C(N+1) = C(N+1)+C(I)*C(N-I)
90 NEXT I
100 PRINT N+1, C(N+1)
110 NEXT N
120 END

PureBasic

Using the third formula...

; saving the division for last ensures we divide the largest
; numerator by the smallest denominator

Procedure.q CatalanNumber(n.q)
If n<0:ProcedureReturn 0:EndIf
If n=0:ProcedureReturn 1:EndIf
ProcedureReturn (2*(2*n-1))*CatalanNumber(n-1)/(n+1)
EndProcedure

ls=25
rs=12

a.s=""
a.s+LSet(RSet("n",rs),ls)+"CatalanNumber(n)"
; cw(a.s)
Debug a.s

For n=0 to 33 ;33 largest correct quad for n 
a.s=""
a.s+LSet(RSet(Str(n),rs),ls)+Str(CatalanNumber(n))
; cw(a.s)
Debug a.s
Next

Sample Output:

           n             CatalanNumber(n)
           0             1
           1             1
           2             2
           3             5
           4             14
           5             42
           6             132
           7             429
           8             1430
           9             4862
          10             16796
          11             58786
          12             208012
          13             742900
          14             2674440
          15             9694845
          16             35357670
          17             129644790
          18             477638700
          19             1767263190
          20             6564120420
          21             24466267020
          22             91482563640
          23             343059613650
          24             1289904147324
          25             4861946401452
          26             18367353072152
          27             69533550916004
          28             263747951750360
          29             1002242216651368
          30             3814986502092304
          31             14544636039226909
          32             55534064877048198
          33             212336130412243110

Run BASIC

FOR i = 1 TO 15
    PRINT i;" ";catalan(i)
NEXT
 
FUNCTION catalan(n) 
 catalan = 1
 if n <> 0 then catalan = ((2 * ((2 * n) - 1)) / (n + 1)) * catalan(n - 1)
END FUNCTION

Sinclair ZX81 BASIC

Works with 1k of RAM.

The specification asks for the first 15 Catalan numbers. A lot of the other implementations produce either C(0) to C(15), which is 16 numbers, or else C(1) to C(15)—which is 15 numbers, but I'm not convinced they're the first 15. This program produces C(0) to C(14).

 10 FOR N=0 TO 14
 20 LET X=N
 30 GOSUB 130
 40 LET A=FX
 50 LET X=N+1
 60 GOSUB 130
 70 LET B=FX
 80 LET X=2*N
 90 GOSUB 130
100 PRINT N,FX/(B*A)
110 NEXT N
120 STOP
130 LET FX=1
140 FOR I=1 TO X
150 LET FX=FX*I
160 NEXT I
170 RETURN

Output:

0               1
1               1
2               2
3               5
4               14
5               42
6               132
7               429
8               1430
9               4862
10              16796
11              58786
12              208012
13              742900
14              2674440

smart BASIC

PRINT "Recursive:"!PRINT
FOR n = 0 TO 15
    PRINT n,"#######":catrec(n)
NEXT n
PRINT!PRINT

PRINT "Non-recursive:"!PRINT
FOR n = 0 TO 15
    PRINT n,"#######":catnonrec(n)
NEXT n

END
 
DEF catrec(x)
    IF x = 0 THEN
        temp = 1
    ELSE 
        n = x
        temp = ((2*((2*n)-1))/(n+1))*catrec(n-1)
    END IF
    catrec = temp
END DEF

DEF catnonrec(x)
    temp = 1
    FOR n = 1 TO x
         temp = (2*((2*n)-1))/(n+1)*temp
    NEXT n
    catnonrec = temp
END DEF

TI-83 BASIC

This problem is perfectly suited for a TI calculator.

:For(I,1,15
:Disp (2I)!/((I+1)!I!
:End

Output:

Tiny BASIC

Integers are limited to 32767 so only the first ten Catalan numbers can be represented. And even then one has to do some finagling to avoid internal overflows.

Works with: TinyBasic

10 REM Catalan numbers
20 LET N = 0
30 LET C = 1
40 PRINT N," ",C
50 IF N > 9 THEN END
60 LET N = N + 1
70 GOSUB 200
80 LET C = (2 * N - 1) * C
90 LET C = 2 * C / (N + 1)
100 LET C = C + 2 * I * (2 * N - 1)
110 GOTO 40
200 LET I = 0
210 IF C <= 0 THEN RETURN
220 LET C = C - (N + 1)
230 LET I = I + 1
240 GOTO 210
250 REM To avoid internal overflow, I subtract something clever from
260 REM C and then add it back at the end.

Output:

0               1
1               1
2               2
3               5
4               14
5               42
6               132
7               429
8               1430
9               4862
10              16796

VBA

Public Sub Catalan1(n As Integer)
'Computes the first n Catalan numbers according to the first recursion given
Dim Cat() As Long
Dim sum As Long

ReDim Cat(n)
Cat(0) = 1
For i = 0 To n - 1
  sum = 0
  For j = 0 To i
    sum = sum + Cat(j) * Cat(i - j)
  Next j
  Cat(i + 1) = sum
Next i
Debug.Print
For i = 0 To n
  Debug.Print i, Cat(i)
Next
End Sub

Public Sub Catalan2(n As Integer)
'Computes the first n Catalan numbers according to the second recursion given
Dim Cat() As Long

ReDim Cat(n)
Cat(0) = 1
For i = 1 To n
  Cat(i) = 2 * Cat(i - 1) * (2 * i - 1) / (i + 1)
Next i
Debug.Print
For i = 0 To n
  Debug.Print i, Cat(i)
Next
End Sub

Result:

Catalan1 15

 0             1 
 1             1 
 2             2 
 3             5 
 4             14 
 5             42 
 6             132 
 7             429 
 8             1430 
 9             4862 
 10            16796 
 11            58786 
 12            208012 
 13            742900 
 14            2674440 
 15            9694845

(Expect same result with "Catalan2 15")

VBScript

Function catalan(n)
	catalan = factorial(2*n)/(factorial(n+1)*factorial(n))
End Function

Function factorial(n)
	If n = 0 Then
		Factorial = 1
	Else
		For i = n To 1 Step -1
			If i = n Then
				factorial = n
			Else
				factorial = factorial * i
			End If
		Next
	End If
End Function

'Find the first 15 Catalan numbers.
For j = 1 To 15
	WScript.StdOut.Write j & " = " & catalan(j)
	WScript.StdOut.WriteLine
Next

Output:

1 = 1
2 = 2
3 = 5
4 = 14
5 = 42
6 = 132
7 = 429
8 = 1430
9 = 4862
10 = 16796
11 = 58786
12 = 208012
13 = 742900
14 = 2674440
15 = 9694845

Visual Basic .NET

Translation of: C#

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

Output:

CatalanNumber(0:1)
CatalanNumber(1:1)
CatalanNumber(2:2)
CatalanNumber(3:5)
CatalanNumber(4:14)
CatalanNumber(5:42)
CatalanNumber(6:132)
CatalanNumber(7:429)
CatalanNumber(8:1430)
CatalanNumber(9:4862)
CatalanNumber(10:16796)
CatalanNumber(11:58786)
CatalanNumber(12:208012)
CatalanNumber(13:742900)
CatalanNumber(14:2674440)
CatalanNumber(15:9694845)
It took 0.19 to execute

CatalanNumber(0:1)
CatalanNumber(1:1)
CatalanNumber(2:2)
CatalanNumber(3:5)
CatalanNumber(4:14)
CatalanNumber(5:42)
CatalanNumber(6:132)
CatalanNumber(7:429)
CatalanNumber(8:1430)
CatalanNumber(9:4862)
CatalanNumber(10:16796)
CatalanNumber(11:58786)
CatalanNumber(12:208012)
CatalanNumber(13:742900)
CatalanNumber(14:2674440)
CatalanNumber(15:9694845)
It took 0.831 to execute

CatalanNumber(0:1)
CatalanNumber(1:1)
CatalanNumber(2:2)
CatalanNumber(3:5)
CatalanNumber(4:14)
CatalanNumber(5:42)
CatalanNumber(6:132)
CatalanNumber(7:429)
CatalanNumber(8:1430)
CatalanNumber(9:4862)
CatalanNumber(10:16796)
CatalanNumber(11:58786)
CatalanNumber(12:208012)
CatalanNumber(13:742900)
CatalanNumber(14:2674440)
CatalanNumber(15:9694845)
It took 0.8 to execute

Yabasic

Translation of: FreeBASIC

print "  n   First    Second    Third"
print "  -   -----    ------    -----"
print
for i = 0 to 15
	print i using "###", catalan1(i) using "########", catalan2(i) using "########", catalan3(i) using "########"
next i
end

sub factorial(n)
    if n = 0  return 1
    return n * factorial(n - 1)
end sub

sub catalan1(n)
    local proc, i

    prod = 1
    for i = n + 2 to 2 * n
        prod = prod * i
    next i
    return int(prod / factorial(n))
end sub

sub catalan2(n)
    local sum, i

    if n = 0  return 1
    sum = 0
    for i = 0 to n - 1
        sum = sum + catalan2(i) * catalan2(n - 1 - i)
    next i
    return sum
end sub

sub catalan3(n)
    if n = 0  return 1
    return ((2 * ((2 * n) - 1)) / (n + 1)) * catalan3(n - 1)
end sub

Output:

Same as FreeBASIC entry.

Befunge

Translation of: Ada

0>:.:000p1>\:00g-#v_v
v 2-1*2p00 :+1g00\< $
> **00g1+/^v,*84,"="<
_^#<`*53:+1>#,.#+5< @

Output:

0 = 1
1 = 1
2 = 2
3 = 5
4 = 14
5 = 42
6 = 132
7 = 429
8 = 1430
9 = 4862
10 = 16796
11 = 58786
12 = 208012
13 = 742900
14 = 2674440
15 = 9694845

BQN

Cat←{ 0⊸<◶⟨1, (𝕊-⟜1)×(¯2+4×⊢)÷1+⊢⟩ 𝕩 }
Fact ← ×´1+↕
Cat1 ← { # direct formula
  ⌊0.5 + (Fact 2×𝕩) ÷ (Fact 𝕩+1) × Fact 𝕩
}
Cat2 ← { # header based recursion
  0: 1;
  (𝕊 𝕩-1)×2×(1-˜2×𝕩)÷𝕩+1
}

Cat¨ ↕15
Cat1¨ ↕15
Cat2¨ ↕15

Output:

⟨ 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 ⟩

Bracmat

( out$straight
& ( C
  =   
    .   ( F
        =   i prod
          .   !arg:0&1
            |   1:?prod
              & 0:?i
              &   whl
                ' ( 1+!i:~>!arg:?i
                  & !i*!prod:?prod
                  )
              & !prod
        )
      & F$(2*!arg)*(F$(!arg+1)*F$!arg)^-1
  )
& -1:?n
&   whl
  ' ( 1+!n:~>15:?n
    & out$(str$(C !n " = " C$!n))
    )
& out$"recursive, with memoization, without fractions"
& :?seenCs
& ( C
  =   i sum
    .   !arg:0&1
      |   ( !seenCs:? (!arg.?sum) ?
          |   0:?sum
            & -1:?i
            &   whl
              ' ( 1+!i:<!arg:?i
                & C$!i*C$(-1+!arg+-1*!i)+!sum:?sum
                )
            & (!arg.!sum) !seenCs:?seenCs
          )
        & !sum
  )
& -1:?n
&   whl
  ' ( 1+!n:~>15:?n
    & out$(str$(C !n " = " C$!n))
    )
& out$"recursive, without memoization, with fractions"
& ( C
  =   
    .   !arg:0&1
      | 2*(2*!arg+-1)*(!arg+1)^-1*C$(!arg+-1)
  )
& -1:?n
&   whl
  ' ( 1+!n:~>15:?n
    & out$(str$(C !n " = " C$!n))
    )
& out$"Using taylor expansion of sqrt(1-4X). (See http://bababadalgharaghtakamminarronnkonnbro.blogspot.in/2012/10/algebraic-type-systems-combinatorial.html)"
& out$(1+(1+-1*tay$((1+-4*X)^1/2,X,16))*(2*X)^-1+-1)
& out$
);

Output:

straight
C0 = 1
C1 = 1
C2 = 2
C3 = 5
C4 = 14
C5 = 42
C6 = 132
C7 = 429
C8 = 1430
C9 = 4862
C10 = 16796
C11 = 58786
C12 = 208012
C13 = 742900
C14 = 2674440
C15 = 9694845
recursive, with memoization, without fractions
C0 = 1
C1 = 1
C2 = 2
C3 = 5
C4 = 14
C5 = 42
C6 = 132
C7 = 429
C8 = 1430
C9 = 4862
C10 = 16796
C11 = 58786
C12 = 208012
C13 = 742900
C14 = 2674440
C15 = 9694845
recursive, without memoization, with fractions
C0 = 1
C1 = 1
C2 = 2
C3 = 5
C4 = 14
C5 = 42
C6 = 132
C7 = 429
C8 = 1430
C9 = 4862
C10 = 16796
C11 = 58786
C12 = 208012
C13 = 742900
C14 = 2674440
C15 = 9694845
Using taylor expansion of sqrt(1-4X). (See http://bababadalgharaghtakamminarronnkonnbro.blogspot.in/2012/10/algebraic-type-systems-combinatorial.html)
  1
+ X
+ 2*X^2
+ 5*X^3
+ 14*X^4
+ 42*X^5
+ 132*X^6
+ 429*X^7
+ 1430*X^8
+ 4862*X^9
+ 16796*X^10
+ 58786*X^11
+ 208012*X^12
+ 742900*X^13
+ 2674440*X^14
+ 9694845*X^15

Brat

catalan = { n |
  true? n == 0
    { 1 }
    { (2 * ( 2 * n - 1) / ( n + 1 )) * catalan(n - 1) }
}

0.to 15 { n |
  p "#{n} - #{catalan n}"
}

Output:

0 - 1
1 - 1
2 - 2
3 - 5
4 - 14
5 - 42
6 - 132
7 - 429
8 - 1430
9 - 4862
10 - 16796
11 - 58786
12 - 208012
13 - 742900
14 - 2674440
15 - 9694845

C

All three methods mentioned in the task:

#include <stdio.h>

typedef unsigned long long ull;

ull binomial(ull m, ull n)
{
	ull r = 1, d = m - n;
	if (d > n) { n = d; d = m - n; }

	while (m > n) {
		r *= m--;
		while (d > 1 && ! (r%d) ) r /= d--;
	}

	return r;
}

ull catalan1(int n) {
	return binomial(2 * n, n) / (1 + n);
}

ull catalan2(int n) {
	int i;
	ull r = !n;

	for (i = 0; i < n; i++)
		r += catalan2(i) * catalan2(n - 1 - i);
	return r;
}

ull catalan3(int n)
{
	return n ? 2 * (2 * n - 1) * catalan3(n - 1) / (1 + n) : 1;
}

int main(void)
{
	int i;
	puts("\tdirect\tsumming\tfrac");
	for (i = 0; i < 16; i++) {
		printf("%d\t%llu\t%llu\t%llu\n", i,
			catalan1(i), catalan2(i), catalan3(i));
	}

	return 0;
}

Output:

       direct  summing frac
0      1       1       1
1      1       1       1
2      2       2       2
3      5       5       5
4      14      14      14
5      42      42      42
6      132     132     132
7      429     429     429
8      1430    1430    1430
9      4862    4862    4862
10     16796   16796   16796
11     58786   58786   58786
12     208012  208012  208012
13     742900  742900  742900
14     2674440 2674440 2674440
15     9694845 9694845 9694845

C#

namespace CatalanNumbers
{
    /// <summary>
    /// Class that holds all options.
    /// </summary>
    public class CatalanNumberGenerator
    {
        private static double Factorial(double n)
        {
            if (n == 0)
                return 1;

            return n * Factorial(n - 1);
        }

        public double FirstOption(double n)
        {
            const double topMultiplier = 2;
            return Factorial(topMultiplier * n) / (Factorial(n + 1) * Factorial(n));
        }

        public double SecondOption(double n)
        {
            if (n == 0)
            {
                return 1;
            }
            double sum = 0;
            double i = 0;
            for (; i <= (n - 1); i++)
            {
                sum += SecondOption(i) * SecondOption((n - 1) - i);
            }
            return sum;
        }

        public double ThirdOption(double n)
        {
            if (n == 0)
            {
                return 1;
            }
            return ((2 * (2 * n - 1)) / (n + 1)) * ThirdOption(n - 1);
        }
    }
}


// Program.cs
using System;
using System.Configuration;

// Main program
// Be sure to add the following to the App.config file and add a reference to System.Configuration:
// <?xml version="1.0" encoding="utf-8" ?>
// <configuration>
//  <appSettings>
//    <clear/>
//    <add key="MaxCatalanNumber" value="50"/>
//  </appSettings>
// </configuration>
namespace CatalanNumbers
{
    class Program
    {
        static void Main(string[] args)
        {
            CatalanNumberGenerator generator = new CatalanNumberGenerator();
            int i = 0;
            DateTime initial;
            DateTime final;
            TimeSpan ts;

            try
            {
                initial = DateTime.Now;
                for (; i <= Convert.ToInt32(ConfigurationManager.AppSettings["MaxCatalanNumber"]); i++)
                {
                    Console.WriteLine("CatalanNumber({0}):{1}", i, generator.FirstOption(i));
                }
                final = DateTime.Now;
                ts = final - initial;
                Console.WriteLine("It took {0}.{1} to execute\n", ts.Seconds, ts.Milliseconds);

                i = 0;
                initial = DateTime.Now;
                for (; i <= Convert.ToInt32(ConfigurationManager.AppSettings["MaxCatalanNumber"]); i++)
                {
                    Console.WriteLine("CatalanNumber({0}):{1}", i, generator.SecondOption(i));
                }
                final = DateTime.Now;
                ts = final - initial;
                Console.WriteLine("It took {0}.{1} to execute\n", ts.Seconds, ts.Milliseconds);   

                i = 0;
                initial = DateTime.Now;
                for (; i <= Convert.ToInt32(ConfigurationManager.AppSettings["MaxCatalanNumber"]); i++)
                {
                    Console.WriteLine("CatalanNumber({0}):{1}", i, generator.ThirdOption(i));
                }
                final = DateTime.Now;
                ts = final - initial;
                Console.WriteLine("It took {0}.{1} to execute", ts.Seconds, ts.Milliseconds, ts.TotalMilliseconds);
                Console.ReadLine();
            }
            catch (Exception ex)
            {
                Console.WriteLine("Stopped at index {0}:", i);
                Console.WriteLine(ex.Message);
                Console.ReadLine();
            }
        }
    }
}

Output:

CatalanNumber(0):1
CatalanNumber(1):1
CatalanNumber(2):2
CatalanNumber(3):5
CatalanNumber(4):14
CatalanNumber(5):42
CatalanNumber(6):132
CatalanNumber(7):429
CatalanNumber(8):1430
CatalanNumber(9):4862
CatalanNumber(10):16796
CatalanNumber(11):58786
CatalanNumber(12):208012
CatalanNumber(13):742900
CatalanNumber(14):2674440
CatalanNumber(15):9694845
It took 0.14 to execute

CatalanNumber(0):1
CatalanNumber(1):1
CatalanNumber(2):2
CatalanNumber(3):5
CatalanNumber(4):14
CatalanNumber(5):42
CatalanNumber(6):132
CatalanNumber(7):429
CatalanNumber(8):1430
CatalanNumber(9):4862
CatalanNumber(10):16796
CatalanNumber(11):58786
CatalanNumber(12):208012
CatalanNumber(13):742900
CatalanNumber(14):2674440
CatalanNumber(15):9694845
It took 0.922 to execute

CatalanNumber(0):1
CatalanNumber(1):1
CatalanNumber(2):2
CatalanNumber(3):5
CatalanNumber(4):14
CatalanNumber(5):42
CatalanNumber(6):132
CatalanNumber(7):429
CatalanNumber(8):1430
CatalanNumber(9):4862
CatalanNumber(10):16796
CatalanNumber(11):58786
CatalanNumber(12):208012
CatalanNumber(13):742900
CatalanNumber(14):2674440
CatalanNumber(15):9694845
It took 0.3 to execute

C++

4 Classes

We declare 4 classes representing the four different algorithms for calculating Catalan numbers as given in the description of the task. In addition, we declare two supporting classes for the calculation of factorials and binomial coefficients. Because these two are only internal supporting code they are hidden in namespace 'detail'. Overloading the function call operator to execute the calculation is an obvious decision when using C++. (algorithms.h)

#if !defined __ALGORITHMS_H__
#define __ALGORITHMS_H__

namespace rosetta
  {
  namespace catalanNumbers
    {
    namespace detail
      {

      class Factorial
        {
        public:
          unsigned long long operator()(unsigned n)const;
        };

      class BinomialCoefficient
        {
        public:
          unsigned long long operator()(unsigned n, unsigned k)const;
        };

      } //namespace detail

    class CatalanNumbersDirectFactorial
      {
      public:
        CatalanNumbersDirectFactorial();
        unsigned long long operator()(unsigned n)const;
      private:
        detail::Factorial factorial;
      };

    class CatalanNumbersDirectBinomialCoefficient
      {
      public:
        CatalanNumbersDirectBinomialCoefficient();
        unsigned long long operator()(unsigned n)const;
      private:
        detail::BinomialCoefficient binomialCoefficient;
      };

    class CatalanNumbersRecursiveSum
      {
      public:
        CatalanNumbersRecursiveSum();
        unsigned long long operator()(unsigned n)const;
      };

    class CatalanNumbersRecursiveFraction
      {
      public:
        CatalanNumbersRecursiveFraction();
        unsigned long long operator()(unsigned n)const;
      };

    }   //namespace catalanNumbers
  }     //namespace rosetta

#endif //!defined __ALGORITHMS_H__

Here is the implementation of the algorithms. The c'tor of each class tells us the algorithm which will be used. (algorithms.cpp)

#include <iostream>
using std::cout;
using std::endl;
#include <cmath>
using std::floor;

#include "algorithms.h"
using namespace rosetta::catalanNumbers;


CatalanNumbersDirectFactorial::CatalanNumbersDirectFactorial()
  {
  cout<<"Direct calculation using the factorial"<<endl;
  }

unsigned long long CatalanNumbersDirectFactorial::operator()(unsigned n)const
  {
  if(n>1)
    {
    unsigned long long nFac = factorial(n);
    return factorial(2 * n) / ((n + 1) * nFac * nFac);
    }
  else
    {
    return 1;
    }
  }


CatalanNumbersDirectBinomialCoefficient::CatalanNumbersDirectBinomialCoefficient()
  {
  cout<<"Direct calculation using a binomial coefficient"<<endl;
  }

unsigned long long CatalanNumbersDirectBinomialCoefficient::operator()(unsigned n)const
  {
  if(n>1)
    return double(1) / (n + 1) * binomialCoefficient(2 * n, n);
  else
    return 1;
  }


CatalanNumbersRecursiveSum::CatalanNumbersRecursiveSum()
  {
  cout<<"Recursive calculation using a sum"<<endl;
  }

unsigned long long CatalanNumbersRecursiveSum::operator()(unsigned n)const
  {
  if(n>1)
    {
    const unsigned n_ = n - 1;
    unsigned long long sum = 0;
    for(unsigned i = 0; i <= n_; i++)
      sum += operator()(i) * operator()(n_ - i);
    return sum;
    }
  else
    {
    return 1;
    }
  }


CatalanNumbersRecursiveFraction::CatalanNumbersRecursiveFraction()
  {
  cout<<"Recursive calculation using a fraction"<<endl;
  }

unsigned long long CatalanNumbersRecursiveFraction::operator()(unsigned n)const
  {
  if(n>1)
    return (double(2 * (2 * n - 1)) / (n + 1)) * operator()(n-1);
  else
    return 1;
  }


unsigned long long detail::Factorial::operator()(unsigned n)const
  {
  if(n>1)
    return n * operator()(n-1);
  else
    return 1;
  }


unsigned long long detail::BinomialCoefficient::operator()(unsigned n, unsigned k)const
  {
  if(k == 0)
    return 1;
  
  if(n == 0)
    return 0;

  double product = 1;
  for(unsigned i = 1; i <= k; i++)
    product *= (double(n - (k - i)) / i);
  return (unsigned long long)(floor(product + 0.5));
  }

In order to test what we have done, a class Test is created. Using the template parameters N (number of Catalan numbers to be calculated) and A (the kind of algorithm to be used) the compiler will create code for all the test cases we need. What would C++ be without templates ;-) (tester.h)

#if !defined __TESTER_H__
#define __TESTER_H__

#include <iostream>

namespace rosetta
  {
  namespace catalanNumbers
    {

    template <int N, typename A>
    class Test
      {
      public:
        static void Do()
          {
          A algorithm;
          for(int i = 0; i <= N; i++)
            std::cout<<"C("<<i<<")\t= "<<algorithm(i)<<std::endl;
          }
      };

    } //namespace catalanNumbers
  }   //namespace rosetta

#endif //!defined __TESTER_H__

Finally, we test the four different algorithms. Note that the first one (direct calculation using the factorial) only works up to N = 10 because some intermediate result (namely (2n)! with n = 11) exceeds the boundaries of an unsigned 64 bit integer. (catalanNumbersTest.cpp)

#include "algorithms.h"
#include "tester.h"
using namespace rosetta::catalanNumbers;

int main(int argc, char* argv[])
  {
  Test<10, CatalanNumbersDirectFactorial>::Do();
  Test<15, CatalanNumbersDirectBinomialCoefficient>::Do();
  Test<15, CatalanNumbersRecursiveFraction>::Do();
  Test<15, CatalanNumbersRecursiveSum>::Do();
  return 0;
  }

Output:

(source code is compiled both by MS Visual C++ 10.0 (WinXP 32 bit) and GNU g++ 4.4.3 (Ubuntu 10.04 64 bit) compilers)

Direct calculation using the factorial
C(0)    = 1
C(1)    = 1
C(2)    = 2
C(3)    = 5
C(4)    = 14
C(5)    = 42
C(6)    = 132
C(7)    = 429
C(8)    = 1430
C(9)    = 4862
C(10)   = 16796
Direct calculation using a binomial coefficient
C(0)    = 1
C(1)    = 1
C(2)    = 2
C(3)    = 5
C(4)    = 14
C(5)    = 42
C(6)    = 132
C(7)    = 428
C(8)    = 1430
C(9)    = 4862
C(10)   = 16796
C(11)   = 58786
C(12)   = 208012
C(13)   = 742900
C(14)   = 2674440
C(15)   = 9694845
Recursive calculation using a fraction
C(0)    = 1
C(1)    = 1
C(2)    = 2
C(3)    = 5
C(4)    = 14
C(5)    = 42
C(6)    = 132
C(7)    = 429
C(8)    = 1430
C(9)    = 4862
C(10)   = 16796
C(11)   = 58786
C(12)   = 208012
C(13)   = 742900
C(14)   = 2674440
C(15)   = 9694845
Recursive calculation using a sum
C(0)    = 1
C(1)    = 1
C(2)    = 2
C(3)    = 5
C(4)    = 14
C(5)    = 42
C(6)    = 132
C(7)    = 429
C(8)    = 1430
C(9)    = 4862
C(10)   = 16796
C(11)   = 58786
C(12)   = 208012
C(13)   = 742900
C(14)   = 2674440
C(15)   = 9694845

Clojure

(def ! (memoize #(apply * (range 1 (inc %)))))

(defn catalan-numbers-direct []
  (map #(/ (! (* 2 %))
	   (* (! (inc %)) (! %))) (range)))

(def catalan-numbers-recursive
     #(->> [1 1] ; [c0 n1]
	   (iterate (fn [[c n]]
		      [(* 2 (dec (* 2 n)) (/ (inc n)) c) (inc n)]) ,)
	   (map first ,)))

user> (take 15 (catalan-numbers-direct))
(1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440)

user> (take 15 (catalan-numbers-recursive))
(1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440)

CLU

catalan = iter (amount: int) yields (int)
    c: int := 1
    for n: int in int$from_to(1, amount) do
        yield(c)
        c := (4*n-2)*c/(n+1)
    end
end catalan

start_up = proc ()
    po: stream := stream$primary_output()
    for n: int in catalan(15) do
        stream$putl(po, int$unparse(n))
    end
end start_up

Output:

Common Lisp

With all three methods defined.

(defun catalan1 (n)
  ;; factorial. CLISP actually has "!" defined for this
  (labels ((! (x) (if (zerop x) 1 (* x (! (1- x))))))
    (/ (! (* 2 n)) (! (1+ n)) (! n))))

;; cache
(defparameter *catalans* (make-array 5
				     :fill-pointer 0
				     :adjustable t
				     :element-type 'integer))
(defun catalan2 (n)
    (if (zerop n) 1
    ;; check cache
    (if (< n (length *catalans*)) (aref *catalans* n)
      (loop with c = 0 for i from 0 to (1- n) collect
	    (incf c (* (catalan2 i) (catalan2 (- n 1 i))))
	    ;; lower values always get calculated first, so
	    ;; vector-push-extend is safe
	    finally (progn (vector-push-extend c *catalans*) (return c))))))

(defun catalan3 (n)
  (if (zerop n) 1 (/ (* 2 (+ n n -1) (catalan3 (1- n))) (1+ n))))

;;; test all three methods
(loop for f in (list #'catalan1 #'catalan2 #'catalan3)
      for i from 1 to 3 do
      (format t "~%Method ~d:~%" i)
      (dotimes (i 16) (format t "C(~2d) = ~d~%" i (funcall f i))))

Cowgol

include "cowgol.coh";

sub catalan(n: uint32): (c: uint32) is
    c := 1;
    var i: uint32 := 1;
    while i <= n loop
        c := (4*i-2)*c/(i+1);
        i := i+1;
    end loop;
end sub;

var i: uint8 := 0;
while i < 15 loop
    print("catalan(");
    print_i8(i);
    print(") = ");
    print_i32(catalan(i as uint32));
    print_nl();
    i := i+1;
end loop;

Output:

catalan(0) = 1
catalan(1) = 1
catalan(2) = 2
catalan(3) = 5
catalan(4) = 14
catalan(5) = 42
catalan(6) = 132
catalan(7) = 429
catalan(8) = 1430
catalan(9) = 4862
catalan(10) = 16796
catalan(11) = 58786
catalan(12) = 208012
catalan(13) = 742900
catalan(14) = 2674440

Crystal

Translation of: Ruby

require "big"
require "benchmark"

def factorial(n : BigInt) : BigInt
  (1..n).product(1.to_big_i)
end

def factorial(n : Int32 | Int64)
  factorial n.to_big_i
end

# direct

def catalan_direct(n)
  factorial(2*n) / (factorial(n + 1) * factorial(n))
end

# recursive

def catalan_rec1(n)
  return 1 if n == 0
  (0...n).reduce(0) do |sum, i|
    sum + catalan_rec1(i) * catalan_rec1(n - 1 - i)
  end
end

def catalan_rec2(n)
  return 1 if n == 0
  2*(2*n - 1) * catalan_rec2(n - 1) / (n + 1)
end

# performance and results

Benchmark.bm do |b|
  b.report("catalan_direct") { 16.times { |n| catalan_direct(n) } }
  b.report("catalan_rec1") { 16.times { |n| catalan_rec1(n) } }
  b.report("catalan_rec2") { 16.times { |n| catalan_rec2(n) } }
end

puts "\n       direct     rec1     rec2"
16.times { |n| puts "%2d :%9d%9d%9d" % [n, catalan_direct(n), catalan_rec1(n), catalan_rec2(n)] }

Output:

# with --release flag 
# Using: i7-6700HQ, 3.5GHz
                     user     system      total        real
catalan_direct   0.000026   0.000052   0.000078 (  0.000074)
catalan_rec1     0.139766   0.001143   0.140909 (  0.141418)
catalan_rec2     0.000003   0.000000   0.000003 (  0.000003)

       direct     rec1     rec2
 0 :        1        1        1
 1 :        1        1        1
 2 :        2        2        2
 3 :        5        5        5
 4 :       14       14       14
 5 :       42       42       42
 6 :      132      132      132
 7 :      429      429      429
 8 :     1430     1430     1430
 9 :     4862     4862     4862
10 :    16796    16796    16796
11 :    58786    58786    58786
12 :   208012   208012   208012
13 :   742900   742900   742900
14 :  2674440  2674440  2674440
15 :  9694845  9694845  9694845

D

import std.stdio, std.algorithm, std.bigint, std.functional, std.range;

auto product(R)(R r) { return reduce!q{a * b}(1.BigInt, r); }

const cats1 = sequence!((a, n) => iota(n+2, 2*n+1).product / iota(1, n+1).product)(1);

BigInt cats2a(in uint n) {
    alias mcats2a = memoize!cats2a;
    if (n == 0) return 1.BigInt;
    return n.iota.map!(i => mcats2a(i) * mcats2a(n - 1 - i)).sum;
}

const cats2 = sequence!((a, n) => n.cats2a);

const cats3 = recurrence!q{ (4*n - 2) * a[n - 1] / (n + 1) }(1.BigInt);

void main() {
    foreach (cats; TypeTuple!(cats1, cats2, cats3))
        cats.take(15).writeln;
}

Output:

[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440]
[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440]
[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440]

Delphi

See Pascal.

DuckDB

Works with: DuckDB version V1.0

In this entry we illustrate how to take advantage of DuckDB's support for polymorphic functions to compute C(n) using integer arithmetic for relatively small n, as well as floating point arithmetic for C(100).

# table of the first Catalan numbers up to catalan(n)
# using the DuckDB type determined by `one`, which should be
# 1 of an appropriate type:
create or replace function catalan_t_(mx, one) as table (
  with recursive cte(n,c) as (
    select 0 as n, one as c
    union all
    select n+1,
           2 * (2 * n + 1) * c / (n+2)
    from cte
    where n < mx
  )
  from cte
);

# In general, use UHUGEINT
create or replace function catalan_t(mx) as table (
  from catalan_t_(mx, 1::UHUGEINT)
);

# point-wise
create or replace function catalan(nn) as (
  select c
  from catalan_t(nn)
  offset nn
);

from catalan_t(15);

from catalan_t_(100, 1::DOUBLE) offset 100;

Output:

┌───────┬─────────┐
│   n   │    c    │
│ int32 │ int128  │
├───────┼─────────┤
│     0 │       1 │
│     1 │       1 │
│     2 │       2 │
│     3 │       5 │
│     4 │      14 │
│     5 │      42 │
│     6 │     132 │
│     7 │     429 │
│     8 │    1430 │
│     9 │    4862 │
│    10 │   16796 │
│    11 │   58786 │
│    12 │  208012 │
│    13 │  742900 │
│    14 │ 2674440 │
│    15 │ 9694845 │
├───────┴─────────┤
│     16 rows     │
└─────────────────┘
┌───────┬──────────────────────┐
│  100  │          c           │
│ int32 │        double        │
├───────┼──────────────────────┤
│  100  │ 8.96519947090131e+56 │
└───────┴──────────────────────┘

EasyLang

func catalan n .
   if n = 0
      return 1
   .
   return 2 * (2 * n - 1) * catalan (n - 1) div (1 + n)
.
for i = 0 to 14
   print catalan i
.

EchoLisp

This example is incorrect. Please fix the code and remove this message.

Details: series starts 1, 1, 2, ...

(lib 'sequences)
(lib 'bigint)
(lib 'math)

;; function definition
(define (C1 n) (/ (factorial (* n 2)) (factorial (1+ n)) (factorial n)))
(for ((i [1 .. 16])) (write (C1 i)))
    → 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 

;; using a recursive procedure with memoization
(define (C2 n) ;; ( Σ  ...)is the same as (sigma ..)
	(Σ (lambda(i) (* (C2 i) (C2 (- n i 1))))  0 (1- n)))
(remember 'C2 #(1)) ;; first term defined here

(for ((i [1 .. 16])) (write (C2 i)))
    → 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 


;; using procrastinators = infinite sequence
(define (catalan n acc) (/ (* acc 2 (1- (* 2 n))) (1+ n)))
(define C3 (scanl catalan 1 [1 ..]))
(take C3 15)
    → (1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845)
 

;; the same, using infix notation
(lib 'match)
(load 'infix.glisp)

(define (catalan n acc) ((2 * acc * ( 2 * n - 1)) / (n + 1)))
(define C3 (scanl catalan 1 [1 ..]))

(take C3 15)
    → (1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845)
;; or
(for ((c C3) (i 15)) (write c))
    → 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845

EDSAC order code

The Catalan numbers are here computed by the second method, as a sum of products. The program illustrates a difficulty with multiplying integers on the EDSAC, which was designed to work with fixed-point numbers in the range [-1, 1). When we store a 35-bit integer A, we are really storing A*(2^-34). As long as integer arithmetic is confined to addition and subtraction, this scaling can be ignored. But if we multiply two 35-bit integers A and B, the result is really A*B*(2^-68), and needs to be multiplied by 2^34 to get the same scaling as for A and B.

  [Calculation of Catalan numbers.
   EDSAC program, Initial Orders 2.]

  [Define where to store the list of Catalan numbers.]
            T   54 K  [store address in location 54, so that values
                       are accessed by code letter C (for Catalan)]
            P  200 F  [<------ address here]

  [Modification of library subroutine P7.
   Prints signed integer up to 10 digits, right-justified.
   54 storage locations; working position 4D.
   Must be loaded at an even address.
   Input: Number is at 0D.]
            T   56 K
  GKA3FT42@A47@T31@ADE10@T31@A48@T31@SDTDH44#@NDYFLDT4DS43@TF
  H17@S17@A43@G23@UFS43@T1FV4DAFG50@SFLDUFXFOFFFSFL4FT4DA49@T31@
  A1FA43@G20@XFP1024FP610D@524D!FO46@O26@XFO46@SFL8FT4DE39@

     [Main routine]
            T  120 K  [load at 120]
            G      K  [set @ (theta) to load address]
     [Variables]
      [0]   P      F  [index of Catalan number]
     [Constants]
      [1]   P    7 D  [maximum index required]
      [2]   P      D  [single-word 1]
      [3]   P    2 F  [to change addresses by 2]
      [4]   H     #C  [these 3 are used to manufacture EDSAC orders]
      [5]   T     #C
      [6]   V     #C
      [7]   K 4096 F  [(1) add to change T order into H order
                       (2) teleprinter null]
      [8]   #      F  [figures shift]
      [9]   !      F  [space]
     [10]   @      F  [carriage return]
     [11]   &      F  [line feed]

           [Enter with acc = 0]
     [12]   O    8 @  [set teleprinter to figures]
            T    4 D  [clear 5F and sandwich bit]
            A    2 @  [load single-word 1]
            T    4 F  [store as double word at 4D; clear acc]
           [Here with index in acc, Catalan number in 4D]
     [16]   U      @  [store index]
            L    1 F  [times 4 by shifting]
            A    5 @  [make T order to store Catalan number]
            U   27 @  [plant in code]
            A    7 @  [make H order with same address]
            U   45 @  [plant in code]
            S   47 @  [make A order with same address]
            T   34 @  [plant in code]
            A    6 @  [load V order for start of list]
            T   46 @  [plant in code]
            A    4 D  [Catalan number from temp store]
     [27]   T     #C  [store in list (manufactured order)]
            T      D  [clear 1F and sandwich bit]
            A      @  [load single-word index]
            T      F  [store as double word at 0D]
     [31]   A   31 @  [for return from print subroutine]
            G   56 F  [print index]
            O    9 @  [followed by space]
     [34]   A     #C  [load Catalan number (manufactured order)]
            T      D  [to 0D for printing]
     [36]   A   36 @  [for return from print subroutine]
            G   56 F  [print Catalan number]
            O   10 @  [followed by new line]
            O   11 @
            T    4 D  [clear partial sum]
            A      @  [load index]
            S    1 @  [reached the maximum?]
            E   64 @  [if so, jump to exit]
            [Inner loop to compute sum of products C{i}*C(n-1}]
     [44]   T      F  [clear acc]
     [45]   H     #C  [C{n-i} to mult reg (manufactured order)]
     [46]   V     #C  [acc := C{i}*C{n-i} (manufactiured order)]
           [Multiply product by 2^34 (see preamble). The 'L F' order is
            also exploited above to convert an H order into an A order.]
     [47]   L      F  [shift acc left by 13 (the maximum available)]
            L      F  [shift 13 more]
            L   64 F  [shift 8 more, total 34]
            A    4 D  [add partial sum]
            T    4 D  [update partial sum]
            A   46 @  [inc i in V order]
            A    3 @
            T   46 @
            A   45 @  [dec (n - i) in H order]
            S    3 @
            U   45 @
            S    4 @  [is (n - i) now negative?]
            E   44 @  [if not, loop back]
           [Here with latest Catalan number in temp store 4D]
            T      F  [clear acc]
            A      @  [load index]
            A    2 @  [add 1]
            E   16 @  [back to start of outer loop]
     [64]   O    7 @  [exit; print null to flush teleprinter buffer]
            Z      F  [stop]
            E   12 Z  [define entry point]
            P      F  [acc = 0 on entry]

Output:

          0           1
          1           1
          2           2
          3           5
          4          14
          5          42
          6         132
          7         429
          8        1430
          9        4862
         10       16796
         11       58786
         12      208012
         13      742900
         14     2674440
         15     9694845

Eiffel

class
	APPLICATION

create
	make

feature {NONE}

	make
		do
			across
				0 |..| 14 as c
			loop
				io.put_double (nth_catalan_number (c.item))
				io.new_line
			end
		end

	nth_catalan_number (n: INTEGER): DOUBLE
			--'n'th number in the sequence of Catalan numbers.
		require
			n_not_negative: n >= 0
		local
			s, t: DOUBLE
		do
			if n = 0 then
				Result := 1.0
			else
				t := 4 * n.to_double - 2
				s := n.to_double + 1
				Result := t / s * nth_catalan_number (n - 1)
			end
		end

end

Output:

Elixir

Translation of: Erlang

defmodule Catalan do
  def cat(n), do: div( factorial(2*n), factorial(n+1) * factorial(n) )
  
  defp factorial(n), do: fac1(n,1)
  
  defp fac1(0, acc), do: acc
  defp fac1(n, acc), do: fac1(n-1, n*acc)
  
  def cat_r1(0), do: 1
  def cat_r1(n), do: Enum.sum(for i <- 0..n-1, do: cat_r1(i) * cat_r1(n-1-i))
  
  def cat_r2(0), do: 1
  def cat_r2(n), do: div(cat_r2(n-1) * 2 * (2*n - 1), n + 1)
  
  def test do
    range = 0..14
    :io.format "Directly:~n~p~n",            [(for n <- range, do: cat(n))]
    :io.format "1st recusive method:~n~p~n", [(for n <- range, do: cat_r1(n))]
    :io.format "2nd recusive method:~n~p~n", [(for n <- range, do: cat_r2(n))]
  end
end

Catalan.test

Output:

Directly:
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440]
1st recusive method:
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440]
2nd recusive method:
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440]

Erlang

-module(catalan).

-export([test/0]).

cat(N) -> 
   factorial(2 * N) div (factorial(N+1) * factorial(N)).

factorial(N) -> 
   fac1(N,1).

fac1(0,Acc) -> 
   Acc; 
fac1(N,Acc) -> 
   fac1(N-1, N * Acc).
 
cat_r1(0) ->
   1;
cat_r1(N) ->
   lists:sum([cat_r1(I)*cat_r1(N-1-I) || I <- lists:seq(0,N-1)]).
   
cat_r2(0) ->
   1;
cat_r2(N) ->
   cat_r2(N - 1) * (2 * ((2 * N) - 1)) div (N + 1).

test() -> 
    TestList = lists:seq(0,14),
    io:format("Directly:\n~p\n",[[cat(N) || N <- TestList]]),
    io:format("1st recusive method:\n~p\n",[[cat_r1(N) || N <- TestList]]),
    io:format("2nd recusive method:\n~p\n",[[cat_r2(N) || N <- TestList]]).

Output:

Directly:
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440]
1st recusive method:
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440]
2nd recusive method:
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440]

ERRE

PROGRAM CATALAN

PROCEDURE CATALAN(N->RES)
   RES=1
   FOR I=1 TO N DO
      RES=RES*2*(2*I-1)/(I+1)
   END FOR
END PROCEDURE

BEGIN
   FOR N=0 TO 15 DO
      CATALAN(N->RES)    
      PRINT(N;"=";RES)
   END FOR
END PROGRAM

Output:

 0 = 1
 1 = 1
 2 = 2
 3 = 5
 4 = 14
 5 = 42
 6 = 132
 7 = 429
 8 = 1430
 9 = 4862
 10 = 16796
 11 = 58786
 12 = 208012
 13 = 742900
 14 = 2674440
 15 = 9694845

Euphoria

--Catalan number task from Rosetta Code wiki
--User:Lnettnay

--function from factorial task
function factorial(integer n)
atom f = 1
while n > 1 do
        f *= n
        n -= 1
end while

return f
end function

function catalan(integer n)  
atom numerator = factorial(2 * n)
atom denominator = factorial(n+1)*factorial(n)
return numerator/denominator
end function
  
for i = 0 to 15 do
        ? catalan(i)
end for

Output:

F#

Seq.unfold(fun (c,n) -> let cc = 2*(2*n-1)*c/(n+1) in Some(c,(cc,n+1))) (1,1) |> Seq.take 15 |> Seq.iter (printf "%i, ")

Output:

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440,

Factor

The first method:

USING: kernel math math.combinatorics prettyprint ;

: catalan ( n -- n ) [ 1 + recip ] [ 2 * ] [ nCk * ] tri ;

15 [ catalan . ] each-integer

Output:

The last method, memoized by using arrays.

USING: kernel math prettyprint sequences ;

: next ( seq -- newseq )
  [ ] [ last ] [ length ] tri
  [ 2 * 1 - 2 * ] [ 1 + ] bi /
  * suffix ;

: Catalan ( n -- seq )  V{ 1 } swap 1 - [ next ] times ;

15 Catalan .

Output:

Similar to above.

Fantom

This example is incorrect. Please fix the code and remove this message.

Details: series starts 1, 1, 2, ...

class Main
{
  static Int factorial (Int n)
  {
    Int res := 1
    if (n>1)
      (2..n).each |i| { res *= i }
    return res
  }

  static Int catalanA (Int n)
  { 
    return factorial(2*n)/(factorial(n+1) * factorial(n))
  }

  static Int catalanB (Int n)
  {
    if (n == 0)
    {
      return 1
    }
    else
    {
      sum := 0
      n.times |i| { sum += catalanB(i) * catalanB(n-1-i) } 
      return sum
    }
  }

  static Int catalanC (Int n)
  {
    if (n == 0)
    {
      return 1
    }
    else
    {
      return catalanC(n-1)*2*(2*n-1)/(n+1)
    }
  }

  public static Void main ()
  {
    (1..15).each |n|
    {
      echo (n.toStr.padl(4) + 
            catalanA(n).toStr.padl(10) +
            catalanB(n).toStr.padl(10) +
            catalanC(n).toStr.padl(10))
    }
  }
}

22! exceeds the range of Fantom's Int class, so the first technique fails afer n=10

   1         1         1         1
   2         2         2         2
   3         5         5         5
   4        14        14        14
   5        42        42        42
   6       132       132       132
   7       429       429       429
   8      1430      1430      1430
   9      4862      4862      4862
  10     16796     16796     16796
  11       -65     58786     58786
  12        -2    208012    208012
  13         0    742900    742900
  14        97   2674440   2674440
  15        -2   9694845   9694845

Fermat

Func Catalan(n)=(2*n)!/((n+1)!*n!).;
for i=1 to 15 do !Catalan(i);!' ' od;

Output:

1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845

Forth

: catalan ( n -- )  1 swap 1+ 1 do dup cr .  i 2* 1- 2*  i 1+ */ loop drop ;

Fortran

Works with: Fortran version 90 and later

program main
  !=======================================================================================
  implicit none

  !=== Local data
  integer                      :: n

  !=== External procedures
  double precision, external   :: catalan_numbers         
  
  !=== Execution =========================================================================

  write(*,'(1x,a)')'==============='
  write(*,'(5x,a,6x,a)')'n','c(n)'
  write(*,'(1x,a)')'---------------'

  do n = 0, 14
    write(*,'(1x,i5,i10)') n, int(catalan_numbers(n))
  enddo

  write(*,'(1x,a)')'==============='

  !=======================================================================================
end program main
!BL
!BL
!BL
double precision recursive function catalan_numbers(n) result(value)
  !=======================================================================================
  implicit none

  !=== Input, ouput data
  integer, intent(in)          :: n

  !=== Execution =========================================================================

  if ( n .eq. 0 ) then
    value = 1
  else 
    value = ( 2.0d0 * dfloat(2 * n - 1) / dfloat( n + 1 ) ) * catalan_numbers(n-1)
  endif

  !=======================================================================================
end function catalan_numbers

Output:

 ===============
     n      c(n)
 ---------------
     0         1
     1         1
     2         2
     3         5
     4        14
     5        42
     6       132
     7       429
     8      1430
     9      4862
    10     16796
    11     58786
    12    208012
    13    742900
    14   2674440
 ===============

Frink

Frink includes efficient algorithms for calculating arbitrarily-large binomial coefficients and automatically caches factorials.

catalan[n] := binomial[2n,n]/(n+1)
for n = 0 to 15
   println[catalan[n]]

FunL

import integers.choose
import util.TextTable

def
  catalan( n ) = choose( 2n, n )/(n + 1)

  catalan2( n ) = product( (n + k)/k | k <- 2..n )

  catalan3( 0 ) = 1
  catalan3( n ) = 2*(2n - 1)/(n + 1)*catalan3( n - 1 )

t = TextTable()
t.header( 'n', 'definition', 'product', 'recursive' )
t.line()

for i <- 1..4
  t.rightAlignment( i )

for i <- 0..15
  t.row( i, catalan(i), catalan2(i), catalan3(i) )
  
println( t )

Output:

+----+------------+---------+-----------+
| n  | definition | product | recursive |
+----+------------+---------+-----------+
|  0 |          1 |       1 |         1 |
|  1 |          1 |       1 |         1 |
|  2 |          2 |       2 |         2 |
|  3 |          5 |       5 |         5 |
|  4 |         14 |      14 |        14 |
|  5 |         42 |      42 |        42 |
|  6 |        132 |     132 |       132 |
|  7 |        429 |     429 |       429 |
|  8 |       1430 |    1430 |      1430 |
|  9 |       4862 |    4862 |      4862 |
| 10 |      16796 |   16796 |     16796 |
| 11 |      58786 |   58786 |     58786 |
| 12 |     208012 |  208012 |    208012 |
| 13 |     742900 |  742900 |    742900 |
| 14 |    2674440 | 2674440 |   2674440 |
| 15 |    9694845 | 9694845 |   9694845 |
+----+------------+---------+-----------+

Fōrmulæ

Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition.

Programs in Fōrmulæ are created/edited online in its website.

In this page you can see and run the program(s) related to this task and their results. You can also change either the programs or the parameters they are called with, for experimentation, but remember that these programs were created with the main purpose of showing a clear solution of the task, and they generally lack any kind of validation.

Solution

Direct definition

Direct definition (alternative)

The expression ${\displaystyle {\frac {(2n)!}{(n+1)!\,n!}}}$ turns out to be equals to ${\displaystyle \prod _{k=2}^{n}{\frac {n+k}{k}}}$

(same result)

No directly defined

Recursive definitions are easy to write, but extremely inefficient (specially the first one).

Because a list is intended to be get, the list of previous values can be used as a form of memoization, avoiding recursion.

The next function make use of the "second" form of recursive definition (without recursion):

(same result)

GAP

Catalan1 := n -> Binomial(2*n, n) - Binomial(2*n, n - 1);

Catalan2 := n -> Binomial(2*n, n)/(n + 1);

Catalan3 := function(n)
    local k, c;
    c := 1;
    k := 0;
    while k < n do
        k := k + 1;
        c := 2*(2*k - 1)*c/(k + 1);
    od;
    return c;
end;

Catalan4_memo := [1];
Catalan4 := function(n)
    if not IsBound(Catalan4_memo[n + 1]) then
        Catalan4_memo[n + 1] := Sum([0 .. n - 1], i -> Catalan4(i)*Catalan4(n - 1 - i));
    fi;
    return Catalan4_memo[n + 1];
end;


# The first fifteen: 0 to 14 !
List([0 .. 14], Catalan1);
List([0 .. 14], Catalan2);
List([0 .. 14], Catalan3);
List([0 .. 14], Catalan4);
# Same output for all four:
# [ 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440 ]

Go

Direct:

package main

import (
    "fmt"
    "math/big"
)

func main() {
    var b, c big.Int
    for n := int64(0); n < 15; n++ {
        fmt.Println(c.Div(b.Binomial(n*2, n), c.SetInt64(n+1)))
    }
}

Output:

Recursive (alternative):

package main

import (
        "fmt"
        "math/big"
)

func c(n int64) *big.Int {
        if n == 0 {
                return big.NewInt(1)
        } else {
                var t1, t2, t3, t4, t5, t6 big.Int
                t1.Mul(big.NewInt(2), big.NewInt(n))
                t2.Sub(&t1, big.NewInt(1))
                t3.Mul(big.NewInt(2), &t2)
                t4.Add(big.NewInt(n), big.NewInt(1))
                t5.Mul(&t3, c(n-1))
                t6.Div(&t5, &t4)
                return &t6
        }
}

func main() {
        for n := int64(1); n < 16; n++ {
                fmt.Println(c(n))
        }
}

Output:

Groovy

class Catalan
{
 public static void main(String[] args)
  {
    BigInteger N = 15;
    BigInteger k,n,num,den;
    BigInteger  catalan;
      print(1);
       for(n=2;n<=N;n++)
          {
            num = 1;
            den = 1;
              for(k=2;k<=n;k++)
                 {
                    num = num*(n+k);
                    den = den*k;
                    catalan = num/den; 
                 }
            println(catalan);
          }
    
  }
}

Output:

Harbour

PROCEDURE Main()
   LOCAL i

   FOR i := 0 to 15
      ? PadL( i, 2 ) + ": " + hb_StrFormat("%d", Catalan( i ))
   NEXT

   RETURN

STATIC FUNCTION Catalan( n )
   LOCAL i, nCatalan := 1

   FOR i := 1 TO n 
      nCatalan := nCatalan * 2 * (2 * i - 1) / (i + 1)
   NEXT

   RETURN nCatalan

Output:

Haskell

-- Three infinite lists, corresponding to the three
-- definitions in the problem statement.

cats1 :: [Integer]
cats1 =
  (div . product . (enumFromTo . (2 +) <*> (2 *)))
    <*> (product . enumFromTo 1) <$> [0 ..]

cats2 :: [Integer]
cats2 =
  1 :
  fmap
    (\n -> sum (zipWith (*) (reverse (take n cats2)) cats2))
    [1 ..]

cats3 :: [Integer]
cats3 =
  scanl
    (\c n -> c * 2 * (2 * n - 1) `div` succ n)
    1
    [1 ..]

main :: IO ()
main = mapM_ (print . take 15) [cats1, cats2, cats3]

Output:

[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440]
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440]
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440]

Isabelle

Works with: Isabelle version 2024

Adapted from the corresponding entry in the Archive of Formal Proofs

theory Catalan_Numbers
imports
  "HOL-Computational_Algebra.Computational_Algebra" "HOL-Library.Code_Target_Numeral"
begin

(* recursive definition *)
fun catalan :: "nat ⇒ nat" where
  "catalan 0 = 1"
| [simp del]: "catalan (Suc n) = (∑i≤n. catalan i * catalan (n - i))"

(* the generating function F(X) = ∑n. C(n)X^n of the Catalan numbers 
   as a formal power series *)
definition fps_catalan :: "real fps" where "fps_catalan = Abs_fps (real ∘ catalan)"

(* C(X) satisfies the identity C(X) = 1 + X C(X)^2 *)
lemma fps_catalan_recurrence:
  "fps_catalan = 1 + fps_X * fps_catalan^2"
proof (rule fps_ext)
  fix n :: nat
  show "fps_nth fps_catalan n = fps_nth (1 + fps_X * fps_catalan^2) n"
    by (cases n) (simp_all add: fps_square_nth catalan.simps(2) fps_catalan_def)
qed

(* Solving for C we get C(X) = (1 - sqrt(1 - 4x)) / (2x) *)
lemma fps_catalan_fps_binomial:
  "fps_catalan = (1/2 * (1 - (fps_binomial (1/2) oo (-4*fps_X)))) / fps_X"
proof -
  let ?F = "fps_catalan"
  have "fps_X * (1 + fps_X * ?F^2) = fps_X * ?F"
    by (simp only: fps_catalan_recurrence [symmetric])
  hence "(1 / 2 - fps_X * ?F)⇧2 = - fps_X + 1 / 4"
    by (simp add: algebra_simps power2_eq_square fps_numeral_simps)
  also have "… = (1/2 * (fps_binomial (1/2) oo (-4*fps_X)))^2"
    by (simp add: power_mult_distrib div_power fps_binomial_1 fps_binomial_power
                  fps_compose_power fps_compose_add_distrib ring_distribs)
  finally have "1/2 - fps_X * ?F = 1/2 * (fps_binomial (1/2) oo (-4*fps_X))"
    by (rule fps_power_eqD) simp_all
  hence "fps_X*?F = 1/2 * (1 - (fps_binomial (1/2) oo (-4*fps_X)))" by algebra
  thus ?thesis
    by (metis fps_X_neq_zero nonzero_mult_div_cancel_left)
qed

(* A closed form for the Catalan numbers in terms of the generalised binomial coefficients
   can be read off directly from this solution for C(x), namely:
   c_n = 2 (-4)^n B(1/2, n+1) *)
lemma catalan_closed_form_gbinomial:
  "real (catalan n) = 2 * (-4) ^ n * ((1/2) gchoose (n+1))"
proof -
  have "(catalan n :: real) = fps_nth fps_catalan n"
    by (simp add: fps_catalan_def)
  also have "… = 2 * (-4) ^ n * ((1/2) gchoose (n+1))"
    by (subst fps_catalan_fps_binomial)
       (simp add: fps_div_fps_X_nth numeral_fps_const fps_compose_linear)
  finally show ?thesis .
qed

(* Simplifying the generalised binomial coefficients to regular ones we get
   another closed form: c_n = B(2n, n) / (n+1) *)
lemma catalan_closed_form':
  "catalan n * (n + 1) = (2*n) choose n"
proof -
  have "real ((2*n) choose n) = fact (2*n) / (fact n)^2"
    by (simp add: binomial_fact power2_eq_square)
  also have "(fact (2*n) :: real) = 4^n * pochhammer (1 / 2) n * fact n"
    by (simp add: fact_double power_mult)
  also have "… / (fact n)^2 / real (n+1) = real (catalan n)"
    by (simp add: catalan_closed_form_gbinomial gbinomial_pochhammer pochhammer_rec
          field_simps power2_eq_square power_mult_distrib [symmetric] del: of_nat_Suc)
  finally have "real (catalan n * (n+1)) = real ((2*n) choose n)" by (simp add: field_simps)
  thus ?thesis
    by linarith
qed

theorem catalan_closed_form: "catalan n = ((2*n) choose n) div (n + 1)"
  by (subst catalan_closed_form' [symmetric], subst div_mult_self_is_m) auto

(* With this, it is now also easy to derive a linear recurrence of order 1
   (with polynomial coefficients): *)
lemma catalan_rec':
  "(n + 2) * catalan (n + 1) = 2 * (2 * n + 1) * catalan n"
proof (cases "n > 0")
  case True
  have "real (catalan (n + 1) * (n + 1 + 1)) =
           real (catalan n * (n + 1)) * 2 * real (2 * n + 1) / real (n + 1)"
    using True unfolding catalan_closed_form' 
    by (simp add: fact_reduce binomial_fact divide_simps) (auto simp: algebra_simps)?
  also have "… = real (2 * (2 * n + 1) * catalan n)"
    by (simp del: of_nat_Suc add: divide_simps) (auto simp: algebra_simps)?
  also have "catalan (n + 1) * (n + 1 + 1) = (n + 2) * catalan (n + 1)"
    by simp
  finally show ?thesis
    by linarith
qed (auto simp: catalan.simps(2))

theorem catalan_rec:
  "catalan (Suc n) = (catalan n * (2*(2*n+1))) div (n+2)"
  by (subst mult.commute, subst catalan_rec' [symmetric], subst div_mult_self1_is_m) auto

(* To make the computation more efficient, we now derive a simple
   tail-recursive version of this *)
function catalan_aux where [simp del]:
  "catalan_aux n k acc =
     (if k ≥ n then acc else catalan_aux n (Suc k) ((acc * (2*(2*k+1))) div (k+2)))"
  by auto
termination by (relation "Wellfounded.measure (λ(a,b,_). a - b)") simp_all

lemma catalan_aux_correct:
  assumes "k ≤ n"
  shows   "catalan_aux n k (catalan k) = catalan n"
using assms
proof (induction n k "catalan k" rule: catalan_aux.induct)
  case (1 n k)
  show ?case
  proof (cases "k < n")
    case True
    hence "catalan_aux n k (catalan k) = catalan_aux n (Suc k) (catalan (Suc k))"
      by (subst catalan_rec; subst catalan_aux.simps) auto
    with 1 True show ?thesis by (simp add: catalan_rec)
  qed (insert "1.prems", simp_all add: catalan_aux.simps)
qed

lemma catalan_code [code]: "catalan n = catalan_aux n 0 1"
  using catalan_aux_correct[of 0 n] by simp

end

Output:

theory Catalan_Numbers
value "map catalan [0..<15]"
(* Output:
  "[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440]"
  :: "nat list"
*)

Icon and Unicon

procedure main()
every writes(catalan(0 to 14)," ")
end

procedure catalan(n) # return catalan(n) or fail
static M
initial M := table()
n=0 & return 1

if n > 0 then 
   return (n = 1) | \M[n] | ( M[n] := (2*(2*n-1)*catalan(n-1))/(n+1))
end

Output:

1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440

J

   ((! +:) % >:) i.15x
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440

Java

Replace double inexact computations with BigInteger implementation.

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class CatlanNumbers {

    public static void main(String[] args) {
        Catlan f1 = new Catlan1();
        Catlan f2 = new Catlan2();
        Catlan f3 = new Catlan3();
        System.out.printf("           Formula 1     Formula 2     Formula 3%n");
        for ( int n = 0 ; n <= 15 ; n++ ) {
             System.out.printf("C(%2d) = %,12d  %,12d  %,12d%n", n, f1.catlin(n), f2.catlin(n), f3.catlin(n));
        }
    }
    
    private static interface Catlan {
        public BigInteger catlin(long n);
    }
    
    private static class Catlan1 implements Catlan {

        //  C(n) = (2n)! / (n+1)!n!
        @Override
        public BigInteger catlin(long n) {
            List<Long> numerator = new ArrayList<>();
            for ( long k = n+2 ; k <= 2*n ; k++ ) {
                numerator.add(k);
            }
            
            List<Long> denominator = new ArrayList<>();
            for ( long k = 2 ; k <= n ; k++ ) {
                denominator.add(k);
            }
            
            for ( int i = numerator.size()-1 ; i >= 0  ; i-- ) {
                for ( int j = denominator.size()-1 ; j >= 0  ; j-- ) {
                    if ( denominator.get(j) == 1 ) {
                        continue;
                    }
                    if ( numerator.get(i) % denominator.get(j) == 0 ) {
                        long val = numerator.get(i) / denominator.get(j);
                        numerator.set(i, val);
                        denominator.remove(denominator.get(j));
                        if ( val == 1 ) {
                            break;
                        }
                    }
                }
            }

            BigInteger catlin = BigInteger.ONE;
            for ( int i = 0 ; i < numerator.size() ; i++ ) {
                catlin = catlin.multiply(BigInteger.valueOf(numerator.get(i)));
            }
            for ( int i = 0 ; i < denominator.size() ; i++ ) {
                catlin = catlin.divide(BigInteger.valueOf(denominator.get(i)));
            }
            return catlin;
        }        
    }
    
    private static class Catlan2 implements Catlan {

        private static Map<Long,BigInteger> CACHE = new HashMap<>();
        static {
            CACHE.put(0L, BigInteger.ONE);
        }
        
        //  C(0) = 1, C(n+1) = sum(i=0..n,C(i)*C(n-i))
        @Override
        public BigInteger catlin(long n) {
            if ( CACHE.containsKey(n) ) {
                return CACHE.get(n);
            }
            BigInteger catlin = BigInteger.ZERO;
            n--;
            for ( int i = 0 ; i <= n ; i++ ) {
                //System.out.println("n = " + n + ", i = " + i + ", n-i = " + (n-i));
                catlin = catlin.add(catlin(i).multiply(catlin(n-i)));
            }
            CACHE.put(n+1, catlin);
            return catlin;
        }
    }
    
    private static class Catlan3 implements Catlan {

        private static Map<Long,BigInteger> CACHE = new HashMap<>();
        static {
            CACHE.put(0L, BigInteger.ONE);
        }
        
        //  C(0) = 1, C(n+1) = 2*(2n-1)*C(n-1)/(n+1)
        @Override
        public BigInteger catlin(long n) {
            if ( CACHE.containsKey(n) ) {
                return CACHE.get(n);
            }
            BigInteger catlin = BigInteger.valueOf(2).multiply(BigInteger.valueOf(2*n-1)).multiply(catlin(n-1)).divide(BigInteger.valueOf(n+1));
            CACHE.put(n, catlin);
            return catlin;
        }
    }

}

Output:

           Formula 1     Formula 2     Formula 3
C( 0) =            1             1             1
C( 1) =            1             1             1
C( 2) =            2             2             2
C( 3) =            5             5             5
C( 4) =           14            14            14
C( 5) =           42            42            42
C( 6) =          132           132           132
C( 7) =          429           429           429
C( 8) =        1,430         1,430         1,430
C( 9) =        4,862         4,862         4,862
C(10) =       16,796        16,796        16,796
C(11) =       58,786        58,786        58,786
C(12) =      208,012       208,012       208,012
C(13) =      742,900       742,900       742,900
C(14) =    2,674,440     2,674,440     2,674,440
C(15) =    9,694,845     9,694,845     9,694,845

JavaScript

Procedural

<html><head><title>Catalan</title></head>
<body><pre id='x'></pre><script type="application/javascript">
function disp(x) {
	var e = document.createTextNode(x + '\n');
	document.getElementById('x').appendChild(e);
}

var fc = [], c2 = [], c3 = [];
function fact(n) { return fc[n] ? fc[n] : fc[n] = (n ? n * fact(n - 1) : 1); }
function cata1(n) { return Math.floor(fact(2 * n) / fact(n + 1) / fact(n) + .5); }
function cata2(n) {
	if (n == 0) return 1;
	if (!c2[n]) {
		var s = 0;
		for (var i = 0; i < n; i++) s += cata2(i) * cata2(n - i - 1);
		c2[n] = s;
	}
	return c2[n];
}
function cata3(n) {
	if (n == 0) return 1;
	return c3[n] ? c3[n] : c3[n] = (4 * n - 2) * cata3(n - 1) / (n + 1);
}

disp("       meth1   meth2   meth3");
for (var i = 0; i <= 15; i++)
	disp(i + '\t' + cata1(i) + '\t' + cata2(i) + '\t' + cata3(i));

</script></body></html>

Output:

       meth1   meth2   meth3
0	1	1	1
1	1	1	1
2	2	2	2
3	5	5	5
4	14	14	14
5	42	42	42
6	132	132	132
7	429	429	429
8	1430	1430	1430
9	4862	4862	4862
10	16796	16796	16796
11	58786	58786	58786
12	208012	208012	208012
13	742900	742900	742900
14	2674440	2674440	2674440
15	9694845	9694845	9694845

Functional

Defining an infinite list:

(() => {
    "use strict";

    // ----------------- CATALAN NUMBERS -----------------

    // catalansDefinitionThree :: [Int]
    const catalansDefinitionThree = () =>
        // An infinite sequence of Catalan numbers.
        scanlGen(
            c => n => Math.floor(
                (2 * c * pred(2 * n)) / succ(n)
            )
        )(1)(
            enumFrom(1)
        );


    // ---------------------- TEST -----------------------
    // main :: IO ()
    const main = () =>
        take(15)(
            catalansDefinitionThree()
        );


    // --------------------- GENERIC ---------------------

    // enumFrom :: Enum a => a -> [a]
    const enumFrom = function* (n) {
        // An infinite sequence of integers,
        // starting with n.
        let v = n;

        while (true) {
            yield v;
            v = 1 + v;
        }
    };


    // pred :: Int -> Int
    const pred = x =>
        x - 1;


    // scanlGen :: (b -> a -> b) -> b -> Gen [a] -> [b]
    const scanlGen = f =>
        // The series of interim values arising
        // from a catamorphism over an infinite list.
        startValue => function* (gen) {
            let
                a = startValue,
                x = gen.next();

            yield a;
            while (!x.done) {
                a = f(a)(x.value);
                yield a;
                x = gen.next();
            }
        };


    // succ :: Int -> Int
    const succ = x =>
        1 + x;


    // take :: Int -> [a] -> [a]
    // take :: Int -> String -> String
    const take = n =>
        // The first n elements of a list,
        // string of characters, or stream.
        xs => Array.from({
            length: n
        }, () => {
            const x = xs.next();

            return x.done ? [] : [x.value];
        }).flat();


    // MAIN ---
    return JSON.stringify(main(), null, 2);
})();

Output:

jq

Works with: jq version 1.4

The recursive formula for C(n) in terms of C(n-1) lends itself directly to efficient implementations in jq so in this section, that formula is used (a) to define a function for computing a single Catalan number; (b) to define a function for generating a sequence of Catalan numbers; and (c) to write a single expression for generating a sequence of Catalan numbers using jq's builtin "recurse/1" filter.

Compute a single Catalan number

def catalan:
  if . == 0 then 1
  elif . < 0 then error("catalan is not defined on \(.)")
  else (2 * (2*. - 1) * ((. - 1) | catalan)) / (. + 1)
  end;

Example 1

(range(0; 16), 100) as $i | $i | catalan | [$i, .]

Output:

$ jq -M -n -c -f Catalan_numbers.jq
[0,1]
[1,1]
[2,2]
[3,5]
[4,14]
[5,42]
[6,132]
[7,429]
[8,1430]
[9,4862]
[10,16796]
[11,58786]
[12,208012]
[13,742900]
[14,2674440]
[15,9694845]
[100,8.96519947090131e+56]

Generate a sequence of Catalan numbers

def catalan_series(max):
  def _catalan: # state: [n, catalan(n)]
    if .[0] > max then empty 
    else .,
      ((.[0] + 1) as $n | .[1] as $cp
       | [$n,  (2 * (2*$n - 1) * $cp) / ($n + 1) ] | _catalan)
    end;
  [0,1] | _catalan;

Example 2:

catalan_series(15)

Output:

As above for 0 to 15.

An expression to generate Catalan numbers

  [0,1]
  | recurse( if .[0] == 15 then empty
             else .[1] as $c | (.[0] + 1) | [ ., (2 * (2*. - 1) * $c) / (. + 1) ] 
             end )

Output:

As above for 0 to 15.

Julia

Works with: Julia version 0.6

catalannum(n::Integer) = binomial(2n, n) ÷ (n + 1)

@show catalannum.(1:15)
@show catalannum(big(100))

Output:

catalannum.(1:15) = [1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]
catalannum(big(100)) = 896519947090131496687170070074100632420837521538745909320

(In the second example, we have used arbitrary-precision integers to avoid overflow for large Catalan numbers.)

K

  catalan: {_{*/(x-i)%1+i:!y-1}[2*x;x+1]%x+1}
  catalan'!:15
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440

Kotlin

Works with: Java version 1.7.0

Works with: Kotlin version 1.1.4

abstract class Catalan {
    abstract operator fun invoke(n: Int) : Double

    protected val m = mutableMapOf(0 to 1.0)
}

object CatalanI : Catalan() {
    override fun invoke(n: Int): Double {
        if (n !in m)
            m[n] = Math.round(fact(2 * n) / (fact(n + 1) * fact(n))).toDouble()
        return m[n]!!
    }

    private fun fact(n: Int): Double {
        if (n in facts)
            return facts[n]!!
        val f = n * fact(n -1)
        facts[n] = f
        return f
    }

    private val facts = mutableMapOf(0 to 1.0, 1 to 1.0, 2 to 2.0)
}

object CatalanR1 : Catalan() {
    override fun invoke(n: Int): Double {
        if (n in m)
            return m[n]!!

        var sum = 0.0
        for (i in 0..n - 1)
            sum += invoke(i) * invoke(n - 1 - i)
        sum = Math.round(sum).toDouble()
        m[n] = sum
        return sum
    }
}

object CatalanR2 : Catalan() {
    override fun invoke(n: Int): Double {
        if (n !in m)
            m[n] = Math.round(2.0 * (2 * (n - 1) + 1) / (n + 1) * invoke(n - 1)).toDouble()
        return m[n]!!
    }
}

fun main(args: Array<String>) {
    val c = arrayOf(CatalanI, CatalanR1, CatalanR2)
    for(i in 0..15) {
        c.forEach { print("%9d".format(it(i).toLong())) }
        println()
    }
}

Output:

        1        1        1
        1        1        1
        2        2        2
        5        5        5
       14       14       14
       42       42       42
      132      132      132
      429      429      429
     1430     1430     1430
     4862     4862     4862
    16796    16796    16796
    58786    58786    58786
   208012   208012   208012
   742900   742900   742900
  2674440  2674440  2674440
  9694845  9694845  9694845

Lambdatalk

Translation of: Javascript

1) catalan1

{def catalan1
 {def fac {lambda {:n} {* {S.serie 1 :n}}}}
 {lambda {:n}
  {floor {+ {/ {fac {* 2 :n}} {fac {+ :n 1}} {fac :n}} 0.5}}}}
-> catalan1

{S.map catalan1 {S.serie 1 15}}
->  1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845

2) catalan2

{def catalan2
 {def catalan2.sum
  {lambda {:n :a :s :i}
   {if {= :i :n}
    then {A.set! :n :s :a}
    else {catalan2.sum :n 
                    :a 
                    {+ :s {* {catalan2.loop :i :a}
                             {catalan2.loop {- :n :i 1} :a}}} 
                    {+ :i 1}} }}}
 {def catalan2.loop
  {lambda {:n :a}
   {if {= :n 0}
    then 1
    else {if {W.equal? {A.get :n :a} undefined}
    then {A.get :n {catalan2.sum :n :a 0 0}}
    else {A.get :n :a} }}}}
 {lambda {:n}
  {catalan2.loop :n {A.new}} }}
-> catalan2

{S.map catalan2 {S.serie 0 15}}
-> 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845

3) catalan3

{def catalan3
 {def catalan3.loop
  {lambda {:n :a}
   {if {= :n 0}
    then 1
    else {if {W.equal? {A.get :n :a} undefined}
    then {A.get :n
                {A.set! :n 
                        {/ {* {- {* 4 :n} 2}
                              {catalan3.loop {- :n 1} :a}}
                           {+ :n 1}}
                        :a}}
    else {A.get :n :a}
 }}}}
 {lambda {:n}
  {catalan3.loop :n {A.new}}}}
-> catalan3

{S.map catalan3 {S.serie 0 15}}
-> 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845

4) Alternative for a vertical diplay

{style 
 td { text-align:right;
      font-family:monospace; 
    }
}

{table
 {tr {td} {td cat1} {td cat2} {td cat3}}
 {S.map {lambda {:i} {tr {td :i}
                         {td {catalan1 :i}}
                         {td {catalan2 :i}}
                         {td {catalan3 :i}}}} 
        {S.serie 0 15}} 
}

	   cat1    cat2    cat3
 0 	      1 	  1 	  1
 1 	      1 	  1 	  1
 2 	      2 	  2 	  2
 3 	      5 	  5 	  5
 4 	     14 	 14 	 14
 5 	     42 	 42 	 42
 6 	    132 	132 	132
 7 	    429 	429 	429
 8 	   1430    1430    1430
 9 	   4862    4862    4862
10 	  16796   16796   16796
11 	  58786   58786   58786
12 	 208012  208012  208012
13 	 742900  742900  742900
14 	2674440 2674440 2674440
15 	9694845 9694845 9694845

langur

Translation of: Perl

val factorial = fn x:if(x < 2: 1; x * fn((x - 1)))

val catalan = fn n:factorial(2 * n) / factorial(n+1) / factorial(n)

for i in 0..15 {
    writeln "{{i:2}}: {{catalan(i):10}}"
}

writeln "10000: ", catalan(10000)

Output:

 0:          1
 1:          1
 2:          2
 3:          5
 4:         14
 5:         42
 6:        132
 7:        429
 8:       1430
 9:       4862
10:      16796
11:      58786
12:     208012
13:     742900
14:    2674440
15:    9694845
10000: 224537812493385215633593584257360578701103586219365887773293713835854436588700534490998102719114320210209905393799589701149327326500953702713977513001838761306936534407802585494454599941773729984591764542782202886796997833276495496514760245912220654267091568311812071300891219894022165175451441066691435091975969499731921675488934120638046514134965974069039677192984714638704528752769863567952620334847707274529741976558104236293861846622622783294667505268651205024766408784881872997404042356319626323351089169906635603513309014645157443570842822082866699012415455339518777770781742052837799476906230350785959040487158118992753484022865373274100095762968510625236915280143408460651206678398725681703811505423791566261735329550627967717189932855983913468867794806585863794483869239933179341394259456515091026456652770409848702116046445406995085092488210998732255656992243441519938747425554228724734242623566663631968254490897214106655375215196762710825001305055093871863518797311135688370964194817463890187212845332422257193414201244344808864449873736345425670715824582633802476282521798739438044652622163657359012681653473214512797365047989922327391063907061792126264420963262176161781711086630089636828211837643128677915076724947168653050318426339007489738275045346257959685376480042860870398232333705506506342394485443047987642390287346746539674780326188825579548593281319807827279403944008553690033855132088140116099772393778770685018936338194366302053586633406848404622048675525765095697363909787189635178694239275237185046710057476484117945279786897787624602379494797322427251542758312638233073625857897083435831841717971137851874666094337671443717108457737153283641719103639784923520519013700030680553564442331411313831920775983175313709250333784211385811480015293165463406576311626295629412110652218717603537723650144357966952842696678735624157616428716812764985074925414219421312810089785108621126934245959900367104035334200067714905754827856122801987429837706493130435832752072139392743006620396370486473952500144779413596417260472218266529167783118015414918168260722824885550181735638670588682513610805160133611349864194033776132438535863120087679096358696928233598996870302136347936567444208209125300149683552369341937471817860835774359234009557030148123353114950735217736514617017504851011193104728986836180908987352236659629183725016607437110422583156042941955830763092095074443334625318588569114114087985404048889671202396824806275701581378689568449507132793603852731445602923990458926101180821029108808623323378547869169352237448925371763574346501610378415722137519019474474794069155118626291447578558908522430436148987521551911541787974276591708584289036595642180860178815462862735993859177180582760389253540408842580225467216988321950591728369194164290645992782274919561096308372635908842325870580231011459216934235078490764707633348336131667313582584404397290232519769625777374165187949140092779343812345117947306771376053099536367169631889642304360871187460737580808157222861127968703067542270175460553478533349238111434409526724363429611803844595968793121871649699680963646793415774160274520010905236593324062464542927011227158945796188186430711399250096518886617184049325827319276468018789191520522185358895653192882843061349706085770767046601045697944646638311930027354235643643713545212361580694059553720806659066661496416423676930095857438882302891350789287291844752601744462789158506243012088536936184422120232369244564444689340142897415432231452353338115944183447986470689449043710051589958391273681116292415738776171575775695905846247205522469202801517417551374761549677412720803623129527503286287755308576386461385928958587649159872019202866614901547860974883963007792442796064165417207167072370586790722366932349325253877744621251386864069101337572557790214048760202008337611577675840153696735860276810033694744314488435390547908483357054897387317002405793108554524629034558098886977538473481750772616164313845337139245688079995996839933620829828339492800825536599964878893947278408890351634126931068657027524005795713514365098086505030570362785115155293306343520969872400876180105031975302255898787642403303027682634969586730202117121076117629457710028105378124677420093990476071697970354661002217702623344454780740808459286778553016318604430682610618871098652904537323336381304469735192868285840882036271136058499391069436145426450229039329475974178236465920534171895204155964515055983303017823692138977622016292722019365841360360274557488926673754175222061483328914099598663902320310143583379354121664996173733086613692927391384486261610892314450463841637667054196985332620403539011932606618414419229492637564924726411270720189611019154677281846409387514072618176832310721327819277699943226895919915049652045449281057471199978267843961724883768772155477073354744908923995448752333726740642292872107500458349718026322755698226793850983280706045951407323891263270928264657562125955511946782954645656015480418543664557515041692091317941000997342935512311493290722434384401250133402934163457264794261787386862382738330195237770190998115114193014769006071380834085352290585937952429981509893303796306071520571655936820282768086579891336876000368502562579738337809071051261343359121744773055264455701014137255399929760233753812017596045145926791136761130783810840502248142803073720015451941006030172192834375431286154255159659778817089767964922549014569972777126726537787896968876337799235679125368824867754881036161730805613471278633981478858113141202728303435218970292775366288829203013873713349923690394124920402725698544786016048685431525811047414746045227535216327530901827040588505255466803793791888002231571686068617764292584075135236237044383334893874602177596602979234717936820827427229615827657960492946059695301906791494260652411424538532836730097985187522379068364429583532675896349363295120431429006688249818006722311568902288350452581968418068616818268667067741994472455501649753611708445979082338902214467454627107888156489438584617793175431865532382711812960546611287516640

Logo

to factorial :n
  output ifelse [less? :n 1] 1 [product :n factorial difference :n 1]
end
to choose :n :r
  output quotient factorial :n product factorial :r factorial difference :n :r
end
to catalan :n
  output product (quotient sum :n 1) choose product 2 :n :n
end

repeat 15 [print catalan repcount]

Output:

Logtalk

For this task it is instructive to show a more general-purpose interface for sequences and an implementation of it for Catalan numbers.

First, loader.lgt:

:- initialization((
    % libraries
    logtalk_load(dates(loader)),
    logtalk_load(meta(loader)),
    logtalk_load(types(loader)),
    % application
    logtalk_load(seqp),
    logtalk_load(catalan),
    logtalk_load(catalan_test)
)).

The interface is defined in seqp.lgt as a protocol:

:- protocol(seqp).

    :- public(init/0).    % reset to a beginning state if meaningful

    :- public(nth/2).     % get the nth value of the sequence

    :- public(to_nth/2).  % get from the start to the nth value of the sequence as a list

:- end_protocol.

The implementation of a Catalan sequence generator is in catalan.lgt:

:- object(catalan, implements(seqp)).

    :- private(catalan/2).
    :- dynamic(catalan/2).

    % Public interface.

    init :- retractall(catalan(_,_)).   % flush any memoized results

    nth(N, V) :- \+ catalan(N, V), catalan_(N, V), !.   % generate iff it's not been memoized
    nth(N, V) :- catalan(N, V), !.                      % otherwise use the memoized version

    to_nth(N, L) :-
        integer::sequence(0, N, S), % generate a list of 0 to N
        meta::map(nth, S, L).       % map the nth/2 predicate to the list for all Catalan numbers up to N

    % Local helper predicates.

    catalan_(N, V) :-
        N > 0,                              % calculate
        N1 is N - 1,
        N2 is N + 1,
        catalan_(N1, V1),                   % via a recursive call
        V is V1 * 2 * (2 * N - 1) // N2,    
        assertz(catalan(N, V)).             % and memoize the result
    catalan_(0, 1).

:- end_object.

This is a memoizing implementation whose impact we will check in the test. The init/0 predicate flushes any memoized results.

The test driver is a simple one that generates the first fifteen Catalan numbers four times, comparing times with and without memoization. From catalan_test.lgt:

:- object(catalan_test).

    :- public(run/0).

    run :-
        % put the object into a known initial state
        catalan::init,

        % first 15 Catalan numbers, record duration.
        time_operation(catalan::to_nth(15, C1), D1),

        % first 15 Catalan numbers again, twice, recording duration.
        time_operation(catalan::to_nth(15, C2), D2),
        time_operation(catalan::to_nth(15, C3), D3),

        % reset the object again
        catalan::init,

        % first 15 Catalan numbers, record duration.
        time_operation(catalan::to_nth(15, C4), D4),

        % ensure the results were the same each time
        C1 = C2, C2 = C3, C3 = C4,

        % write the results and durations of each run
        write(C1), write(' '), write(D1), nl,
        write(C2), write(' '), write(D2), nl,
        write(C3), write(' '), write(D3), nl,
        write(C4), write(' '), write(D4), nl.
        % visual inspection should show all results the same
        % first and final durations should be much larger

    :- meta_predicate(time_operation(0, *)).

    time_operation(Goal, Duration) :-
        time::cpu_time(Before),
        call(Goal),
        time::cpu_time(After),
        Duration is After - Before.

:- end_object.

Output:

The session at the top-level looks like this:

?- {loader}.
% ... messages elided ...
% (0 warnings)
   true.

?- catalan_test::run.
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845] 0.001603
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845] 0.000306
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845] 0.00026
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845] 0.001346
   true.

This test shows:

The nth/2 predicate works (since to_nth/2 is implemented in terms of it).
The to_nth/2 predicate works.
Memoization generates a speedup of between ~4.5× to ~6.2× over generating from scratch.

Lua

-- recursive with memoization
local catalan = { [0] = 1 }
setmetatable(catalan, {
    __index = function(c, n)
        c[n] = c[n - 1] * 2 * (2 * n - 1) / (n + 1)
        return c[n]
    end
})

for i = 0, 14 do
    print(string.format("%d", catalan[i]))
end

Output:

MAD

            NORMAL MODE IS INTEGER
            DIMENSION C(15)
            
            C(0) = 1
            THROUGH CALC, FOR N=1, 1, N.GE.15
CALC        C(N) = ((4*N-2)*C(N-1))/(N+1)
            
            THROUGH SHOW, FOR N=0, 1, N.GE.15
SHOW        PRINT FORMAT CFMT,N,C(N)

            VECTOR VALUES CFMT=$2HC(,I2,4H) = ,I7*$
            END OF PROGRAM

Output:

C( 0) =       1
C( 1) =       1
C( 2) =       2
C( 3) =       5
C( 4) =      14
C( 5) =      42
C( 6) =     132
C( 7) =     429
C( 8) =    1430
C( 9) =    4862
C(10) =   16796
C(11) =   58786
C(12) =  208012
C(13) =  742900
C(14) = 2674440

Maple

CatalanNumbers := proc( n::posint )
    return seq( (2*i)!/((i + 1)!*i!), i = 0 .. n - 1 );
end proc:
CatalanNumbers(15);

Output:

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440

Mathematica / Wolfram Language

CatalanN[n_Integer /; n >= 0] := (2 n)!/((n + 1)! n!)

Sample Output:

TableForm[CatalanN/@Range[0,15]]
//TableForm= 
1
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440
9694845

MATLAB / Octave

function n = catalanNumber(n)
    for i = (1:length(n))
        n(i) = (1/(n(i)+1))*nchoosek(2*n(i),n(i));
    end
end

The following version computes at the same time the n first Catalan numbers (including C0).

function n = catalanNumbers(n)
    n = [1 cumprod((2:4:4*n-6) ./ (2:n))];
end

Sample Output:

>> catalanNumber(14)

ans =

     2674440

>> catalanNumbers(18)'

ans =

           1
           1
           2
           5
          14
          42
         132
         429
        1430
        4862
       16796
       58786
      208012
      742900
     2674440
     9694845
    35357670
   129644790

The following version uses the identity Ln(x!)=Gammaln(x+1) and prod(1:x)=sum(ln(1:x))

CatalanNumber=@(n) round(exp(gammaln(2*n+1)-sum(gammaln([n+2 n+1]))));

Sample Output:

>>CatalanNumber(10)

ans =

       16796

>> num2str(CatalanNumber(20))

ans =

    '6564120420'

Maxima

/* The following is an array function, hence the square brackets. It uses memoization automatically */
cata[n] := sum(cata[i]*cata[n - 1 - i], i, 0, n - 1)$
cata[0]: 1$

cata2(n) := binomial(2*n, n)/(n + 1)$

makelist(cata[n], n, 0, 14);

makelist(cata2(n), n, 0, 14);

/* both return [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440] */

Miranda

main :: [sys_message]
main = [Stdout (lay (map (show . catalan) [0..14]))]

catalan :: num->num
catalan 0 = 1
catalan n = (4*n - 2) * catalan (n - 1) div (n + 1)

Output:

Modula-2

MODULE CatalanNumbers;
FROM FormatString IMPORT FormatString;
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;

PROCEDURE binomial(m,n : LONGCARD) : LONGCARD;
VAR r,d : LONGCARD;
BEGIN
    r := 1;
    d := m - n;
    IF d>n THEN
        n := d;
        d := m - n;
    END;
    WHILE m>n DO
        r := r * m;
        DEC(m);
        WHILE (d>1) AND NOT (r MOD d # 0) DO
            r := r DIV d;
            DEC(d)
        END
    END;
    RETURN r
END binomial;

PROCEDURE catalan1(n : LONGCARD) : LONGCARD;
BEGIN
    RETURN binomial(2*n,n) DIV (1+n)
END catalan1;

PROCEDURE catalan2(n : LONGCARD) : LONGCARD;
VAR i,sum : LONGCARD;
BEGIN
    IF n>1 THEN
        sum := 0;
        FOR i:=0 TO n-1 DO
            sum := sum + catalan2(i) * catalan2(n - 1 - i)
        END;
        RETURN sum
    ELSE
        RETURN 1
    END
END catalan2;

PROCEDURE catalan3(n : LONGCARD) : LONGCARD;
BEGIN
    IF n#0 THEN
        RETURN 2  *(2 * n - 1) * catalan3(n - 1) DIV (1 + n)
    ELSE
        RETURN 1
    END
END catalan3;

VAR
    blah : LONGCARD = 123;
    buf : ARRAY[0..63] OF CHAR;
    i : LONGCARD;
BEGIN
    FormatString("\tdirect\tsumming\tfrac\n", buf);
    WriteString(buf);
    FOR i:=0 TO 15 DO
        FormatString("%u\t%u\t%u\t%u\n", buf, i, catalan1(i), catalan2(i), catalan3(i));
        WriteString(buf)
    END;
    ReadChar
END CatalanNumbers.

Nim

import math
import strformat

proc catalan1(n: int): int =
  binom(2 * n, n) div (n + 1)

proc catalan2(n: int): int =
  if n == 0:
    return 1
  for i in 0..<n:
    result += catalan2(i) * catalan2(n - 1 - i)

proc catalan3(n: int): int =
  if n > 0: 2 * (2 * n - 1) * catalan3(n - 1) div (1 + n)
  else: 1

for i in 0..15:
  echo &"{i:7} {catalan1(i):7} {catalan2(i):7} {catalan3(i):7}"

Output:

      0       1       1       1
      1       1       1       1
      2       2       2       2
      3       5       5       5
      4      14      14      14
      5      42      42      42
      6     132     132     132
      7     429     429     429
      8    1430    1430    1430
      9    4862    4862    4862
     10   16796   16796   16796
     11   58786   58786   58786
     12  208012  208012  208012
     13  742900  742900  742900
     14 2674440 2674440 2674440
     15 9694845 9694845 9694845

OCaml

let imp_catalan n =
  let return = ref 1 in
  for i = 1 to n do
    return := !return * 2 * (2 * i - 1) / (i + 1)
  done;
  !return

let rec catalan = function
  | 0 -> 1
  | n -> catalan (n - 1) * 2 * (2 * n - 1) / (n + 1)

let memoize f =
  let cache = Hashtbl.create 20 in
  fun n ->
    match Hashtbl.find_opt cache n with
    | None ->
      let x = f n in
      Hashtbl.replace cache n x;
      x
    | Some x -> x

let catalan_cache = Hashtbl.create 20

let rec memo_catalan n =
  if n = 0 then 1 else
    match Hashtbl.find_opt catalan_cache n with
    | None ->
      let x = memo_catalan (n - 1) * 2 * (2 * n - 1) / (n + 1) in
      Hashtbl.replace catalan_cache n x;
      x
    | Some x -> x

let () =
  if not !Sys.interactive then
    let bench label f n times =
      let start = Unix.gettimeofday () in
      begin
        for i = 1 to times do f n done;
        let stop = Unix.gettimeofday () in
        Printf.printf "%s (%d runs) : %.3f\n"
          label times (stop -. start)
      end in
    let show f g h f' n =
      for i = 0 to n do
        Printf.printf "%2d %7d %7d %7d %7d\n"
          i (f i) (g i) (h i) (f' i)
      done
    in
    List.iter (fun (l, f) -> bench l f 15 10_000_000)
      ["imperative", imp_catalan;
       "recursive", catalan;
       "hand-memoized", memo_catalan;
       "memoized", (memoize catalan)];
    show imp_catalan catalan memo_catalan (memoize catalan) 15

Output:

$ ocaml unix.cma catalan.ml
imperative (10000000 runs) : 3.420
recursive (10000000 runs) : 3.821
hand-memoized (10000000 runs) : 0.531
memoized (10000000 runs) : 0.515
 0       1       1       1       1
 1       1       1       1       1
 2       2       2       2       2
 3       5       5       5       5
 4      14      14      14      14
 5      42      42      42      42
 6     132     132     132     132
 7     429     429     429     429
 8    1430    1430    1430    1430
 9    4862    4862    4862    4862
10   16796   16796   16796   16796
11   58786   58786   58786   58786
12  208012  208012  208012  208012
13  742900  742900  742900  742900
14 2674440 2674440 2674440 2674440
15 9694845 9694845 9694845 9694845

$ ocamlopt -O2 unix.cmxa catalan.ml -o catalan
$ ./catalan
imperative (10000000 runs) : 2.020
recursive (10000000 runs) : 2.283
hand-memoized (10000000 runs) : 0.159
memoized (10000000 runs) : 0.167
...

Oforth

: catalan( n -- m ) 
    n ifZero: [ 1 ] else: [ catalan( n 1- ) 2 n * 1- * 2 * n 1+ / ] ;

Output:

import: mapping
seqFrom(0, 15) map( #catalan ) .
[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]

ooRexx

Three versions of this.

loop i = 0 to 15
    say "catI("i") =" .catalan~catI(i)
    say "catR1("i") =" .catalan~catR1(i)
    say "catR2("i") =" .catalan~catR2(i)
end

-- This is implemented as static members on a class object
-- so that the code is able to keep state information between calls.  This
-- memoization will speed up things like factorial calls by remembering previous
-- results.
::class catalan
-- initialize the class object
::method init class
  expose facts catI catR1 catR2
         facts = .table~new
         catI = .table~new
         catR1 = .table~new
         catR2 = .table~new
         -- seed a few items
         facts[0] = 1
         facts[1] = 1
         facts[2] = 2
         catI[0] = 1
         catR1[0] = 1
         catR2[0] = 1

-- private factorial method
::method fact private class
  expose facts
  use arg n
  -- see if we've calculated this before
  if facts~hasIndex(n) then return facts[n]
  numeric digits 120

  fact = 1
  loop i = 2 to n
      fact *= i
  end
  -- save this result
  facts[n] = fact
  return fact

::method catI class
  expose catI
  use arg n
  numeric digits 20

  res = catI[n]
  if res == .nil then do
      -- dividing by 1 removes insignificant trailing 0s
      res = (self~fact(2 * n)/(self~fact(n + 1) * self~fact(n))) / 1
      catI[n] = res
  end
  return res

::method catR1 class
  expose catR1
  use arg n
  numeric digits 20

  if catR1~hasIndex(n) then return catR1[n]
  sum = 0
  loop i = 0 to n - 1
      sum += self~catR1(i) * self~catR1(n - 1 - i)
  end
  -- remove insignificant trailing 0s
  sum = sum / 1
  catR1[n] = sum
  return sum

::method catR2 class
  expose catR2
  use arg n
  numeric digits 20

  res = catR2[n]
  if res == .nil then do
     res = ((2 * (2 * n - 1) * self~catR2(n - 1)) /  (n + 1))
     catR2[n] = res
  end
  return res

Output:

catI(0) = 1
catR1(0) = 1
catR2(0) = 1
catI(1) = 1
catR1(1) = 1
catR2(1) = 1
catI(2) = 2
catR1(2) = 2
catR2(2) = 2
catI(3) = 5
catR1(3) = 5
catR2(3) = 5
catI(4) = 14
catR1(4) = 14
catR2(4) = 14
catI(5) = 42
catR1(5) = 42
catR2(5) = 42
catI(6) = 132
catR1(6) = 132
catR2(6) = 132
catI(7) = 429
catR1(7) = 429
catR2(7) = 429
catI(8) = 1430
catR1(8) = 1430
catR2(8) = 1430
catI(9) = 4862
catR1(9) = 4862
catR2(9) = 4862
catI(10) = 16796
catR1(10) = 16796
catR2(10) = 16796
catI(11) = 58786
catR1(11) = 58786
catR2(11) = 58786
catI(12) = 208012
catR1(12) = 208012
catR2(12) = 208012
catI(13) = 742900
catR1(13) = 742900
catR2(13) = 742900
catI(14) = 2674440
catR1(14) = 2674440
catR2(14) = 2674440
catI(15) = 9694845
catR1(15) = 9694845
catR2(15) = 9694845

PARI/GP

First version

Memoization is not worthwhile; PARI has fast built-in facilities for calculating binomial coefficients and factorials.

catalan(n)=binomial(2*n,n+1)/n

Second version

catalan(n)=(2*n)!/(n+1)!/n!

Naive version with binary splitting

catalan(n)=prod(k=n+2,2*n,k)/prod(k=2,n,k)

Naive version

catalan(n)={
  my(t=1);
  for(k=n+2,2*n,t*=k);
  for(k=2,n,t/=k);
  t
};

The first version takes about 1.5 seconds to compute the millionth Catalan number, while the second takes 3.9 seconds. The naive implementations, for comparison, take 21 and 45 minutes. In any case, printing the first 15 is simple:

vector(15,n,catalan(n))

Version using Catalan numbers Generating function

Vec((1-sqrt(1 - 4*x))/(2*x)+O(x^16))

Output:

[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440]

Pascal

Program CatalanNumbers(output);

function catalanNumber1(n: integer): double;
  begin
    if n = 0 then
      catalanNumber1 := 1.0
    else 
      catalanNumber1 := double(4 * n - 2) / double(n + 1) * catalanNumber1(n-1);
  end;
 
var
  number: integer;

begin
  writeln('Catalan Numbers');
  writeln('Recursion with a fraction:');
  for number := 0 to 14 do
    writeln (number:3, round(catalanNumber1(number)):9);
end.

Output:

:> ./CatalanNumbers
Catalan Numbers
Recursion with a fraction:
  0        1
  1        1
  2        2
  3        5
  4       14
  5       42
  6      132
  7      429
  8     1430
  9     4862
 10    16796
 11    58786
 12   208012
 13   742900
 14  2674440

PascalABC.NET

##
function binom(n, k: integer): int64;
begin
  result := 1;
  for var i := 1 to k do
    result := result * (n - i + 1) div i
end;

function catalan1(n: integer) := binom(2 * n, n) div (n + 1);

function catalan2(n: integer): integer;
begin
  if n = 0 then begin result := 1; exit end;
  for var i := 0 to n - 1 do 
    result += catalan2(i) * catalan2(n - 1 - i)
end;

function catalan3(n: integer): integer;
begin
  if n > 0 then result := 2 * (2 * n - 1) * catalan3(n - 1) div (1 + n)
  else result := 1;
end;

for var i := 0 to 15 do 
  writeln(i:2, catalan1(i):9, catalan2(i):9, catalan3(i):9);

Perl

sub factorial { my $f = 1; $f *= $_ for 2 .. $_[0]; $f; }
sub catalan {
  my $n = shift;
  factorial(2*$n) / factorial($n+1) / factorial($n);
}

print "$_\t@{[ catalan($_) ]}\n" for 0 .. 20;

For computing up to 20 ish, memoization is not needed. For much bigger numbers, this is faster:

my @c = (1);
sub catalan { 
        use bigint;
        $c[$_[0]] //= catalan($_[0]-1) * (4 * $_[0]-2) / ($_[0]+1)
}

# most of the time is spent displaying the long numbers, actually
print "$_\t", catalan($_), "\n" for 0 .. 10000;

That has two downsides: high memory use and slow access to an isolated large value. Using a fast binomial function can solve both these issues. The downside here is if the platform doesn't have the GMP library then binomials won't be fast.

Library: ntheory

use ntheory qw/binomial/;
sub catalan {
  my $n = shift;
  binomial(2*$n,$n)/($n+1);
}
print "$_\t", catalan($_), "\n" for 0 .. 10000;

Phix

See also Catalan_numbers/Pascal's_triangle#Phix which may be faster.

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)

Output:

 0:          1          1          1
 1:          1          1          1
 2:          2          2          2
 3:          5          5          5
 4:         14         14         14
 5:         42         42         42
 6:        132        132        132
 7:        429        429        429
 8:       1430       1430       1430
 9:       4862       4862       4862
10:      16796      16796      16796
11:      58786      58786      58786
12:     208012     208012     208012
13:     742900     742900     742900
14:    2674440    2674440    2674440
15:    9694845    9694845    9694845
times:      0s       1.6s         0s

As expected, catalan2() is by far the slowest, so let's memoise that one!

memoized recursive gmp version

Library: Phix/mpfr

with javascript_semantics 
include builtins\mpfr.e
 
sequence c2cache = {}
 
function catalan2m(integer n)   -- very fast!
object r -- result (a [cached/shared] mpz)
         -- (nb: modifying result will mess up cache)
    if n<=0 then return mpz_init(1) end if
    if n<=length(c2cache) then
        r = c2cache[n]
        if r!=0 then return r end if
    else
        c2cache &= repeat(0,n-length(c2cache))
    end if
    r = mpz_init(0)
    mpz t = mpz_init()
    for i=0 to n-1 do
        mpz_mul(t,catalan2m(i),catalan2m(n-1-i))
        mpz_add(r,r,t)
    end for
    t = mpz_free(t)
    c2cache[n] = r
    return r
end function
 
sequence s = {}
for i=0 to 15 do s = append(s,mpz_get_str(catalan2m(i))) end for
printf(1,"0..15: %s\n",join(s,","))
printf(1,"100: %s\n",{mpz_get_str(catalan2m(100))})

Output:

0..15: 1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845
100: 896519947090131496687170070074100632420837521538745909320

PHP

<?php

class CatalanNumbersSerie
{
  private static $cache = array(0 => 1);
   
  private function fill_cache($i)
  {
    $accum = 0;
    $n = $i-1;
    for($k = 0; $k <= $n; $k++)
    {
      $accum += $this->item($k)*$this->item($n-$k);
    } 
    self::$cache[$i] = $accum;
  }
  function item($i)
  {
    if (!isset(self::$cache[$i]))
    {
      $this->fill_cache($i);
    }
    return self::$cache[$i];
  }
}

$cn = new CatalanNumbersSerie();
for($i = 0; $i <= 15;$i++)
{
  $r = $cn->item($i);
  echo "$i = $r\r\n";
}
?>

Output:

0 = 1
1 = 1                                                                                                                                         
2 = 2                                                                                                                                         
3 = 5                                                                                                                                         
4 = 14                                                                                                                                        
5 = 42                                                                                                                                        
6 = 132                                                                                                                                       
7 = 429                                                                                                                                       
8 = 1430                                                                                                                                      
9 = 4862                                                                                                                                      
10 = 16796                                                                                                                                    
11 = 58786                                                                                                                                    
12 = 208012                                                                                                                                   
13 = 742900                                                                                                                                   
14 = 2674440                                                                                                                                  
15 = 9694845

<?php 
$n = 15;
$t[1] = 1;
foreach (range(1, $n+1) as $i) {
    foreach (range($i, 1-1) as $j) {
        $t[$j] += $t[$j - 1];
    }
    $t[$i +1] = $t[$i];
    foreach (range($i+1, 1-1) as $j) {
        $t[$j] += $t[$j -1];
    }
    print ($t[$i+1]-$t[$i])."\t";
}

Output:

1	2	5	14	42	132	429	1430	4862	16796	58786	208012	742900	2674440	9694845	35357670

Picat

Works with: Picat

table
factorial(0) = 1.

factorial(N) = N * factorial(N - 1).

catalan1(N) = factorial(2 * N) // (factorial(N + 1) * factorial(N)).

catalan2(0) = 1.

catalan2(N) = 2 * (2 * N - 1) * catalan2(N - 1) // (N + 1).

main =>
    foreach (I in 0..14)
        printf("%d. %d = %d\n", I, catalan1(I), catalan2(I))
    end.

Output:

0. 1 = 1
1. 1 = 1
2. 2 = 2
3. 5 = 5
4. 14 = 14
5. 42 = 42
6. 132 = 132
7. 429 = 429
8. 1430 = 1430
9. 4862 = 4862
10. 16796 = 16796
11. 58786 = 58786
12. 208012 = 208012
13. 742900 = 742900
14. 2674440 = 2674440

PicoLisp

# Factorial
(de fact (N)
   (if (=0 N)
      1
      (* N (fact (dec N))) ) )

# Directly
(de catalanDir (N)
   (/ (fact (* 2 N)) (fact (inc N)) (fact N)) )

# Recursively
(de catalanRec (N)
   (if (=0 N)
      1
      (cache '(NIL) N  # Memoize
         (sum
            '((I) (* (catalanRec I) (catalanRec (- N I 1))))
            (range 0 (dec N)) ) ) ) )

# Alternatively
(de catalanAlt (N)
   (if (=0 N)
      1
      (*/ 2 (dec (* 2 N)) (catalanAlt (dec N)) (inc N)) ) )

# Test
(for (N 0 (> 15 N) (inc N))
   (tab (2 4 8 8 8)
      N
      " => "
      (catalanDir N)
      (catalanRec N)
      (catalanAlt N) ) )

Output:

 0 =>        1       1       1
 1 =>        1       1       1
 2 =>        2       2       2
 3 =>        5       5       5
 4 =>       14      14      14
 5 =>       42      42      42
 6 =>      132     132     132
 7 =>      429     429     429
 8 =>     1430    1430    1430
 9 =>     4862    4862    4862
10 =>    16796   16796   16796
11 =>    58786   58786   58786
12 =>   208012  208012  208012
13 =>   742900  742900  742900
14 =>  2674440 2674440 2674440

PL/0

Translation of: Tiny BASIC

Integers are limited to 32767 so only the first ten Catalan numbers can be represented. To avoid internal overflow, the program subtracts something clever from c and then adds it back at the end.

var n, c, i;
begin
  n := 0; c := 1;
  ! c;
  while n <= 9 do
  begin
    n := n + 1;
    i := 0;
    while c > 0 do
    begin
      c := c - (n + 1);
      i := i + 1
    end;
    c := 2 * (2 * n - 1) * c / (n + 1); 
    c := c + 2 * i * (2 * n - 1);
    ! c
  end;
end.

Output:

PL/I

catalan: procedure options (main);   /* 23 February 2012 */
   declare (i, n) fixed;

   put skip list ('How many catalan numbers do you want?');
   get list (n);

   do i = 0 to n;
      put skip list (c(i));
   end;

c: procedure (n) recursive returns (fixed decimal (15));
   declare n fixed;

   if n <= 1 then return (1);

   return ( 2*(2*n-1) * c(n-1) / (n + 1) );
end c;

end catalan;

Output:

How many catalan numbers do you want? 

                 1 
                 1 
                 2 
                 5 
                14 
                42 
               132 
               429 
              1430 
              4862 
             16796 
             58786 
            208012 
            742900 
           2674440 
           9694845 
          35357670 
         129644790 
         477638700 
        1767263190 
        6564120420

Plain $T e X$

\newcount\n
\newcount\r
\newcount\x
\newcount\ii

\def\catalan#1{%
	\n#1\advance\n by1\ii1\r1%
	\loop{%
		\x\ii%
		\multiply\x by 2 \advance\x by -1 \multiply\x by 2%
		\global\multiply\r by\x%
		\global\advance\ii by1%
		\global\divide\r by\ii%
	} \ifnum\number\ii<\n\repeat%
	\the\r
}

\rightskip=0pt plus1fil\parindent=0pt
\loop{${\rm Catalan}(\the\x) = \catalan{\the\x}$\hfil\break}%
	\advance\x by 1\ifnum\x<15\repeat

\bye

PowerShell

function Catalan([uint64]$m) {
    function fact([bigint]$n) {
        if($n -lt 2) {[bigint]::one}
        else{2..$n | foreach -Begin {$prod = [bigint]::one} -Process {$prod = [bigint]::Multiply($prod,$_)} -End {$prod}}
    }
    $fact = fact $m
    $fact1 = [bigint]::Multiply($m+1,$fact)
    [bigint]::divide((fact (2*$m)), [bigint]::Multiply($fact,$fact1))
}
0..15 | foreach {"catalan($_): $(catalan $_)"}

Output:

catalan(0): 1
catalan(1): 1
catalan(2): 2
catalan(3): 5
catalan(4): 14
catalan(5): 42
catalan(6): 132
catalan(7): 429
catalan(8): 1430
catalan(9): 4862
catalan(10): 16796
catalan(11): 58786
catalan(12): 208012
catalan(13): 742900
catalan(14): 2674440
catalan(15): 9694845

An Alternate Version

This version could easily be modified to work with big integers.

function Get-CatalanNumber
{
    [CmdletBinding()]
    [OutputType([PSCustomObject])]
    Param
    (
        [Parameter(Mandatory=$true,
                   ValueFromPipeline=$true,
                   ValueFromPipelineByPropertyName=$true,
                   Position=0)]
        [uint32[]]
        $InputObject
    )

    Begin
    {
        function Get-Factorial ([int]$Number)
        {
            if ($Number -eq 0)
            {
                return 1
            }

            $factorial = 1

            1..$Number | ForEach-Object {$factorial *= $_}

            $factorial
        }    

        function Get-Catalan ([int]$Number)
        {
            if ($Number -eq 0)
            {
                return 1
            }

            (Get-Factorial (2 * $Number)) / ((Get-Factorial (1 + $Number)) * (Get-Factorial $Number))
        }
    }
    Process
    {
        foreach ($number in $InputObject)
        {
            [PSCustomObject]@{
                Number        = $number
                CatalanNumber = Get-Catalan $number
            }
        }
    }
}

Get the first fifteen Catalan numbers as a PSCustomObject:

0..14 | Get-CatalanNumber

Output:

Number CatalanNumber
------ -------------
     0             1
     1             1
     2             2
     3             5
     4            14
     5            42
     6           132
     7           429
     8          1430
     9          4862
    10         16796
    11         58786
    12        208012
    13        742900
    14       2674440

To return only the array of Catalan numbers:

(0..14 | Get-CatalanNumber).CatalanNumber

Output:

Prolog

Works with: SWI-Prolog

catalan(N) :-
	length(L1, N),
	L = [1 | L1],
	init(1,1,L1),
	numlist(0, N, NL),
	maplist(my_write, NL, L).


init(_, _, []).

init(V, N, [H | T]) :-
	N1 is N+1,
	H is 2 * (2 * N - 1) * V / N1,
	init(H, N1, T).

my_write(N, V) :-
	format('~w : ~w~n', [N, V]).

Output:

 ?- catalan(15).
0 : 1
1 : 1
2 : 2
3 : 5
4 : 14
5 : 42
6 : 132
7 : 429
8 : 1430
9 : 4862
10 : 16796
11 : 58786
12 : 208012
13 : 742900
14 : 2674440
15 : 9694845
true .

Python

Three algorithms including explicit memoization. (Pythons factorial built-in function is not memoized internally).

Python will transparently switch to bignum-type integer arithmetic, so the code below works unchanged on computing larger catalan numbers such as cat(50) and beyond.

Works with: Python version 3

from math import factorial
import functools


def memoize(func):
    cache = {}

    def memoized(key):
        # Returned, new, memoized version of decorated function
        if key not in cache:
            cache[key] = func(key)
        return cache[key]
    return functools.update_wrapper(memoized, func)


@memoize
def fact(n):
    return factorial(n)


def cat_direct(n):
    return fact(2 * n) // fact(n + 1) // fact(n)


@memoize
def catR1(n):
    return 1 if n == 0 else (
        sum(catR1(i) * catR1(n - 1 - i) for i in range(n))
    )


@memoize
def catR2(n):
    return 1 if n == 0 else (
        ((4 * n - 2) * catR2(n - 1)) // (n + 1)
    )


if __name__ == '__main__':
    def pr(results):
        fmt = '%-10s %-10s %-10s'
        print((fmt % tuple(c.__name__ for c in defs)).upper())
        print(fmt % (('=' * 10,) * 3))
        for r in zip(*results):
            print(fmt % r)

    defs = (cat_direct, catR1, catR2)
    results = [tuple(c(i) for i in range(15)) for c in defs]
    pr(results)

Sample Output:

CAT_DIRECT CATR1      CATR2     
========== ========== ==========
1          1          1         
1          1          1         
2          2          2         
5          5          5         
14         14         14        
42         42         42        
132        132        132       
429        429        429       
1430       1430       1430      
4862       4862       4862      
16796      16796      16796     
58786      58786      58786     
208012     208012     208012    
742900     742900     742900    
2674440    2674440    2674440

The third definition is directly expressible, as an infinite series, in terms of itertools.accumulate:

'''Catalan numbers'''

from itertools import accumulate, chain, count, islice


# catalans3 :: [Int]
def catalans3():
    '''Infinite sequence of Catalan numbers
    '''
    def go(c, n):
        return 2 * c * pred(2 * n) // succ(n)

    return accumulate(
        chain([1], count(1)), go
    )


# ------------------------- TEST -------------------------
# main :: IO ()
def main():
    '''Catalan numbers, definition 3'''
    print("Catalans 1-15:\n")
    print(
        '\n'.join([
            f'{n:>10}' for n
            in islice(catalans3(), 15)
        ])
    )


# ----------------------- GENERIC ------------------------

# pred :: Int -> Int
def pred(n):
    '''Predecessor function'''
    return n - 1


# succ :: Int -> Int
def succ(n):
    '''Successor function'''
    return 1 + n


# MAIN ---
if __name__ == '__main__':
    main()

Output:

Catalans 1-15:

         1
         1
         2
         5
        14
        42
       132
       429
      1430
      4862
     16796
     58786
    208012
    742900
   2674440

Quackery

  [ 1 over times [ over i 1+ + * ] nip ] is 2n!/n!  ( n --> n )

  [ times [ i 1+ / ] ]                   is /n!     ( n --> n )

  [ dup 2n!/n! swap 1+ /n! ]             is catalan ( n --> n )

  15 times [ i^  dup echo say " : " catalan echo cr ]

Output:

0 : 1
1 : 1
2 : 2
3 : 5
4 : 14
5 : 42
6 : 132
7 : 429
8 : 1430
9 : 4862
10 : 16796
11 : 58786
12 : 208012
13 : 742900
14 : 2674440

R

catalan <- function(n) choose(2*n, n)/(n + 1)
catalan(0:15)
 [1]       1       1       2       5      14      42     132     429    1430
[10]    4862   16796   58786  208012  742900 2674440 9694845

Racket

#lang racket
(require planet2)
; (install "this-and-that")  ; uncomment to install
(require memoize/memo)

(define/memo* (catalan m)
  (if (= m 0) 
      1
      (for/sum ([i m]) 
        (* (catalan i) (catalan (- m i 1))))))
      
(map catalan (range 1 15))

Output:

'(1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440)

Raku

(formerly Perl 6)

Works with: Rakudo version 2015.12

The recursive formulas are easily written into a constant array, either:

constant Catalan = 1, { [+] @_ Z* @_.reverse } ... *;

or

constant Catalan = 1, |[\*] (2, 6 ... *) Z/ 2 .. *;


# In both cases, the sixteen first values can be seen with:
.say for Catalan[^16];

Output:

REXX

version 1

All four methods of calculate the Catalan numbers use independent memoization for the computation of factorials.

In the 1^st equation, the 2^nd version's denominator:

(n+1)! n!

has been rearranged to:

(n+1) * [fact(n) **2]

/*REXX program calculates and displays  Catalan numbers  using  four different methods. */
parse arg LO HI .                                /*obtain optional arguments from the CL*/
if LO=='' | LO==","  then do;  HI=15; LO=0;  end /*No args? Then use a range of 0 ──► 15*/
if HI=='' | HI==","  then      HI=LO             /*No HI?   Then use  LO for the default*/
numeric digits max(20, 5*HI)                     /*this allows gihugic Catalan numbers. */
w=length(HI)                                     /*W:  is used for aligning the output. */
call hdr 1A;  do j=LO  to HI;  say '     Catalan'     right(j, w)": "      Cat1A(j);   end
call hdr 1B;  do j=LO  to HI;  say '     Catalan'     right(j, w)": "      Cat1B(j);   end
call hdr 2 ;  do j=LO  to HI;  say '     Catalan'     right(j, w)": "      Cat2(j) ;   end
call hdr 3 ;  do j=LO  to HI;  say '     Catalan'     right(j, w)": "      Cat3(j) ;   end
exit                                             /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
!:     arg z; if !.z\==. then return !.z; !=1;  do k=2  to z; !=!*k; end;  !.z=!; return !
Cat1A: procedure expose !.;  parse arg n;     return comb(n+n, n)    %  (n+1)
Cat1B: procedure expose !.;  parse arg n;     return !(n+n) % ((n+1) * !(n)**2)
Cat3:  procedure expose c.;  arg n; if c.n==. then c.n=(4*n-2)*cat3(n-1)%(n+1); return c.n
comb:  procedure;            parse arg x,y;   return pFact(x-y+1, x) % pFact(2, y)
hdr:   !.=.; c.=.; c.0=1; say; say center('Catalan numbers, method' arg(1),79,'─'); return
pFact: procedure;            !=1;      do k=arg(1)  to arg(2);  !=!*k;  end;    return !
/*──────────────────────────────────────────────────────────────────────────────────────*/
Cat2:  procedure expose c.;  parse arg n;  $=0;         if c.n\==.  then return c.n
                                       do k=0  for n;   $=$ + Cat2(k) * Cat2(n-k-1);   end
                             c.n=$;           return $    /*use a memoization technique.*/

output when using the input of: 0 16

───────────────────────── Catalan numbers, method 1A ──────────────────────────
     Catalan  0:  1
     Catalan  1:  1
     Catalan  2:  2
     Catalan  3:  5
     Catalan  4:  14
     Catalan  5:  42
     Catalan  6:  132
     Catalan  7:  429
     Catalan  8:  1430
     Catalan  9:  4862
     Catalan 10:  16796
     Catalan 11:  58786
     Catalan 12:  208012
     Catalan 13:  742900
     Catalan 14:  2674440
     Catalan 15:  9694845 

───────────────────────── Catalan numbers, method 1B ──────────────────────────
···  (elided, same as first method) ··· 

───────────────────────── Catalan numbers, method 2  ──────────────────────────
···  (elided, same as first method) ···

───────────────────────── Catalan numbers, method 3  ──────────────────────────
···  (elided, same as first method) ···

Timing notes of the four methods:

For Catalan numbers 1 ──► 200:

method 1A is about 50 times slower than method 3
method 1B is about 100 times slower than method 3
method 2 is about 85 times slower than method 3

For Catalan numbers 1 ──► 300:

method 1A is about 100 times slower than method 3
method 1B is about 200 times slower than method 3
method 2 is about 200 times slower than method 3

Method 3 is really quite fast; even in the thousands range, computation time is still quite reasonable.

version 2

Implements the 3 methods shown in the task description

/* REXX ---------------------------------------------------------------
* 01.07.2014 Walter Pachl
*--------------------------------------------------------------------*/
Numeric Digits 1000
Parse Arg m .
If m='' Then m=20
Do i=0 To m
  c1.i=c1(i)
  End
c2.=1
Do i=1 To m
  c2.i=c2(i)
  End
c3.=1
Do i=1 To m
  im1=i-1
  c3.i=2*(2*i-1)*c3.im1/(i+1)
  End
l=length(c3.m)
hdr=' n' right('c1.n',l),
         right('c2.n',l),
         right('c3.n',l)
Say hdr
Do i=0 To m
  Say right(i,2) format(c1.i,l),
                 format(c2.i,l),
                 format(c3.i,l)
  End
Say hdr
Exit

c1: Procedure
Parse Arg n
return fact(2*n)/(fact(n)*fact(n+1))

c2: Procedure Expose c2.
Parse Arg n
res=0
Do i=0 To n-1
  nmi=n-i-1
  res=res+c2.i*c2.nmi
  End
Return res

fact: Procedure
Parse Arg n
f=1
Do i=1 To n
  f=f*i
  End
Return f

Output:

 n       c1.n       c2.n       c3.n
 0          1          1          1
 1          1          1          1
 2          2          2          2
 3          5          5          5
 4         14         14         14
 5         42         42         42
 6        132        132        132
 7        429        429        429
 8       1430       1430       1430
 9       4862       4862       4862
10      16796      16796      16796
11      58786      58786      58786
12     208012     208012     208012
13     742900     742900     742900
14    2674440    2674440    2674440
15    9694845    9694845    9694845
16   35357670   35357670   35357670
17  129644790  129644790  129644790
18  477638700  477638700  477638700
19 1767263190 1767263190 1767263190
20 6564120420 6564120420 6564120420
 n       c1.n       c2.n       c3.n

Ring

for n = 1 to 15
    see catalan(n) + nl
next
 
func catalan n
     if n = 0 return 1 ok
     cat = 2 * (2 * n - 1) * catalan(n - 1) / (n + 1)
     return cat

Output:

RPL

Works with: Halcyon Calc version 4.2.7

Code

Comments

≪  
 IFERR R→B THEN END
 IF DUP #1 ≠
 THEN
     DUP 2 * 1 - 2 * OVER 1 - →CAT * SWAP 1 + /
 END 
≫ '→CAT' STO

( n -- C(n) )
Ignore the conversion error if n is already a binary integer
C(1) = 1

Divide by (n+1) at the end to stay in the integer world

To speed up execution, additions can be preferred to multiplications by replacing 2 * with DUP +. The following piece of code will deliver what is required:

≪ 1 { } DO OVER →CAT B→R + SWAP 1 + SWAP UNTIL OVER 15 > END ≫ EVAL

Output:

1: { 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 }

Ruby

def factorial(n)
  (1..n).reduce(1, :*)
end

# direct

def catalan_direct(n)
  factorial(2*n) / (factorial(n+1) * factorial(n))
end

# recursive

def catalan_rec1(n)
  return 1 if n == 0
  (0...n).sum{|i| catalan_rec1(i) * catalan_rec1(n-1-i)}
end

def catalan_rec2(n)
  return 1 if n == 0
  2*(2*n - 1) * catalan_rec2(n-1) / (n+1)
end

# performance and results

require 'benchmark'
require 'memoize'
include Memoize

Benchmark.bm(17) do |b|
  b.report('catalan_direct')    {16.times {|n| catalan_direct(n)} }
  b.report('catalan_rec1')      {16.times {|n| catalan_rec1(n)} }
  b.report('catalan_rec2')      {16.times {|n| catalan_rec2(n)} }
  
  memoize :catalan_rec1
  b.report('catalan_rec1(memo)'){16.times {|n| catalan_rec1(n)} }
end

puts "\n       direct     rec1     rec2"
16.times {|n| puts "%2d :%9d%9d%9d" % [n, catalan_direct(n), catalan_rec1(n), catalan_rec2(n)]}

The output shows the dramatic difference memoizing makes.

                        user     system      total        real
catalan_direct      0.000000   0.000000   0.000000 (  0.000124)
catalan_rec1        6.178000   0.000000   6.178000 (  6.195141)
catalan_rec2        0.000000   0.000000   0.000000 (  0.000023)
catalan_rec1(memo)  0.000000   0.000000   0.000000 (  0.000641)

       direct     rec1     rec2
 0 :        1        1        1
 1 :        1        1        1
 2 :        2        2        2
 3 :        5        5        5
 4 :       14       14       14
 5 :       42       42       42
 6 :      132      132      132
 7 :      429      429      429
 8 :     1430     1430     1430
 9 :     4862     4862     4862
10 :    16796    16796    16796
11 :    58786    58786    58786
12 :   208012   208012   208012
13 :   742900   742900   742900
14 :  2674440  2674440  2674440
15 :  9694845  9694845  9694845

Rust

Recursive Function Version

fn c_n(n: u64) -> u64 {
    match n {
        0 => 1,
        _ => c_n(n - 1) * 2 * (2 * n - 1) / (n + 1)
    }
}

fn main() {
    for i in 1..16 {
        println!("c_n({}) = {}", i, c_n(i));
    }
}

Output:

c(1) = 1
c(2) = 2
c(3) = 5
c(4) = 14
c(5) = 42
c(6) = 132
c(7) = 429
c(8) = 1430
c(9) = 4862
c(10) = 16796
c(11) = 58786
c(12) = 208012
c(13) = 742900
c(14) = 2674440
c(15) = 9694845

Custom Iterator

struct Catalan {
    catalans: Vec<i64>,
    n: i64,
}

impl Default for Catalan {
    fn default() -> Self {
        Catalan {
            catalans: vec![1],
            n: 1,
        }
    }
}

impl Iterator for Catalan {
    type Item = i64;

    fn next(&mut self) -> Option<Self::Item> {
        let c = *self.catalans.last().unwrap();
        let next = 2 * c * (2 * self.n - 1) / (self.n + 1);
        
        self.catalans.push(next);
        self.n += 1;
        
        Some(next)
    }
}

fn main() {
    for (i, catalan) in Catalan::default().take(15).enumerate() {
        println!("c_n({}) = {}", i, catalan);
    }
}

Output:

Idem

Scala

Simple and straightforward. Noticeably out of steam without memoizing at about 5000.

object CatalanNumbers {
  def main(args: Array[String]): Unit = {
    for (n <- 0 to 15) {
      println("catalan(" + n + ") = " + catalan(n))
    }
  }

  def catalan(n: BigInt): BigInt = factorial(2 * n) / (factorial(n + 1) * factorial(n))

  def factorial(n: BigInt): BigInt = BigInt(1).to(n).foldLeft(BigInt(1))(_ * _)
}

Output:

catalan(0) = 1
catalan(1) = 1
catalan(2) = 2
catalan(3) = 5
catalan(4) = 14
catalan(5) = 42
catalan(6) = 132
catalan(7) = 429
catalan(8) = 1430
catalan(9) = 4862
catalan(10) = 16796
catalan(11) = 58786
catalan(12) = 208012
catalan(13) = 742900
catalan(14) = 2674440
catalan(15) = 9694845

Scheme

Tail recursive implementation.

(define (catalan m)
    (let loop ((c 1)(n 0))
        (if (not (eqv? n m))
            (begin
                (display n)(display ": ")(display c)(newline)
                (loop (* (/ (* 2 (- (* 2 (+ n 1)) 1)) (+ (+ n 1) 1)) c) (+ n 1) )))))

(catalan 15)

Output:

0: 1
1: 1
2: 2
3: 5
4: 14
5: 42
6: 132
7: 429
8: 1430
9: 4862
10: 16796
11: 58786
12: 208012
13: 742900
14: 2674440

Seed7

$ include "seed7_05.s7i";
  include "bigint.s7i";

const proc: main is func
  local
    var bigInteger: n is 0_;
  begin
    for n range 0_ to 15_ do
      writeln((2_ * n) ! n div succ(n));
    end for;
  end func;

Output:

Sidef

func f(i) { i==0 ? 1 : (i * f(i-1)) }
func c(n) { f(2*n) / f(n) / f(n+1) }

With memoization:

func c(n) is cached {
    n == 0 ? 1 : (c(n-1) * (4 * n - 2) / (n + 1))
}

Calling the function:

15.times { |i|
    say "#{i}\t#{c(i)}"
}

Output:

Standard ML

(*
 * val catalan : int -> int
 * Returns the nth Catalan number.
 *)
fun catalan 0 = 1
|   catalan n = ((4 * n - 2) * catalan(n - 1)) div (n + 1);

(*
 * val print_catalans : int -> unit
 * Prints out Catalan numbers 0 through 15.
 *)
fun print_catalans(n) =
    if n > 15 then ()
    else (print (Int.toString(catalan n) ^ "\n"); print_catalans(n + 1)); print_catalans(0);
(*
 * 1
 * 1
 * 2
 * 5
 * 14
 * 42
 * 132
 * 429
 * 1430
 * 4862
 * 16796
 * 58786
 * 208012
 * 742900
 * 2674440
 * 9694845
 *)

Stata

clear
set obs 15
gen catalan=1 in 1
replace catalan=catalan[_n-1]*2*(2*_n-3)/_n in 2/l
list, noobs noh

Output

  +---------+
  |       1 |
  |       1 |
  |       2 |
  |       5 |
  |      14 |
  |---------|
  |      42 |
  |     132 |
  |     429 |
  |    1430 |
  |    4862 |
  |---------|
  |   16796 |
  |   58786 |
  |  208012 |
  |  742900 |
  | 2674440 |
  +---------+

Swift

Translation of: Rust

func catalan(_ n: Int) -> Int {
  switch n {
  case 0:
    return 1
  case _:
    return catalan(n - 1) * 2 * (2 * n - 1) / (n + 1)
  }
}

for i in 1..<16 {
  print("catalan(\(i)) => \(catalan(i))")
}

Output:

catalan(1) => 1
catalan(2) => 2
catalan(3) => 5
catalan(4) => 14
catalan(5) => 42
catalan(6) => 132
catalan(7) => 429
catalan(8) => 1430
catalan(9) => 4862
catalan(10) => 16796
catalan(11) => 58786
catalan(12) => 208012
catalan(13) => 742900
catalan(14) => 2674440
catalan(15) => 9694845

Tcl

package require Tcl 8.5

# Memoization wrapper
proc memoize {function value generator} {
    variable memoize
    set key $function,$value
    if {![info exists memoize($key)]} {
	set memoize($key) [uplevel 1 $generator]
    }
    return $memoize($key)
}

# The simplest recursive definition
proc tcl::mathfunc::catalan n {
    if {[incr n 0] < 0} {error "must not be negative"}
    memoize catalan $n {expr {
	$n == 0 ? 1 : 2 * (2*$n - 1) * catalan($n - 1) / ($n + 1)
    }}
}

Demonstration:

for {set i 0} {$i < 15} {incr i} {
    puts "C_$i = [expr {catalan($i)}]"
}

Output:

C_0 = 1
C_1 = 1
C_2 = 2
C_3 = 5
C_4 = 14
C_5 = 42
C_6 = 132
C_7 = 429
C_8 = 1430
C_9 = 4862
C_10 = 16796
C_11 = 58786
C_12 = 208012
C_13 = 742900
C_14 = 2674440

Of course, this code also works unchanged (apart from extending the loop) for producing higher Catalan numbers. For example, here is the end of the output when asked to produce the first fifty:

C_45 = 2257117854077248073253720
C_46 = 8740328711533173390046320
C_47 = 33868773757191046886429490
C_48 = 131327898242169365477991900
C_49 = 509552245179617138054608572

TypeScript

Translation of: GW-BASIC

// Catalan numbers
var c: number[] = [1];
console.log(`${0}\t${c[0]}`);
for (n = 0; n < 15; n++) {
  c[n + 1] = 0;
  for (i = 0; i <= n; i++)
    c[n + 1] = c[n + 1] + c[i] * c[n - i];
  console.log(`${n + 1}\t${c[n + 1]}`);
}

Output:

Ursala

#import std
#import nat

catalan = quotient^\successor choose^/double ~&

#cast %nL

t = catalan* iota 16

Output:

Vala

namespace CatalanNumbers {
  public class CatalanNumberGenerator {
    private static double factorial(double n) {
      if (n == 0)
        return 1;
      return n * factorial(n - 1);
    }
    
    public double first_method(double n) {
      const double top_multiplier = 2;
      return factorial(top_multiplier * n) / (factorial(n + 1) * factorial(n));
    }

    public double second_method(double n) {
      if (n == 0) {
        return 1;
      }
      double sum = 0;
      double i = 0;
      for (; i <= (n - 1); i++) {
        sum += second_method(i) * second_method((n - 1) - i);
      }
      return sum;
    }

    public double third_method(double n) {
      if (n == 0) {
        return 1;
      }
      return ((2 * (2 * n - 1)) / (n + 1)) * third_method(n - 1);
    }
  }

  void main() {
    CatalanNumberGenerator generator = new CatalanNumberGenerator();
    DateTime initial_time;
    DateTime final_time;
    TimeSpan ts;

    stdout.printf("Direct Method\n");
    stdout.printf(" n%9s\n", "C_n");
    stdout.printf("............\n");
    initial_time = new DateTime.now();
    for (double i = 0; i <= 15; i++) {
      stdout.printf("%2s %8s\n", i.to_string(), Math.ceil(generator.first_method(i)).to_string());
    }
    final_time = new DateTime.now();
    ts = final_time.difference(initial_time);
    stdout.printf("............\n");
    stdout.printf("Time Elapsed: %s μs\n", ts.to_string());

    stdout.printf("\nRecursive Method 1\n");
    stdout.printf(" n%9s\n", "C_n");
    stdout.printf("............\n");
    initial_time = new DateTime.now();
    for (double i = 0; i <= 15; i++) {
      stdout.printf("%2s %8s\n", i.to_string(), Math.ceil(generator.second_method(i)).to_string());
    }
    final_time = new DateTime.now();
    ts = final_time.difference(initial_time);
    stdout.printf("............\n");
    stdout.printf("Time Elapsed: %s μs\n", ts.to_string());

    stdout.printf("\nRecursive Method 2\n");
    stdout.printf(" n%9s\n", "C_n");
    stdout.printf("............\n");
    initial_time = new DateTime.now();
    for (double i = 0; i <= 15; i++) {
      stdout.printf("%2s %8s\n", i.to_string(), Math.ceil(generator.third_method(i)).to_string());
    }
    final_time = new DateTime.now();
    ts = final_time.difference(initial_time);
    stdout.printf("............\n");
    stdout.printf("Time Elapsed: %s μs\n", ts.to_string());

  }
}

Output:

Direct Method
 n      C_n
............
 0        1
 1        1
 2        2
 3        5
 4       14
 5       42
 6      132
 7      429
 8     1430
 9     4862
10    16796
11    58786
12   208012
13   742900
14  2674440
15  9694845
............
Time Elapsed: 132 μs

Recursive Method 1
 n      C_n
............
 0        1
 1        1
 2        2
 3        5
 4       14
 5       42
 6      132
 7      429
 8     1430
 9     4862
10    16796
11    58786
12   208012
13   742900
14  2674440
15  9694845
............
Time Elapsed: 130430 μs

Recursive Method 2
 n      C_n
............
 0        1
 1        1
 2        2
 3        5
 4       14
 5       42
 6      132
 7      429
 8     1430
 9     4862
10    16796
11    58786
12   208012
13   742900
14  2674440
15  9694845
............
Time Elapsed: 76 μs

V (Vlang)

Translation of: Go

import math.big

fn main() {
    mut b:= big.zero_int
    for n := i64(0); n < 15; n++ {
		b = big.integer_from_i64(n)
		b = (b*big.two_int).factorial()/(b.factorial()*(b*big.two_int-b).factorial())
        println(b/big.integer_from_i64(n+1))
    }
}

Output:

Wortel

; the following number expression calculcates the nth Catalan number
#~ddiFSFmSoFSn
; which stands for: dup dup inc fac swap fac mult swap double fac swap divide
; to get the first 15 Catalan numbers we map this function over a list from 0 to 15
!*#~ddiFSFmSoFSn @til 15
; returns [1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674439.9999999995]

Wren

Library: Wren-fmt

Library: Wren-math

import "./fmt" for Fmt
import "./math" for Int
 
var catalan = Fn.new { |n|
    if (n < 0) Fiber.abort("Argument must be a non-negative integer")
    var prod = 1
    var i = n + 2
    while (i <= n * 2) {
        prod = prod * i
        i = i + 1
    }
    return prod / Int.factorial(n)
}

var catalanRec
catalanRec = Fn.new { |n| (n != 0) ? 2 * (2 * n - 1) * catalanRec.call(n - 1) / (n + 1) : 1 }

System.print(" n  Catalan number")
System.print("------------------")
for (i in 0..15) System.print("%(Fmt.d(2, i))  %(catalan.call(i))")
System.print("\nand again using a recursive function:\n")
for (i in 0..15) System.print("%(Fmt.d(2, i))  %(catalanRec.call(i))")

Output:

 n  Catalan number
------------------
 0  1
 1  1
 2  2
 3  5
 4  14
 5  42
 6  132
 7  429
 8  1430
 9  4862
10  16796
11  58786
12  208012
13  742900
14  2674440
15  9694845

and again using a recursive function:

 0  1
 1  1
 2  2
 3  5
 4  14
 5  42
 6  132
 7  429
 8  1430
 9  4862
10  16796
11  58786
12  208012
13  742900
14  2674440
15  9694845

XLISP

(defun catalan (n)
	(if (= n 0)
		1
		(* (/ (* 2 (- (* 2 n) 1)) (+ n 1)) (catalan (- n 1))) ) )

(defun range (x y)
	(cons x
		(if (< x y)
			(range (+ x 1) y) ) ) )

(print (mapcar catalan (range 0 14)))

Output:

(1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440)

XPL0

code CrLf=9, IntOut=11;
int  C, N;
[C:= 1;
IntOut(0, C);  CrLf(0);
for N:= 1 to 14 do
    [C:= C*2*(2*N-1)/(N+1);
    IntOut(0, C);  CrLf(0);
    ];
]

Output:

zkl

Uses GMP to calculate big factorials.

var BN=Import("zklBigNum");
fcn catalan(n){
   BN(2*n).factorial() / BN(n+1).factorial() / BN(n).factorial();
}

foreach n in (16){
   println("%2d --> %,d".fmt(n, catalan(n)));
}
println("%2d --> %,d".fmt(100, catalan(100)));

And an iterative solution at works up to the limit of 64 bit ints (n=33). Would be 35 but need to avoid factional intermediate results.

fcn catalan(n){ (1).reduce(n,fcn(p,n){ 2*(2*n-1)*p/(n+1) },1) }

Output:

 0 --> 1
 1 --> 1
 2 --> 2
 3 --> 5
 4 --> 14
 5 --> 42
 6 --> 132
 7 --> 429
 8 --> 1,430
 9 --> 4,862
10 --> 16,796
11 --> 58,786
12 --> 208,012
13 --> 742,900
14 --> 2,674,440
15 --> 9,694,845
100 --> 896,519,947,090,131,496,687,170,070,074,100,632,420,837,521,538,745,909,320

ZX Spectrum Basic

Translation of: C

10 FOR i=0 TO 15
20 LET n=i: LET m=2*n
30 LET r=1: LET d=m-n
40 IF d>n THEN LET n=d: LET d=m-n
50 IF m<=n THEN GO TO 90
60 LET r=r*m: LET m=m-1
70 IF (d>1) AND NOT FN m(r,d) THEN LET r=r/d: LET d=d-1: GO TO 70
80 GO TO 50
90 PRINT i;TAB 4;r/(1+n)
100 NEXT i
110 STOP 
120 DEF FN m(a,b)=a-INT (a/b)*b: REM Modulus function