Catalan numbers: Difference between revisions
No edit summary |
m Updated Julia |
||
Line 1,470: | Line 1,470: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
From the Catalan package, returns the n-th Catalan number |
|||
<lang julia>function catalan( |
<lang julia>function catalan(bn::Integer) |
||
⚫ | |||
if bn < 0 |
|||
throw(DomainError()) |
|||
else |
|||
n = BigInt(bn) |
|||
end |
|||
⚫ | |||
end</lang> |
end</lang> |
||
{{out}} |
{{out}} |
||
< |
<pre>julia> for n = 1:15 println(catalan(n)) end |
||
1 |
1 |
||
2 |
2 |
||
5 |
5 |
||
14 |
14 |
||
42 |
42 |
||
132 |
132 |
||
429 |
429 |
||
1430 |
1430 |
||
4862 |
4862 |
||
16796 |
16796 |
||
58786 |
58786 |
||
208012 |
208012 |
||
742900 |
742900 |
||
2674440 |
|||
2.67444e6 |
|||
9694845</pre> |
|||
9.694845e6</lang> |
|||
=={{header|K}}== |
=={{header|K}}== |
Revision as of 20:11, 6 May 2013
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) |
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:
Or recursively:
Or alternatively (also recursive):
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.
Ada
<lang 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;</lang>
- 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
AutoHotkey
As AutoHotkey has no BigInt, the formula had to be tweaked to prevent overflow. It still fails after n=22 <lang AHK>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 }</lang>
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
AWK
<lang 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)
}</lang>
- 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
Use of REDIM PRESERVE
means this will not work in QBasic (although that could be worked around if desired).
<lang qbasic>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</lang>
- 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
BBC BASIC
<lang bbcbasic> 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)</lang>
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
Bracmat
<lang 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)) )
& );</lang>
- Output:
<lang bracmat>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</lang>
Brat
<lang brat>catalan = { n |
true? n == 0 { 1 } { (2 * ( 2 * n - 1) / ( n + 1 )) * catalan(n - 1) }
}
0.to 15 { n |
p "#{n} - #{catalan n}"
}</lang>
- Output:
0 - 1 1 - 1 2 - 2 3 - 5 4 - 14 5 - 42 6 - 132 7 - 429 8 - 1430 9 - 4862 10 - 16796 11 - 58786 12 - 208012 13 - 742900 14 - 2674440 15 - 9694845
C
All three methods mentioned in the task: <lang c>#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; }</lang>
- 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#
<lang csharp>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(); } } }
}</lang>
- 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) <lang cpp>#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__</lang>
Here is the implementation of the algorithms. The c'tor of each class tells us the algorithm which will be used. (algorithms.cpp) <lang 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)); }</lang>
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) <lang cpp>#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__</lang>
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) <lang 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; }</lang>
- 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
<lang 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)</lang>
Common Lisp
With all three methods defined. <lang lisp>(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))))</lang>
D
<lang 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));
}</lang>
- 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
Erlang
<lang 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",| N <- TestList), io:format("1st recusive method:\n~p\n",| N <- TestList), io:format("2nd recusive method:\n~p\n",| N <- TestList).</lang>
- 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]
Euphoria
<lang 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</lang>
- Output:
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
Factor
This is the last solution, memoized by using arrays. Run in scratchpad. <lang factor>: 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
}</lang>
Fantom
<lang 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)) } }
}</lang> 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
Forth
<lang forth>: catalan ( n -- ) 1 swap 1+ 1 do dup cr . i 2* 1- 2* i 1+ */ loop drop ;</lang>
Fortran
<lang fortran>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</lang>
- Output:
=============== n c(n) --------------- 0 1 1 1 2 2 3 5 4 14 5 42 6 132 7 429 8 1430 9 4862 10 16796 11 58786 12 208012 13 742900 14 2674440 ===============
Frink
Frink includes efficient algorithms for calculating arbitrarily-large binomial coefficients and automatically caches factorials. <lang frink>catalan[n] := binomial[2n,n]/(n+1) for n = 0 to 15
println[catalan[n]]</lang>
GAP
<lang 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 ]</lang>
Go
Direct: <lang go>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))) }
}</lang>
- Output:
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
Haskell
<lang 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]</lang>
- 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
<lang Icon>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</lang>
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
J
<lang j> ((! +:) % >:) i.15x 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440</lang>
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"). <lang java5>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)); } } }</lang>
- 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
JavaScript
<lang javascript><html><head><title>Catalan</title></head>
<body>
<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></lang>
- 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
Julia
From the Catalan package, returns the n-th Catalan number <lang julia>function catalan(bn::Integer)
if bn < 0 throw(DomainError()) else n = BigInt(bn) end return binomial(2n, n)/(n + 1)
end</lang>
- 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
K
<lang 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</lang>
Liberty BASIC
<lang lb>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</lang>
- 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
Lua
<lang 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</lang>
- Output:
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
Mathematica
<lang Mathematica>CatalanN[n_Integer /; n >= 0] := (2 n)!/((n + 1)! n!)</lang>
- Sample Output:
<lang Mathematica>TableForm[CatalanN/@Range[0,15]] //TableForm= 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</lang>
MATLAB / Octave
<lang MATLAB>function n = catalanNumbers(n)
for i = (1:length(n)) n(i) = (1/(n(i)+1))*nchoosek(2*n(i),n(i)); end
end</lang> The following version is fully vectorized and does not require a loop <lang MATLAB>function n = catalanNumbers(n)
n = prod(n+1:2*n)/prod(1:n+1);
end</lang>
- Sample Output:
<lang MATLAB>>> 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</lang>
Maxima
<lang 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] */</lang>
ooRexx
Three versions of this. <lang ooRexx>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</lang>
- 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
PARI/GP
Memoization is not worthwhile; PARI has fast built-in facilities for calculating binomial coefficients and factorials. <lang parigp>Catalan(n)=binomial(2*n,n+1)/n</lang> A second version: <lang parigp>Catalan(n)=(2*n)!/(n+1)!/n!</lang> Naive version with binary splitting: <lang parigp>Catalan(n)=prod(k=n+2,2*n,k)/prod(k=2,n,k)</lang> Naive version: <lang parigp>Catalan(n)={
my(t=1); for(k=n+2,2*n,t*=k); for(k=2,n,t/=k); t
};</lang> 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: <lang parigp>vector(15,n,Catalan(n))</lang>
Pascal
<lang 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.</lang>
- 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
<lang 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;</lang> For computing up to 20 ish, memoization is not needed. For much bigger numbers, this is faster: <lang perl>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;</lang>
Perl 6
<lang perl6>my @catalan := 1, { (state $n)++; 2*(2*$n-1)/($n+1) * $_ } ... *;
.say for @catalan[^15];</lang>
- Output:
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
PHP
<lang 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";
} ?></lang>
- 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
PicoLisp
<lang 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) ) )</lang>
- 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
<lang 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;</lang>
- 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
<lang 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</lang>
Prolog
<lang 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]).</lang>
- 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... <lang PureBasic>; 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</lang>
- 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. <lang python>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)</lang>
- 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
R
<lang 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</lang>
Racket
<lang 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))</lang>
- Output:
'(1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440)
REXX
All methods use memoization. <lang rexx>/*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 !</lang> 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
Ruby
Using a memoization module found at the Ruby Application Archive. <lang ruby># 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)]}</lang> 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]
Run BASIC
<lang Runbasic>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</lang>
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
Scala
Simple and straightforward. Noticeably out of steam without memoizing at about 5000. <lang scala>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)) } }
}</lang>
- 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
Scheme
Tail recursive implementation. <lang scheme>(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)</lang>
- Output:
0: 1 1: 1 2: 2 3: 5 4: 14 5: 42 6: 132 7: 429 8: 1430 9: 4862 10: 16796 11: 58786 12: 208012 13: 742900 14: 2674440
Seed7
<lang 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;</lang>
- Output:
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
Standard ML
<lang sml>(*
* 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 *)</lang>
Tcl
<lang 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)
}}
}</lang> Demonstration: <lang tcl>for {set i 0} {$i < 15} {incr i} {
puts "C_$i = [expr {catalan($i)}]"
}</lang>
- 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. <lang TI-83 BASIC>:For(I,1,15
- Disp (2I)!/((I+1)!I!
- End</lang>
- Output:
1 2 4 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 Done
Ursala
<lang ursala>#import std
- import nat
catalan = quotient^\successor choose^/double ~&
- cast %nL
t = catalan* iota 16</lang>
- Output:
< 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845>
VBA
<lang vb>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</lang>
- 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")
XPL0
<lang 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); ];
]</lang>
- Output:
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
- WikipediaSourced
- Programming Tasks
- Arithmetic operations
- Ada
- AutoHotkey
- AWK
- BASIC
- BBC BASIC
- Bracmat
- Brat
- C
- C sharp
- C++
- Clojure
- Common Lisp
- D
- Erlang
- Euphoria
- Factor
- Fantom
- Forth
- Fortran
- Frink
- GAP
- Go
- Haskell
- Icon
- Unicon
- J
- Java
- Memoization
- JavaScript
- Julia
- K
- Liberty BASIC
- Lua
- Mathematica
- MATLAB
- Octave
- Maxima
- OoRexx
- PARI/GP
- Pascal
- Perl
- Perl 6
- PHP
- PicoLisp
- PL/I
- PlainTeX
- Prolog
- PureBasic
- Python
- R
- Racket
- REXX
- Ruby
- Run BASIC
- Scala
- Scheme
- Seed7
- Standard ML
- Tcl
- TI-83 BASIC
- Ursala
- VBA
- XPL0