I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

# 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
You are encouraged to solve this task according to the task description, using any language you may know.

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

${\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},}$

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.

## 11l

V c = 1L(n) 1..15   print(c)   c = 2 * (2 * n - 1) * c I/ (n + 1)
Output:
1
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440


## 360 Assembly

Very compact version.

CATALAN  CSECT        08/09/2015         USING  CATALAN,R15         LA     R7,1               c=1         LA     R6,1               i=1LOOPI    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 iELOOPI   BR     R14PG       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!

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)  ODRETURN
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


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_nend.
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:
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440
9694845

## AWK

# syntax: GAWK -f CATALAN_NUMBERS.AWKBEGIN {    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


### GW-BASIC

10 DIM C(15)20 C(0) = 130 PRINT 0, C(0)40 FOR N = 0 to 1450 C(N+1) = 060 FOR I = 0 TO N70 C(N+1) = C(N+1) + C(I)*C(N-I)80 NEXT I90 PRINT N+1, C(N+1)100 NEXT N 

### Minimal BASIC

Translation of: GW-BASIC
 10 REM Catalan numbers20 DIM C(15)30 LET C(0) = 140 PRINT 0, C(0)50 FOR N = 0 TO 1460 LET C(N+1) = 070 FOR I = 0 TO N80 LET C(N+1) = C(N+1)+C(I)*C(N-I)90 NEXT I100 PRINT N+1, C(N+1)110 NEXT N120 END 

### 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 130100 PRINT N,FX/(B*A)110 NEXT N120 STOP130 LET FX=1140 FOR I=1 TO X150 LET FX=FX*I160 NEXT I170 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

### 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.

 10 LET N = 020 LET C = 130 print N," ",C40 IF N > 9 THEN END50 LET N = N + 160 GOSUB 10070 LET C = (2*N - 1)*C80 LET C = 2*C/(N+1) + 2*I*(2*N-1)90 GOTO 30100 LET I = 0 REM to avoid internal overflow, I subtract something clever from110 IF C <= 0 THEN RETURN   REM C and then add it back at the end120 LET C = C - (N+1)130 LET I = I + 1140 GOTO 110
Output:
0 1
1 1
2 2
3 5
4 14
5 42
6 132
7 429
8 1430
9 4862
10 16796

## 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 sumend 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 "-", "-----", "------", "-----"printfor 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:
         1
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440

## Befunge

0>:.:000p1>\:00g-#v_vv 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 ## 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: straightC0 = 1C1 = 1C2 = 2C3 = 5C4 = 14C5 = 42C6 = 132C7 = 429C8 = 1430C9 = 4862C10 = 16796C11 = 58786C12 = 208012C13 = 742900C14 = 2674440C15 = 9694845recursive, with memoization, without fractionsC0 = 1C1 = 1C2 = 2C3 = 5C4 = 14C5 = 42C6 = 132C7 = 429C8 = 1430C9 = 4862C10 = 16796C11 = 58786C12 = 208012C13 = 742900C14 = 2674440C15 = 9694845recursive, without memoization, with fractionsC0 = 1C1 = 1C2 = 2C3 = 5C4 = 14C5 = 42C6 = 132C7 = 429C8 = 1430C9 = 4862C10 = 16796C11 = 58786C12 = 208012C13 = 742900C14 = 2674440C15 = 9694845Using 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  ## 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¨ ↕15Cat1¨ ↕15Cat2¨ ↕15 Output: ⟨ 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 ⟩ ## 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.csusing 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) ## 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)))) ## 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_iend # 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) endend 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. ## EasyLang func catalan n . ans . if n = 0 ans = 1 else call catalan n - 1 h ans = 2 * (2 * n - 1) * h div (1 + n) ..for i range 15 call catalan i h print h. Output: 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440  ## 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 [email protected]@[email protected]@[email protected]@[email protected]#@[email protected] [email protected]@[email protected]@[email protected]@[email protected]@ [email protected]@[email protected][email protected]@[email protected]@ [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: 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440  ## 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))] endend 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 FOREND PROCEDURE BEGIN FOR N=0 TO 15 DO CATALAN(N->RES) PRINT(N;"=";RES) END FOREND 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 taskfunction factorial(integer n)atom f = 1while n > 1 do f *= n n -= 1end while return fend function function catalan(integer n) atom numerator = factorial(2 * n)atom denominator = factorial(n+1)*factorial(n)return numerator/denominatorend function for i = 0 to 15 do ? catalan(i)end for Output: 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845  ## 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: 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440  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!BLdouble 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 ===============  ## 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 sumEnd 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 "-", "-----", "------", "-----"PrintFor i As UInteger = 0 To 15 Print i, catalan1(i), catalan2(i), catalan3(i)NextPrintPrint "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  ## 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.chooseimport 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, However they run on execution servers. By default remote servers are used, but they are limited in memory and processing power, since they are intended for demonstration and casual use. A local server can be downloaded and installed, it has no limitations (it runs in your own computer). Because of that, example programs can be fully visualized and edited, but some of them will not run if they require a moderate or heavy computation/memory resources, and no local server is being used. In this page you can see the program(s) related to this task and their results. ## 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: 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440  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: 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845  ## 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: 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845  ## 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: 0: 1 1: 1 2: 2 3: 5 4: 14 5: 42 6: 132 7: 429 8: 1430 9: 4862 0: 16796 1: 58786 2: 208012 3: 742900 4: 2674440 5: 9694845  ## 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]

## Icon and Unicon

procedure main()every writes(catalan(0 to 14)," ")end procedure catalan(n) # return catalan(n) or failstatic Minitial 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.15x1 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

<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

## 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'!:151 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

## langur

Translation of: Perl

## 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 rEND 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    ENDEND 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    ENDEND 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;    ReadCharEND CatalanNumbers.

## Nim

import mathimport 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 Memoization is not worthwhile; PARI has fast built-in facilities for calculating binomial coefficients and factorials. catalan(n)=binomial(2*n,n+1)/n A 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)) ## 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  ## 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, actuallyprint "$_\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  tablefactorial(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/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 TeX \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: 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440  ## 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 .  ## 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:EndIfIf n=0:ProcedureReturn 1:EndIfProcedureReturn (2*(2*n-1))*CatalanNumber(n-1)/(n+1)EndProcedure ls=25rs=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.sNext 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  ## 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 factorialimport 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) @memoizedef fact(n): return factorial(n) def cat_direct(n): return fact(2 * n) // fact(n + 1) // fact(n) @memoizedef catR1(n): return 1 if n == 0 else ( sum(catR1(i) * catR1(n - 1 - i) for i in range(n)) ) @memoizedef 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 -> Intdef pred(n): '''Predecessor function''' return n - 1 # succ :: Int -> Intdef 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: 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 ## REXX ### version 1 All four methods of calculate the Catalan numbers use independent memoization for the computation of factorials. In the 1st equation, the 2nd 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); endcall hdr 1B; do j=LO to HI; say ' Catalan' right(j, w)": " Cat1B(j); endcall hdr 2 ; do j=LO to HI; say ' Catalan' right(j, w)": " Cat2(j) ; endcall hdr 3 ; do j=LO to HI; say ' Catalan' right(j, w)": " Cat3(j) ; endexit /*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.ncomb: 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,'─'); returnpFact: 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 1000Parse Arg m .If m='' Then m=20Do i=0 To m  c1.i=c1(i)  Endc2.=1Do i=1 To m  c2.i=c2(i)  Endc3.=1Do i=1 To m  im1=i-1  c3.i=2*(2*i-1)*c3.im1/(i+1)  Endl=length(c3.m)hdr=' n' right('c1.n',l),         right('c2.n',l),         right('c3.n',l)Say hdrDo i=0 To m  Say right(i,2) format(c1.i,l),                 format(c2.i,l),                 format(c3.i,l)  EndSay hdrExit c1: ProcedureParse Arg nreturn fact(2*n)/(fact(n)*fact(n+1)) c2: Procedure Expose c2.Parse Arg nres=0Do i=0 To n-1  nmi=n-i-1  res=res+c2.i*c2.nmi  EndReturn res fact: ProcedureParse Arg nf=1Do i=1 To n  f=f*i  EndReturn 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) + nlnext func catalan n     if n = 0 return 1 ok     cat = 2 * (2 * n - 1) * catalan(n - 1) / (n + 1)     return cat

Output:

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


## Ruby

Library: RubyGems
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).inject(0) {|sum, i| sum + 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


## 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
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

## Rust

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

## 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

$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: 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845  ## 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: 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:"!PRINTFOR n = 0 TO 15 PRINT n,"#######":catrec(n)NEXT nPRINT!PRINT PRINT "Non-recursive:"!PRINTFOR 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 = tempEND DEF DEF catnonrec(x) temp = 1 FOR n = 1 TO x temp = (2*((2*n)-1))/(n+1)*temp NEXT n catnonrec = tempEND DEF ## 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 clearset obs 15gen catalan=1 in 1replace catalan=catalan[_n-1]*2*(2*_n-3)/_n in 2/llist, 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 wrapperproc 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 definitionproc 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


## TI-83 BASIC

This problem is perfectly suited for a TI calculator.

:For(I,1,15:Disp (2I)!/((I+1)!I!:End
Output:
               1
2
4
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440
9694845
Done

## TypeScript

Translation of: GW-BASIC
 // Catalan numbersvar 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:
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


## Ursala

#import std#import nat catalan = quotient^\successor choose^/double ~& #cast %nL t = catalan* iota 16
Output:
<
1,
1,
2,
5,
14,
42,
132,
429,
1430,
4862,
16796,
58786,
208012,
742900,
2674440,
9694845>

## 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


## VBA

Public Sub Catalan1(n As Integer)'Computes the first n Catalan numbers according to the first recursion givenDim Cat() As LongDim sum As Long ReDim Cat(n)Cat(0) = 1For i = 0 To n - 1  sum = 0  For j = 0 To i    sum = sum + Cat(j) * Cat(i - j)  Next j  Cat(i + 1) = sumNext iDebug.PrintFor i = 0 To n  Debug.Print i, Cat(i)NextEnd Sub Public Sub Catalan2(n As Integer)'Computes the first n Catalan numbers according to the second recursion givenDim Cat() As Long ReDim Cat(n)Cat(0) = 1For i = 1 To n  Cat(i) = 2 * Cat(i - 1) * (2 * i - 1) / (i + 1)Next iDebug.PrintFor i = 0 To n  Debug.Print i, Cat(i)NextEnd 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 IfEnd Function 'Find the first 15 Catalan numbers.For j = 1 To 15	WScript.StdOut.Write j & " = " & catalan(j)	WScript.StdOut.WriteLineNext
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

## 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:
 1
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440


## 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 Fmtimport "/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 catalanReccatalanRec = 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


## Yabasic

Translation of: FreeBASIC
print "  n   First    Second    Third"print "  -   -----    ------    -----"printfor i = 0 to 15	print i using "###", catalan1(i) using "########", catalan2(i) using "########", catalan3(i) using "########"next iend 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 sumend 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.

## 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:
1
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440


## 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 1520 LET n=i: LET m=2*n30 LET r=1: LET d=m-n40 IF d>n THEN LET n=d: LET d=m-n50 IF m<=n THEN GO TO 9060 LET r=r*m: LET m=m-170 IF (d>1) AND NOT FN m(r,d) THEN LET r=r/d: LET d=d-1: GO TO 7080 GO TO 5090 PRINT i;TAB 4;r/(1+n)100 NEXT i110 STOP 120 DEF FN m(a,b)=a-INT (a/b)*b: REM Modulus function