Catalan numbers

From Rosetta Code
Jump to: navigation, search
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)
Task
Catalan numbers
You are encouraged to solve this task according to the task description, using any language you may know.
Catalan numbers are a sequence of numbers which can be defined directly:
C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!} \qquad\mbox{ for }n\ge 0.

Or recursively:

C_0 = 1 \quad \mbox{and} \quad C_{n+1}=\sum_{i=0}^{n}C_i\,C_{n-i}\quad\text{for }n\ge 0;

Or alternatively (also recursive):

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.

Contents

[edit] Ada

with Ada.Text_IO;  use Ada.Text_IO;
 
procedure Test_Catalan is
   function Catalan (N : Natural) return Natural is
      Result : Positive := 1;
   begin
      for I in 1..N loop
         Result := Result * 2 * (2 * I - 1) / (I + 1);
      end loop;
      return Result;
   end Catalan;
begin
   for N in 0..15 loop
      Put_Line (Integer'Image (N) & " =" & Integer'Image (Catalan (N)));
   end loop;
end Test_Catalan;
Sample output:
 0 = 1
 1 = 1
 2 = 2
 3 = 5
 4 = 14
 5 = 42
 6 = 132
 7 = 429
 8 = 1430
 9 = 4862
 10 = 16796
 11 = 58786
 12 = 208012
 13 = 742900
 14 = 2674440
 15 = 9694845

[edit] 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

[edit] AWK

# syntax: GAWK -f CATALAN_NUMBERS.AWK
BEGIN {
    for (i=0; i<=15; i++) {
      printf("%2d %10d\n",i,catalan(i))
    }
    exit(0)
}
function catalan(n,  ans) {
    if (n == 0) {
      ans = 1
    }
    else {
      ans = ((2*(2*n-1))/(n+1))*catalan(n-1)
    }
    return(ans)
}
Output:
 0          1
 1          1
 2          2
 3          5
 4         14
 5         42
 6        132
 7        429
 8       1430
 9       4862
10      16796
11      58786
12     208012
13     742900
14    2674440
15    9694845

[edit] 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

[edit] BBC BASIC

      FOR i% = 1 TO 15
        PRINT FNcatalan(i%)
      NEXT
      END
 
      DEF FNcatalan(n%)
      IF n% = 0 THEN = 1
      = 2 * (2 * n% - 1) * FNcatalan(n% - 1) / (n% + 1)
Output:
         1
         2
         5
        14
        42
       132
       429
      1430
      4862
     16796
     58786
    208012
    742900
   2674440
   9694845

[edit] 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))
    )
&
);
Output:
straight
C0 = 1
C1 = 1
C2 = 2
C3 = 5
C4 = 14
C5 = 42
C6 = 132
C7 = 429
C8 = 1430
C9 = 4862
C10 = 16796
C11 = 58786
C12 = 208012
C13 = 742900
C14 = 2674440
C15 = 9694845
recursive, with memoization, without fractions
C0 = 1
C1 = 1
C2 = 2
C3 = 5
C4 = 14
C5 = 42
C6 = 132
C7 = 429
C8 = 1430
C9 = 4862
C10 = 16796
C11 = 58786
C12 = 208012
C13 = 742900
C14 = 2674440
C15 = 9694845
recursive, without memoization, with fractions
C0 = 1
C1 = 1
C2 = 2
C3 = 5
C4 = 14
C5 = 42
C6 = 132
C7 = 429
C8 = 1430
C9 = 4862
C10 = 16796
C11 = 58786
C12 = 208012
C13 = 742900
C14 = 2674440
C15 = 9694845

[edit] 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

[edit] 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

[edit] C# 

namespace CatalanNumbers
{
    /// <summary>
    /// Class that holds all options.
    /// </summary>
    public class CatalanNumberGenerator
    {
        private static double Factorial(double n)
        {
            if (n == 0)
                return 1;
 
            return n * Factorial(n - 1);
        }
 
        public double FirstOption(double n)
        {
            const double topMultiplier = 2;
            return Factorial(topMultiplier * n) / (Factorial(n + 1) * Factorial(n));
        }
 
        public double SecondOption(double n)
        {
            if (n == 0)
            {
                return 1;
            }
            double sum = 0;
            double i = 0;
            for (; i <= (n - 1); i++)
            {
                sum += SecondOption(i) * SecondOption((n - 1) - i);
            }
            return sum;
        }
 
        public double ThirdOption(double n)
        {
            if (n == 0)
            {
                return 1;
            }
            return ((2 * (2 * n - 1)) / (n + 1)) * ThirdOption(n - 1);
        }
    }
}
 
 
// Program.cs
using System;
using System.Configuration;
 
// Main program
// Be sure to add the following to the App.config file and add a reference to System.Configuration:
// <?xml version="1.0" encoding="utf-8" ?>
// <configuration>
//  <appSettings>
//    <clear/>
//    <add key="MaxCatalanNumber" value="50"/>
//  </appSettings>
// </configuration>
namespace CatalanNumbers
{
    class Program
    {
        static void Main(string[] args)
        {
            CatalanNumberGenerator generator = new CatalanNumberGenerator();
            int i = 0;
            DateTime initial;
            DateTime final;
            TimeSpan ts;
 
            try
            {
                initial = DateTime.Now;
                for (; i <= Convert.ToInt32(ConfigurationManager.AppSettings["MaxCatalanNumber"]); i++)
                {
                    Console.WriteLine("CatalanNumber({0}):{1}", i, generator.FirstOption(i));
                }
                final = DateTime.Now;
                ts = final - initial;
                Console.WriteLine("It took {0}.{1} to execute\n", ts.Seconds, ts.Milliseconds);
 
                i = 0;
                initial = DateTime.Now;
                for (; i <= Convert.ToInt32(ConfigurationManager.AppSettings["MaxCatalanNumber"]); i++)
                {
                    Console.WriteLine("CatalanNumber({0}):{1}", i, generator.SecondOption(i));
                }
                final = DateTime.Now;
                ts = final - initial;
                Console.WriteLine("It took {0}.{1} to execute\n", ts.Seconds, ts.Milliseconds);   
 
                i = 0;
                initial = DateTime.Now;
                for (; i <= Convert.ToInt32(ConfigurationManager.AppSettings["MaxCatalanNumber"]); i++)
                {
                    Console.WriteLine("CatalanNumber({0}):{1}", i, generator.ThirdOption(i));
                }
                final = DateTime.Now;
                ts = final - initial;
                Console.WriteLine("It took {0}.{1} to execute", ts.Seconds, ts.Milliseconds, ts.TotalMilliseconds);
                Console.ReadLine();
            }
            catch (Exception ex)
            {
                Console.WriteLine("Stopped at index {0}:", i);
                Console.WriteLine(ex.Message);
                Console.ReadLine();
            }
        }
    }
}
Output:
CatalanNumber(0):1
CatalanNumber(1):1
CatalanNumber(2):2
CatalanNumber(3):5
CatalanNumber(4):14
CatalanNumber(5):42
CatalanNumber(6):132
CatalanNumber(7):429
CatalanNumber(8):1430
CatalanNumber(9):4862
CatalanNumber(10):16796
CatalanNumber(11):58786
CatalanNumber(12):208012
CatalanNumber(13):742900
CatalanNumber(14):2674440
CatalanNumber(15):9694845
It took 0.14 to execute

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

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

[edit] C++

[edit] 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

[edit] 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)

[edit] 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))))

[edit] D

import std.stdio, std.bigint, std.functional;
 
BigInt factorial(uint n) {
    alias memoize!factorial mfact;
    return n ? mfact(n - 1) * n : BigInt(1);
}
 
auto cats1(uint n) {
    return factorial(2 * n) / (factorial(n + 1) * factorial(n));
}
 
BigInt cats2(uint n) {
    alias memoize!cats2 mcats2;
    if (n == 0) return BigInt(1);
    auto sum = BigInt(0);
    foreach (i; 0 .. n)
        sum += mcats2(i) * mcats2(n - 1 - i);
    return sum;
}
 
BigInt cats3(uint n) {
    alias memoize!cats3 mcats3;
    return n ? (4*n - 2) * mcats3(n - 1) / (n + 1) : BigInt(1);
}
 
void main() {
    foreach (i; 0 .. 15)
        writefln("%2d => %s %s %s", i, cats1(i), cats2(i), cats3(i));
}
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

[edit] 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]

[edit] Euphoria

--Catalan number task from Rosetta Code wiki
--User:Lnettnay
 
--function from factorial task
function factorial(integer n)
atom f = 1
while n > 1 do
        f *= n
        n -= 1
end while
 
return f
end function
 
function catalan(integer n)  
atom numerator = factorial(2 * n)
atom denominator = factorial(n+1)*factorial(n)
return numerator/denominator
end function
 
for i = 0 to 15 do
        ? catalan(i)
end for
Output:
1                                                                                                                                                                             
1                                                                                                                                                                             
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440
9694845

[edit] Factor

This is the last solution, memoized by using arrays. Run in scratchpad. 

: next ( seq -- newseq )
  [ ] [ last ] [ length ] tri
  [ 2 * 1 - 2 * ] [ 1 + ] bi /
  * suffix ;
: Catalan ( n -- seq )  V{ 1 } swap 1 - [ next ] times ;
15 Catalan .
V{
    1
    1
    2
    5
    14
    42
    132
    429
    1430
    4862
    16796
    58786
    208012
    742900
    2674440
}

[edit] Fantom

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

[edit] Forth

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

[edit] Fortran

Works with: Fortran version 90 and later
program main
  !=======================================================================================
  implicit none
 
  !=== Local data
  integer                      :: n
 
  !=== External procedures
  double precision, external   :: catalan_numbers         
 
  !=== Execution =========================================================================
 
  write(*,'(1x,a)')'==============='
  write(*,'(5x,a,6x,a)')'n','c(n)'
  write(*,'(1x,a)')'---------------'
 
  do n = 0, 14
    write(*,'(1x,i5,i10)') n, int(catalan_numbers(n))
  enddo
 
  write(*,'(1x,a)')'==============='
 
  !=======================================================================================
end program main
!BL
!BL
!BL
double precision recursive function catalan_numbers(n) result(value)
  !=======================================================================================
  implicit none
 
  !=== Input, ouput data
  integer, intent(in)          :: n
 
  !=== Execution =========================================================================
 
  if ( n .eq. 0 ) then
    value = 1
  else 
    value = ( 2.0d0 * dfloat(2 * n - 1) / dfloat( n + 1 ) ) * catalan_numbers(n-1)
  endif
 
  !=======================================================================================
end function catalan_numbers
Output:
 ===============
     n      c(n)
 ---------------
     0         1
     1         1
     2         2
     3         5
     4        14
     5        42
     6       132
     7       429
     8      1430
     9      4862
    10     16796
    11     58786
    12    208012
    13    742900
    14   2674440
 ===============

[edit] 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]]

[edit] GAP

Catalan1 := function(n)
	return Binomial(2*n, n) - Binomial(2*n, n - 1);
end;
 
Catalan2 := function(n)
	return Binomial(2*n, n)/(n + 1);
end;
 
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], n -> Catalan1(n));
List([0 .. 14], n -> Catalan2(n));
List([0 .. 14], n -> Catalan3(n));
List([0 .. 14], n -> Catalan4(n));
# Same output for all four:
# [ 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440 ]

[edit] 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

[edit] Haskell

-- Three infinite lists, corresponding to the three definitions in the problem
-- statement.
 
cats1 = map (\n -> product [n+2..2*n] `div` product [1..n]) [0..]
 
cats2 = 1 : map (\n -> sum $ zipWith (*) (reverse (take n cats2)) cats2) [1..]
 
cats3 = scanl (\c n -> c*2*(2*n-1) `div` (n+1)) 1 [1..]
 
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]

[edit] Icon and Unicon

procedure main(arglist)
every writes(catalan(i)," ")
end
 
procedure catalan(n) # return catalan(n) or fail
static M
initial M := table()
 
if n > 0 then 
   return (n = 1) | \M[n] | ( M[n] := (2*(2*n-1)*catalan(n-1))/(n+1))
end
Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845

[edit] J

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

[edit] Java

Accuracy may be lost for larger n's due to floating-point arithmetic (seen for C(15) here). This implementation is memoized (factorial and Catalan numbers are stored in the Maps "facts", "catsI", "catsR1", and "catsR2"). 

import java.util.HashMap;
import java.util.Map;
 
public class Catalan {
	private static final Map<Long, Double> facts = new HashMap<Long, Double>();
	private static final Map<Long, Double> catsI = new HashMap<Long, Double>();
	private static final Map<Long, Double> catsR1 = new HashMap<Long, Double>();
	private static final Map<Long, Double> catsR2 = new HashMap<Long, Double>();
 
	static{//pre-load the memoization maps with some answers 
		facts.put(0L, 1D);
		facts.put(1L, 1D);
		facts.put(2L, 2D);
 
		catsI.put(0L, 1D);
		catsR1.put(0L, 1D);
		catsR2.put(0L, 1D);
	}
 
	private static double fact(long n){
		if(facts.containsKey(n)){
			return facts.get(n);
		}
		double fact = 1;
		for(long i = 2; i <= n; i++){
			fact *= i; //could be further optimized, but it would probably be ugly
		}
		facts.put(n, fact);
		return fact;
	}
 
	private static double catI(long n){
		if(!catsI.containsKey(n)){
			catsI.put(n, fact(2 * n)/(fact(n+1)*fact(n)));
		}
		return catsI.get(n);
	}
 
	private static double catR1(long n){
		if(catsR1.containsKey(n)){
			return catsR1.get(n);
		}
		double sum = 0;
		for(int i = 0; i < n; i++){
			sum += catR1(i) * catR1(n - 1 - i);
		}
		catsR1.put(n, sum);
		return sum;
	}
 
	private static double catR2(long n){
		if(!catsR2.containsKey(n)){
			catsR2.put(n, ((2.0*(2*(n-1) + 1))/(n + 1)) * catR2(n-1));
		}
		return catsR2.get(n);
	}
 
	public static void main(String[] args){
		for(int i = 0; i <= 15; i++){
			System.out.println(catI(i));
			System.out.println(catR1(i));
			System.out.println(catR2(i));
		}
	}
}
Output:
1.0
1.0
1.0
1.0
1.0
1.0
2.0
2.0
2.0
5.0
5.0
5.0
14.0
14.0
14.0
42.0
42.0
42.0
132.0
132.0
132.0
429.0
429.0
429.0
1430.0
1430.0
1430.0
4862.0
4862.0
4862.0
16796.0
16796.0
16796.0
58786.0
58786.0
58786.0
208012.0
208012.0
208012.0
742900.0
742900.0
742900.0
2674439.9999999995
2674440.0
2674440.0
9694844.999999998
9694845.0
9694845.0

[edit] 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

[edit] Julia

From the Catalan package, returns the n-th Catalan number 

function catalan(bn::Integer)
    if bn < 0
        throw(DomainError())
    else
        n = BigInt(bn)
    end
    return binomial(2n, n)/(n + 1)
end
Output:
julia>  for n = 1:15 println(catalan(n)) end
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440
9694845

[edit] K

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

[edit] Liberty BASIC

print "non-recursive version"
print catNonRec(5)
for i = 0 to 15
    print i;"   =   "; catNonRec(i)
next
print
 
print "recursive version"
print catRec(5)
for i = 0 to 15
    print i;"   =   "; catRec(i)
next
print
 
print "recursive with memoisation"
redim cats(20)  'clear the array
print catRecMemo(5)
for i = 0 to 15
    print i;"   =   "; catRecMemo(i)
next
print
 
 
wait
 
function catNonRec(n)   'non-recursive version
    catNonRec=1
    for i=1 to n
        catNonRec=((2*((2*i)-1))/(i+1))*catNonRec
    next
end function
 
function catRec(n)  'recursive version
    if n=0 then
        catRec=1
    else
        catRec=((2*((2*n)-1))/(n+1))*catRec(n-1)
    end if
end function
 
function catRecMemo(n)  'recursive version with memoisation
    if n=0 then
        catRecMemo=1
    else
        if cats(n-1)=0 then    'call it recursively only if not already calculated
            prev = catRecMemo(n-1)
        else
            prev = cats(n-1)
        end if
        catRecMemo=((2*((2*n)-1))/(n+1))*prev
    end if
    cats(n) = catRecMemo    'memoisation for future use
end function
Output:
non-recursive version
42
0   =   1
1   =   1
2   =   2
3   =   5
4   =   14
5   =   42
6   =   132
7   =   429
8   =   1430
9   =   4862
10   =   16796
11   =   58786
12   =   208012
13   =   742900
14   =   2674440
15   =   9694845

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

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

[edit] Lua

-- recursive with memoization
catalan = {[0] = 1}
setmetatable(catalan, {
	__index = function(c, n)
			c[n] = c[n-1]*2*(2*n-1)/(n+1)
			return c[n]
		end
	}
)
 
for i=0,14 do
	print(catalan[i])
end
Output:
1
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440

[edit] Mathematica

CatalanN[n_Integer /; n >= 0] := (2 n)!/((n + 1)! n!)
Sample Output:
TableForm[CatalanN/@Range[0,15]]
//TableForm= 
1
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440
9694845

[edit] MATLAB / Octave

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

The following version is fully vectorized and does not require a loop 

function n = catalanNumbers(n)
    n = prod(n+1:2*n)/prod(1:n+1);
end
Sample Output:
>> catalanNumbers(14)
 
ans =
 
     2674440
 
>> catalanNumbers((0:17))'
 
ans =
 
           1
           1
           2
           5
          14
          42
         132
         429
        1430
        4862
       16796
       58786
      208012
      742900
     2674440
     9694845
    35357670
   129644790

[edit] Maxima

/* The following is an array function, hence the square brackets. It uses memoization automatically */
cata[n] := sum(cata[i]*cata[n - 1 - i], i, 0, n - 1)$
cata[0]: 1$
 
cata2(n) := binomial(2*n, n)/(n + 1)$
 
makelist(cata[n], n, 0, 14);
 
makelist(cata2(n), n, 0, 14);
 
/* both return [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440] */

[edit] 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
-- memorization 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 20
 
  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) + 1)) / (n + 1)) * self~catR2(n - 1)) / 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) = 742899.99999999999999
catR1(13) = 742900
catR2(13) = 742900.00000000000001
catI(14) = 2674440.0000000000001
catR1(14) = 2674440
catR2(14) = 2674440
catI(15) = 9694845.0000000000001
catR1(15) = 9694845
catR2(15) = 9694845

[edit] 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))

[edit] 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

[edit] Perl

sub f { $_[0] ? $_[0] * f($_[0]-1) : 1 }
sub catalan { f(2 * $_[0]) / f($_[0]) / f($_[0]+1) }
 
print "$_\t@{[ catalan($_) ]}\n" for 0 .. 20;

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

my @c = (1);
sub catalan { 
        use bigint;
        $c[$_[0]] //= catalan($_[0]-1) * (4 * $_[0]-2) / ($_[0]+1)
}
 
# most of the time is spent displaying the long numbers, actually
print "$_\t", catalan($_), "\n" for 0 .. 10000;

[edit] Perl 6

my @catalan := 1, { (state $n)++; 2*(2*$n-1)/($n+1) * $_ } ... *;
 
.say for @catalan[^15];
Output:
1
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440

[edit] 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

[edit] 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) (pack (char (hash N)) 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

[edit] 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

[edit] PlainTeX

\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

[edit] 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 .

[edit] PureBasic

Using the third formula... 

; saving the division for last ensures we divide the largest
; numerator by the smallest denominator
 
Procedure.q CatalanNumber(n.q)
If n<0:ProcedureReturn 0:EndIf
If n=0:ProcedureReturn 1:EndIf
ProcedureReturn (2*(2*n-1))*CatalanNumber(n-1)/(n+1)
EndProcedure
 
ls=25
rs=12
 
a.s=""
a.s+LSet(RSet("n",rs),ls)+"CatalanNumber(n)"
; cw(a.s)
Debug a.s
 
For n=0 to 33 ;33 largest correct quad for n 
a.s=""
a.s+LSet(RSet(Str(n),rs),ls)+Str(CatalanNumber(n))
; cw(a.s)
Debug a.s
Next
Sample Output:
           n             CatalanNumber(n)
           0             1
           1             1
           2             2
           3             5
           4             14
           5             42
           6             132
           7             429
           8             1430
           9             4862
          10             16796
          11             58786
          12             208012
          13             742900
          14             2674440
          15             9694845
          16             35357670
          17             129644790
          18             477638700
          19             1767263190
          20             6564120420
          21             24466267020
          22             91482563640
          23             343059613650
          24             1289904147324
          25             4861946401452
          26             18367353072152
          27             69533550916004
          28             263747951750360
          29             1002242216651368
          30             3814986502092304
          31             14544636039226909
          32             55534064877048198
          33             212336130412243110

[edit] 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. 

from math import factorial
import functools
 
def memoize(func):
    cache = {}
    def memoized(key):
        # Returned, new, memoized version of decorated function
        if key not in cache:
            cache[key] = func(key)
        return cache[key]
    return functools.update_wrapper(memoized, func)
 
 
@memoize
def fact(n):
    return factorial(n)
 
def cat_direct(n):
    return fact(2*n) // fact(n + 1) // fact(n)
 
@memoize    
def catR1(n):
    return ( 1 if n == 0
             else sum( catR1(i) * catR1(n - 1 - i)
                       for i in range(n) ) )
 
@memoize    
def catR2(n):
    return ( 1 if n == 0
             else ( ( 4 * n - 2 ) * catR2( n - 1) ) // ( n + 1 ) )
 
 
if __name__ == '__main__':
    def pr(results):
        fmt = '%-10s %-10s %-10s'
        print ((fmt % tuple(c.__name__ for c in defs)).upper())
        print (fmt % (('='*10,)*3))
        for r in zip(*results):
            print (fmt % r)
 
 
    defs = (cat_direct, catR1, catR2)
    results = [ tuple(c(i) for i in range(15)) for c in defs ]
    pr(results)
Sample Output:
CAT_DIRECT CATR1      CATR2     
========== ========== ==========
1          1          1         
1          1          1         
2          2          2         
5          5          5         
14         14         14        
42         42         42        
132        132        132       
429        429        429       
1430       1430       1430      
4862       4862       4862      
16796      16796      16796     
58786      58786      58786     
208012     208012     208012    
742900     742900     742900    
2674440    2674440    2674440

[edit] R

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

[edit] 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)

[edit] REXX

All methods use memoization. 

/*REXX program calculates Catalan numbers using three different methods.*/
parse arg bot top .                    /*get args from the command line.*/
if bot=='' then do; top=15; bot=0; end /*No args? Use a range of 0 ─► 15*/
if top=='' then top=bot                /*No top?  Use the bottom for it.*/
numeric digits max(20,5*top)           /*no limit on big Catalan numbers*/
w=length(top)                          /*use  W  to align Catalan index.*/
 
say;  say center(' Catalan numbers, method 1 ' , 79, '-');    !.=0
                          do m1=bot  to top
                          say right(m1,w)  '='  catalan1(m1)
                          end     /*m1*/
 
say;  say center(' Catalan numbers, method 2 ' , 79, '-');    c.=0;  c.0=1
                          do m2=bot  to top
                          say right(m2,w)  '='  catalan2(m2)
                          end     /*m2*/
 
say;  say center(' Catalan numbers, method 3 ' , 79, '-');    c.=0;  c.0=1
                          do m3=bot  to top
                          say right(m3,w)  '='  catalan3(m3)
                          end     /*m3*/
exit                                   /*stick a fork in it, we're done.*/
 
/*──────────────────────────────────catalan method 1────────────────────*/
catalan1: procedure expose !.; parse arg n  /*n+n  is faster than  2*n  */
return !(n+n)  %    ( (n+1)  *  !(n)**2 )   /*using COMB would be faster*/
 
/*──────────────────────────────────catalan method 2────────────────────*/
catalan2: procedure expose c.; parse arg n; if c.n\==0 then return c.n
s=0;     do j=0  to  n-1
         s=s   +   catalan2(j) * catalan2(n-j-1)    /*recursive invokes.*/
         end   /*j*/
c.n=s                                  /*use REXX memoization technique.*/
return s
 
/*──────────────────────────────────catalan method 3────────────────────*/
catalan3: procedure expose c.; parse arg n;  if c.n\==0 then return c.n
c.n=(4*n-2) * catalan3(n-1) % (n+1)    /*use REXX memoization technique.*/
return c.n
 
/*──────────────────────────────────! (factorial) function──────────────*/
!: procedure expose !.;   parse arg x;   if !.x\==0 then return !.x;   !=1
            do k=1  for x
            !=!*k
            end   /*k*/
!.x=!                                  /*use REXX memoization technique.*/
return !

output when using the input of: 0 16 

-------------------------- Catalan numbers, method 1 --------------------------
 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

-------------------------- Catalan numbers, method 2 --------------------------
 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

-------------------------- Catalan numbers, method 3 --------------------------
 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

[edit] Ruby

Using a memoization module found at the Ruby Application Archive. 

# direct
 
def factorial(n)
  (1..n).reduce(:*)
end
 
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-1).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(10) do |b|
  b.report('forget') {
    16.times {|n| [n, catalan_direct(n), catalan_rec1(n), catalan_rec2(n)]}
  }
  b.report('memoized') {
    memoize :factorial
    memoize :catalan_direct
    memoize :catalan_rec1
    memoize :catalan_rec2
    16.times {|n| [n, catalan_direct(n), catalan_rec1(n), catalan_rec2(n)]}
  }
end
 
16.times {|n| p [n, catalan_direct(n), catalan_rec1(n), catalan_rec2(n)]}

The output shows the dramatic difference memoizing makes. 

                user     system      total        real
forget     11.578000   0.000000  11.578000 ( 11.687000)
memoized    0.000000   0.000000   0.000000 (  0.000000)
[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]

[edit] Run BASIC

FOR i = 1 TO 15
    PRINT i;" ";catalan(i)
NEXT
 
FUNCTION catalan(n) 
  IF n = 0 THEN 
      catalan = 1
  ELSE
      catalan = ((2 * ((2 * n) - 1)) / (n + 1)) * catalan(n - 1)
 END IF
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

[edit] Scala

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

object Catalan {
  def factorial(n: BigInt) = BigInt(1).to(n).foldLeft(BigInt(1))(_ * _)
  def catalan(n: BigInt) = factorial(2 * n) / (factorial(n + 1) * factorial(n))
 
  def main(args: Array[String]) {
    for (n <- 1 to 15) {
      println("catalan(" + n + ") = " + catalan(n))
    }
  }
}
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

[edit] 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

[edit] Seed7

$ include "seed7_05.s7i";
  include "bigint.s7i";
 
const proc: main is func
  local
    var bigInteger: n is 0_;
  begin
    for n range 0_ to 15_ do
      writeln((2_ * n) ! n div succ(n));
    end for;
  end func;
Output:
1
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440
9694845

[edit] 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
 *)

[edit] Tcl

package require Tcl 8.5
 
# Memoization wrapper
proc memoize {function value generator} {
    variable memoize
    set key $function,$value
    if {![info exists memoize($key)]} {
	set memoize($key) [uplevel 1 $generator]
    }
    return $memoize($key)
}
 
# The simplest recursive definition
proc tcl::mathfunc::catalan n {
    if {[incr n 0] < 0} {error "must not be negative"}
    memoize catalan $n {expr {
	$n == 0 ? 1 : 2 * (2*$n - 1) * catalan($n - 1) / ($n + 1)
    }}
}

Demonstration: 

for {set i 0} {$i < 15} {incr i} {
    puts "C_$i = [expr {catalan($i)}]"
}
Output:
C_0 = 1
C_1 = 1
C_2 = 2
C_3 = 5
C_4 = 14
C_5 = 42
C_6 = 132
C_7 = 429
C_8 = 1430
C_9 = 4862
C_10 = 16796
C_11 = 58786
C_12 = 208012
C_13 = 742900
C_14 = 2674440

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

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

[edit] 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

[edit] 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>

[edit] VBA

Public Sub Catalan1(n As Integer)
'Computes the first n Catalan numbers according to the first recursion given
Dim Cat() As Long
Dim sum As Long
 
ReDim Cat(n)
Cat(0) = 1
For i = 0 To n - 1
  sum = 0
  For j = 0 To i
    sum = sum + Cat(j) * Cat(i - j)
  Next j
  Cat(i + 1) = sum
Next i
Debug.Print
For i = 0 To n
  Debug.Print i, Cat(i)
Next
End Sub
 
Public Sub Catalan2(n As Integer)
'Computes the first n Catalan numbers according to the second recursion given
Dim Cat() As Long
 
ReDim Cat(n)
Cat(0) = 1
For i = 1 To n
  Cat(i) = 2 * Cat(i - 1) * (2 * i - 1) / (i + 1)
Next i
Debug.Print
For i = 0 To n
  Debug.Print i, Cat(i)
Next
End Sub
Result:
Catalan1 15

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

(Expect same result with "Catalan2 15")

[edit] 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
Retrieved from "http://rosettacode.org/mw/index.php?title=Catalan_numbers&oldid=157262"
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox