Rosetta Code

Catalan numbers: Difference between revisions

Page Discussion

Catalan numbers (view source)

Revision as of 18:56, 1 May 2024

79,836 bytes added ,  1 month ago
→‎{{header|langur}}
(149 intermediate revisions by 58 users not shown)
Line 1:
{{Wikipedia}}
{{wikipedia}}{{task|Arithmetic operations}}
{{task|Arithmetic operations}}
 
<br>
Line 20 ⟶ 21:
*[[Evaluate binomial coefficients]]
<br><br>
=={{header|11l}}==
 
<syntaxhighlight lang="11l">V c = 1
L(n) 1..15
print(c)
c = 2 * (2 * n - 1) * c I/ (n + 1)</syntaxhighlight>
{{out}}
<pre>
1
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440
</pre>
=={{header|360 Assembly}}==
Very compact version.
<langsyntaxhighlight lang="360asm">CATALAN CSECT 08/09/2015
USING CATALAN,R15
LA R7,1 c=1
Line 44 ⟶ 67:
PG DS CL24
YREGS
END CATALAN</langsyntaxhighlight>
{{out}}
<pre>
<pre style="height:16ex">
1 1
2 2
Line 63 ⟶ 86:
15 9694845
</pre>
=={{header|ABAP}}==
This works for ABAP Version 7.40 and above
 
<syntaxhighlight lang="abap">
report z_catalan_numbers.
 
class catalan_numbers definition.
public section.
class-methods:
get_nth_number
importing
i_n type int4
returning
value(r_catalan_number) type int4.
endclass.
 
class catalan_numbers implementation.
method get_nth_number.
r_catalan_number = cond int4(
when i_n eq 0
then 1
else reduce int4(
init
result = 1
index = 1
for position = 1 while position <= i_n
next
result = result * 2 * ( 2 * index - 1 ) div ( index + 1 )
index = index + 1 ) ).
endmethod.
endclass.
 
start-of-selection.
do 15 times.
write / |C({ sy-index - 1 }) = { catalan_numbers=>get_nth_number( sy-index - 1 ) }|.
enddo.
</syntaxhighlight>
 
{{out}}
 
<pre>
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
</pre>
=={{header|Action!}}==
{{libheader|Action! Tool Kit}}
<syntaxhighlight lang="action!">INCLUDE "D2:REAL.ACT" ;from the Action! Tool Ki
 
PROC Main()
REAL c,rnom,rden
BYTE n,nom,den
 
Put(125) PutE() ;clear the screen
IntToReal(1,c)
FOR n=1 TO 15
DO
nom=(n LSH 1-1) LSH 1
den=n+1
IntToReal(nom,rnom)
IntToReal(den,rden)
RealMult(c,rnom,c)
RealDiv(c,rden,c)
PrintF("C(%B)=",n) PrintRE(c)
OD
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Catalan_numbers.png Screenshot from Atari 8-bit computer]
<pre>
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
</pre>
=={{header|Ada}}==
<langsyntaxhighlight Adalang="ada">with Ada.Text_IO; use Ada.Text_IO;
 
procedure Test_Catalan is
Line 80 ⟶ 200:
Put_Line (Integer'Image (N) & " =" & Integer'Image (Catalan (N)));
end loop;
end Test_Catalan;</langsyntaxhighlight>
{{out|Sample output}}
<pre>
Line 100 ⟶ 220:
15 = 9694845
</pre>
 
=={{header|ALGOL 68}}==
<langsyntaxhighlight lang="algol68"># calculate the first few catalan numbers, using LONG INT values #
# (64-bit quantities in Algol 68G which can handle up to C23) #
 
Line 133 ⟶ 252:
FOR i FROM 0 TO 15 DO
print( ( whole( i, -2 ), ": ", whole( catalan( i ), 0 ), newline ) )
OD</langsyntaxhighlight>
{{out}}
<pre>
Line 153 ⟶ 272:
15: 9694845
</pre>
 
=={{header|ALGOL W}}==
<langsyntaxhighlight lang="algolw">begin
% print the catalan numbers up to C15 %
integer Cprev;
Line 164 ⟶ 282:
write( s_w := 0, i_w := 3, n, ": ", i_w := 9, Cprev );
end for_n
end.</langsyntaxhighlight>
{{out}}
<pre>
Line 184 ⟶ 302:
15: 9694845
</pre>
 
=={{header|APL}}==
<langsyntaxhighlight lang="apl"> {(!2×⍵)÷(!⍵+1)×!⍵}(⍳15)-1</langsyntaxhighlight>
{{out}}
<pre>1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">catalan: function [n][
if? n=0 -> 1
else -> div (catalan n-1) * (4*n)-2 n+1
]
loop 0..15 [i][
print [
pad.right to :string i 5
pad.left to :string catalan i 20
]
]</syntaxhighlight>
{{out}}
 
<pre>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</pre>
=={{header|AutoHotkey}}==
As AutoHotkey has no BigInt, the formula had to be tweaked to prevent overflow. It still fails after n=22
<langsyntaxhighlight AHKlang="ahk">Loop 15
out .= "`n" Catalan(A_Index)
Msgbox % clipboard := SubStr(out, 2)
Line 211 ⟶ 358:
 
Return i
}</langsyntaxhighlight>
{{out}}
<pre>1
Line 228 ⟶ 375:
2674440
9694845</pre>
 
=={{header|AWK}}==
<langsyntaxhighlight AWKlang="awk"># syntax: GAWK -f CATALAN_NUMBERS.AWK
BEGIN {
for (i=0; i<=15; i++) {
Line 245 ⟶ 391:
}
return(ans)
}</langsyntaxhighlight>
{{out}}
<pre>
Line 272 ⟶ 418:
Use of <code>REDIM PRESERVE</code> means this will not work in QBasic (although that could be worked around if desired).
 
<langsyntaxhighlight lang="qbasic">DECLARE FUNCTION catalan (n as INTEGER) AS SINGLE
 
REDIM SHARED results(0) AS SINGLE
Line 289 ⟶ 435:
END IF
catalan = results(n)
END FUNCTION</langsyntaxhighlight>
{{out}}
1 1
Line 307 ⟶ 453:
15 9694845
 
==={{header|BBCApplesoft BASIC}}===
{{works with|Chipmunk Basic}}
<lang bbcbasic> FOR i% = 1 TO 15
{{works with|QBasic}}
PRINT FNcatalan(i%)
<syntaxhighlight lang="qbasic">10 HOME : REM 10 CLS for Chipmunk Basic/QBasic
NEXT
20 DIM c(15)
END
30 c(0) = 1
40 PRINT 0, c(0)
DEF FNcatalan(n%)
50 IFFOR n% = 0 THEN =TO 114
60 c(n + 1) = 0
= 2 * (2 * n% - 1) * FNcatalan(n% - 1) / (n% + 1)</lang>
70 FOR i = 0 TO n
80 c(n + 1) = c(n + 1) + c(i) * c(n - i)
90 NEXT i
100 PRINT n + 1, c(n + 1)
110 NEXT n
120 END</syntaxhighlight>
 
==={{header|BASIC256}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="freebasic">function factorial(n)
if n = 0 then return 1
return n * factorial(n - 1)
end function
 
function catalan1(n)
prod = 1
for i = n + 2 to 2 * n
prod *= i
next i
return int(prod / factorial(n))
end function
 
function catalan2(n)
if n = 0 then return 1
sum = 0
for i = 0 to n - 1
sum += catalan2(i) * catalan2(n - 1 - i)
next i
return sum
end function
 
function catalan3(n)
if n = 0 then return 1
return catalan3(n - 1) * 2 * (2 * n - 1) \ (n + 1)
end function
 
print "n", "First", "Second", "Third"
print "-", "-----", "------", "-----"
print
for i = 0 to 15
print i, catalan1(i), catalan2(i), catalan3(i)
next i</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
 
==={{header|BBC BASIC}}===
<syntaxhighlight lang="bbcbasic"> 10 FOR i% = 1 TO 15
20 PRINT FNcatalan(i%)
30 NEXT
40 END
50 DEF FNcatalan(n%)
60 IF n% = 0 THEN = 1
70 = 2 * (2 * n% - 1) * FNcatalan(n% - 1) / (n% + 1)</syntaxhighlight>
{{out}}
<pre> 1
1
2
5
Line 330 ⟶ 530:
208012
742900
2674440</pre>
9694845</pre>
 
==={{header|BefungeChipmunk Basic}}===
{{works with|Chipmunk Basic|3.6.4}}
{{trans|Run BASIC}}
<syntaxhighlight lang="qbasic">10 FOR i = 1 TO 15
20 PRINT i;" ";catalan(i)
30 NEXT
40 END
50 SUB catalan(n)
60 catalan = 1
70 IF n <> 0 THEN catalan = ((2*((2*n)-1))/(n+1))*catalan(n-1)
80 END SUB</syntaxhighlight>
 
==={{header|Craft Basic}}===
<syntaxhighlight lang="basic">dim c[16]
 
let c[0] = 1
 
for n = 0 to 15
 
let p = n + 1
let c[p] = 0
 
for i = 0 to n
 
let q = n - i
let c[p] = c[p] + c[i] * c[q]
 
next i
 
print n, " ", c[n]
 
next n</syntaxhighlight>
{{out| Output}}<pre>
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
</pre>
 
==={{header|FreeBASIC}}===
<syntaxhighlight lang="freebasic">' FB 1.05.0 Win64
 
Function factorial(n As UInteger) As UInteger
If n = 0 Then Return 1
Return n * factorial(n - 1)
End Function
 
Function catalan1(n As UInteger) As UInteger
Dim prod As UInteger = 1
For i As UInteger = n + 2 To 2 * n
prod *= i
Next
Return prod / factorial(n)
End Function
 
Function catalan2(n As UInteger) As UInteger
If n = 0 Then Return 1
Dim sum As UInteger = 0
For i As UInteger = 0 To n - 1
sum += catalan2(i) * catalan2(n - 1 - i)
Next
Return sum
End Function
 
Function catalan3(n As UInteger) As UInteger
If n = 0 Then Return 1
Return catalan3(n - 1) * 2 * (2 * n - 1) \ (n + 1)
End Function
 
Print "n", "First", "Second", "Third"
Print "-", "-----", "------", "-----"
Print
For i As UInteger = 0 To 15
Print i, catalan1(i), catalan2(i), catalan3(i)
Next
Print
Print "Press any key to quit"
Sleep</syntaxhighlight>
 
{{out}}
<pre>
n First Second Third
- ----- ------ -----
 
0 1 1 1
1 1 1 1
2 2 2 2
3 5 5 5
4 14 14 14
5 42 42 42
6 132 132 132
7 429 429 429
8 1430 1430 1430
9 4862 4862 4862
10 16796 16796 16796
11 58786 58786 58786
12 208012 208012 208012
13 742900 742900 742900
14 2674440 2674440 2674440
15 9694845 9694845 9694845
</pre>
 
==={{header|FutureBasic}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="futurebasic">
include "NSLog.incl"
 
local fn Factorial( n as NSInteger ) as UInt64
UInt64 sum = 0
if n = 0 then sum = 1 : exit fn
sum = n * fn Factorial( n - 1 )
end fn = sum
 
local fn Catalan1( n as NSInteger ) as UInt64
UInt64 product = 1, result
NSUInteger i
for i = n + 2 to 2 * n
product = product * i
next
result = product / fn Factorial( n )
end fn = result
 
local fn Catalan2( n as NSInteger ) as UInt64
UInt64 sum = 0
NSUInteger i
if n = 0 then sum = 1 : exit fn
for i = 0 to n - 1
sum += fn Catalan2(i) * fn Catalan2( n - 1 - i )
next
end fn = sum
 
local fn Catalan3( n as NSInteger ) as UInt64
UInt64 result
if n = 0 then result = 1 : exit fn
result = fn Catalan3( n - 1 ) * 2 * ( 2 * n - 1 ) / ( n + 1 )
end fn = result
 
NSUInteger i
 
for i = 0 to 19
if( i < 16 )
NSLog( @"%3d.\t\t%7llu\t\t%12llu\t\t%12llu", i, fn Catalan1( i ), fn Catalan2( i ), fn Catalan3( i ) )
else
NSLog( @"%3d.\t\t%@\t\t%12llu\t\t%12llu", i, @"[-err-]", fn Catalan2( i ), fn Catalan3( i ) )
end if
next
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
0. 1 1 1
1. 1 1 1
2. 2 2 2
3. 5 5 5
4. 14 14 14
5. 42 42 42
6. 132 132 132
7. 429 429 429
8. 1430 1430 1430
9. 4862 4862 4862
10. 16796 16796 16796
11. 58786 58786 58786
12. 208012 208012 208012
13. 742900 742900 742900
14. 2674440 2674440 2674440
15. 9694845 9694845 9694845
16. [-err-] 35357670 35357670
17. [-err-] 129644790 129644790
18. [-err-] 477638700 477638700
19. [-err-] 1767263190 1767263190
</pre>
 
==={{header|GW-BASIC}}===
{{works with|BASICA}}
<syntaxhighlight lang="gwbasic">
100 REM Catalan numbers
110 DIM C(15)
120 C(0) = 1
130 PRINT 0, C(0)
140 FOR N = 0 TO 14
150 C(N + 1) = 0
160 FOR I = 0 TO N
170 C(N + 1) = C(N + 1) + C(I) * C(N - I)
180 NEXT I
190 PRINT N + 1, C(N + 1)
200 NEXT N
210 END
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
 
==={{header|Liberty BASIC}}===
{{works with|Just BASIC}}
<syntaxhighlight 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</syntaxhighlight>
{{out}}
<pre>
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</pre>
 
==={{header|Minimal BASIC}}===
{{trans|GW-BASIC}}
<syntaxhighlight lang="gwbasic">
10 REM Catalan numbers
20 DIM C(15)
30 LET C(0) = 1
40 PRINT 0, C(0)
50 FOR N = 0 TO 14
60 LET C(N+1) = 0
70 FOR I = 0 TO N
80 LET C(N+1) = C(N+1)+C(I)*C(N-I)
90 NEXT I
100 PRINT N+1, C(N+1)
110 NEXT N
120 END
</syntaxhighlight>
 
==={{header|PureBasic}}===
Using the third formula...
<syntaxhighlight 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</syntaxhighlight>
{{out|Sample Output}}
<pre>
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
</pre>
 
==={{header|Run BASIC}}===
<syntaxhighlight lang="runbasic">FOR i = 1 TO 15
PRINT i;" ";catalan(i)
NEXT
FUNCTION catalan(n)
catalan = 1
if n <> 0 then catalan = ((2 * ((2 * n) - 1)) / (n + 1)) * catalan(n - 1)
END FUNCTION</syntaxhighlight>
<pre>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</pre>
 
==={{header|Sinclair ZX81 BASIC}}===
Works with 1k of RAM.
 
The specification asks for the first 15 Catalan numbers. A lot of the other implementations produce either C(0) to C(15), which is 16 numbers, or else C(1) to C(15)—which is 15 numbers, but I'm not convinced they're the first 15. This program produces C(0) to C(14).
 
<syntaxhighlight lang="basic"> 10 FOR N=0 TO 14
20 LET X=N
30 GOSUB 130
40 LET A=FX
50 LET X=N+1
60 GOSUB 130
70 LET B=FX
80 LET X=2*N
90 GOSUB 130
100 PRINT N,FX/(B*A)
110 NEXT N
120 STOP
130 LET FX=1
140 FOR I=1 TO X
150 LET FX=FX*I
160 NEXT I
170 RETURN</syntaxhighlight>
{{out}}
<pre>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</pre>
 
==={{header|smart BASIC}}===
<syntaxhighlight lang="qbasic">PRINT "Recursive:"!PRINT
FOR n = 0 TO 15
PRINT n,"#######":catrec(n)
NEXT n
PRINT!PRINT
 
PRINT "Non-recursive:"!PRINT
FOR n = 0 TO 15
PRINT n,"#######":catnonrec(n)
NEXT n
 
END
DEF catrec(x)
IF x = 0 THEN
temp = 1
ELSE
n = x
temp = ((2*((2*n)-1))/(n+1))*catrec(n-1)
END IF
catrec = temp
END DEF
 
DEF catnonrec(x)
temp = 1
FOR n = 1 TO x
temp = (2*((2*n)-1))/(n+1)*temp
NEXT n
catnonrec = temp
END DEF</syntaxhighlight>
 
==={{header|TI-83 BASIC}}===
This problem is perfectly suited for a TI calculator.
<syntaxhighlight lang="ti-83 basic">:For(I,1,15
:Disp (2I)!/((I+1)!I!
:End</syntaxhighlight>
{{out}}
<pre> 1
2
4
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440
9694845
Done</pre>
 
==={{Header|Tiny BASIC}}===
Integers are limited to 32767 so only the first ten Catalan numbers can be represented. And even then one has to do some finagling to avoid internal overflows.
{{works with|TinyBasic}}
<syntaxhighlight lang="basic">
10 REM Catalan numbers
20 LET N = 0
30 LET C = 1
40 PRINT N," ",C
50 IF N > 9 THEN END
60 LET N = N + 1
70 GOSUB 200
80 LET C = (2 * N - 1) * C
90 LET C = 2 * C / (N + 1)
100 LET C = C + 2 * I * (2 * N - 1)
110 GOTO 40
200 LET I = 0
210 IF C <= 0 THEN RETURN
220 LET C = C - (N + 1)
230 LET I = I + 1
240 GOTO 210
250 REM To avoid internal overflow, I subtract something clever from
260 REM C and then add it back at the end.</syntaxhighlight>
{{out}}
<pre>0 1
1 1
2 2
3 5
4 14
5 42
6 132
7 429
8 1430
9 4862
10 16796</pre>
 
==={{header|VBA}}===
<syntaxhighlight 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</syntaxhighlight>
{{out|Result}}
<pre>
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
</pre>
(Expect same result with "Catalan2 15")
 
==={{header|VBScript}}===
<syntaxhighlight lang="vb">
Function catalan(n)
catalan = factorial(2*n)/(factorial(n+1)*factorial(n))
End Function
 
Function factorial(n)
If n = 0 Then
Factorial = 1
Else
For i = n To 1 Step -1
If i = n Then
factorial = n
Else
factorial = factorial * i
End If
Next
End If
End Function
 
'Find the first 15 Catalan numbers.
For j = 1 To 15
WScript.StdOut.Write j & " = " & catalan(j)
WScript.StdOut.WriteLine
Next
</syntaxhighlight>
 
{{Out}}
<pre>
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
</pre>
 
==={{header|Visual Basic .NET}}===
{{trans|C#}}
<syntaxhighlight lang="vbnet">Module Module1
 
Function Factorial(n As Double) As Double
If n < 1 Then
Return 1
End If
 
Dim result = 1.0
For i = 1 To n
result = result * i
Next
 
Return result
End Function
 
Function FirstOption(n As Double) As Double
Return Factorial(2 * n) / (Factorial(n + 1) * Factorial(n))
End Function
 
Function SecondOption(n As Double) As Double
If n = 0 Then
Return 1
End If
 
Dim sum = 0
For i = 0 To n - 1
sum = sum + SecondOption(i) * SecondOption((n - 1) - i)
Next
Return sum
End Function
 
Function ThirdOption(n As Double) As Double
If n = 0 Then
Return 1
End If
 
Return ((2 * (2 * n - 1)) / (n + 1)) * ThirdOption(n - 1)
End Function
 
Sub Main()
Const MaxCatalanNumber = 15
 
Dim initial As DateTime
Dim final As DateTime
Dim ts As TimeSpan
 
initial = DateTime.Now
For i = 0 To MaxCatalanNumber
Console.WriteLine("CatalanNumber({0}:{1})", i, FirstOption(i))
Next
final = DateTime.Now
ts = final - initial
Console.WriteLine("It took {0}.{1} to execute", ts.Seconds, ts.Milliseconds)
Console.WriteLine()
 
initial = DateTime.Now
For i = 0 To MaxCatalanNumber
Console.WriteLine("CatalanNumber({0}:{1})", i, SecondOption(i))
Next
final = DateTime.Now
ts = final - initial
Console.WriteLine("It took {0}.{1} to execute", ts.Seconds, ts.Milliseconds)
Console.WriteLine()
 
initial = DateTime.Now
For i = 0 To MaxCatalanNumber
Console.WriteLine("CatalanNumber({0}:{1})", i, ThirdOption(i))
Next
final = DateTime.Now
ts = final - initial
Console.WriteLine("It took {0}.{1} to execute", ts.Seconds, ts.Milliseconds)
End Sub
 
End Module</syntaxhighlight>
{{out}}
<pre>CatalanNumber(0:1)
CatalanNumber(1:1)
CatalanNumber(2:2)
CatalanNumber(3:5)
CatalanNumber(4:14)
CatalanNumber(5:42)
CatalanNumber(6:132)
CatalanNumber(7:429)
CatalanNumber(8:1430)
CatalanNumber(9:4862)
CatalanNumber(10:16796)
CatalanNumber(11:58786)
CatalanNumber(12:208012)
CatalanNumber(13:742900)
CatalanNumber(14:2674440)
CatalanNumber(15:9694845)
It took 0.19 to execute
 
CatalanNumber(0:1)
CatalanNumber(1:1)
CatalanNumber(2:2)
CatalanNumber(3:5)
CatalanNumber(4:14)
CatalanNumber(5:42)
CatalanNumber(6:132)
CatalanNumber(7:429)
CatalanNumber(8:1430)
CatalanNumber(9:4862)
CatalanNumber(10:16796)
CatalanNumber(11:58786)
CatalanNumber(12:208012)
CatalanNumber(13:742900)
CatalanNumber(14:2674440)
CatalanNumber(15:9694845)
It took 0.831 to execute
 
CatalanNumber(0:1)
CatalanNumber(1:1)
CatalanNumber(2:2)
CatalanNumber(3:5)
CatalanNumber(4:14)
CatalanNumber(5:42)
CatalanNumber(6:132)
CatalanNumber(7:429)
CatalanNumber(8:1430)
CatalanNumber(9:4862)
CatalanNumber(10:16796)
CatalanNumber(11:58786)
CatalanNumber(12:208012)
CatalanNumber(13:742900)
CatalanNumber(14:2674440)
CatalanNumber(15:9694845)
It took 0.8 to execute</pre>
 
==={{header|Yabasic}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="yabasic">print " n First Second Third"
print " - ----- ------ -----"
print
for i = 0 to 15
print i using "###", catalan1(i) using "########", catalan2(i) using "########", catalan3(i) using "########"
next i
end
 
sub factorial(n)
if n = 0 return 1
return n * factorial(n - 1)
end sub
 
sub catalan1(n)
local proc, i
 
prod = 1
for i = n + 2 to 2 * n
prod = prod * i
next i
return int(prod / factorial(n))
end sub
 
sub catalan2(n)
local sum, i
 
if n = 0 return 1
sum = 0
for i = 0 to n - 1
sum = sum + catalan2(i) * catalan2(n - 1 - i)
next i
return sum
end sub
 
sub catalan3(n)
if n = 0 return 1
return ((2 * ((2 * n) - 1)) / (n + 1)) * catalan3(n - 1)
end sub</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
 
=={{header|Befunge}}==
{{trans|Ada}}
<langsyntaxhighlight lang="befunge">0>:.:000p1>\:00g-#v_v
v 2-1*2p00 :+1g00\< $
> **00g1+/^v,*84,"="<
_^#<`*53:+1>#,.#+5< @</langsyntaxhighlight>
 
{{out}}
Line 358 ⟶ 1,408:
14 = 2674440
15 = 9694845</pre>
=={{header|BQN}}==
<syntaxhighlight lang="bqn">Cat←{ 0⊸<◶⟨1, (𝕊-⟜1)×(¯2+4×⊢)÷1+⊢⟩ 𝕩 }
Fact ← ×´1+↕
Cat1 ← { # direct formula
⌊0.5 + (Fact 2×𝕩) ÷ (Fact 𝕩+1) × Fact 𝕩
}
Cat2 ← { # header based recursion
0: 1;
(𝕊 𝕩-1)×2×(1-˜2×𝕩)÷𝕩+1
}
 
Cat¨ ↕15
Cat1¨ ↕15
Cat2¨ ↕15</syntaxhighlight>
{{out}}
<pre>⟨ 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 ⟩</pre>
=={{header|Bracmat}}==
<langsyntaxhighlight lang="bracmat">( out$straight
& ( C
=
Line 416 ⟶ 1,481:
& out$(1+(1+-1*tay$((1+-4*X)^1/2,X,16))*(2*X)^-1+-1)
& out$
);</langsyntaxhighlight>
{{out}}
<langsyntaxhighlight lang="bracmat">straight
C0 = 1
C1 = 1
Line 486 ⟶ 1,551:
+ 2674440*X^14
+ 9694845*X^15
</syntaxhighlight>
</lang>
 
=={{header|Brat}}==
<langsyntaxhighlight lang="brat">catalan = { n |
true? n == 0
{ 1 }
Line 497 ⟶ 1,561:
0.to 15 { n |
p "#{n} - #{catalan n}"
}</langsyntaxhighlight>
{{out}}
<pre>0 - 1
Line 516 ⟶ 1,580:
15 - 9694845
</pre>
 
=={{header|C}}==
All three methods mentioned in the task:
<langsyntaxhighlight lang="c">#include <stdio.h>
 
typedef unsigned long long ull;
Line 564 ⟶ 1,627:
 
return 0;
}</langsyntaxhighlight>
{{out}}
direct summing frac
Line 583 ⟶ 1,646:
14 2674440 2674440 2674440
15 9694845 9694845 9694845
=={{header|C sharp|C#}}==
 
<syntaxhighlight lang="csharp">namespace CatalanNumbers
== {{header|C sharp}} ==
<lang csharp>namespace CatalanNumbers
{
/// <summary>
Line 698 ⟶ 1,760:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>
Line 755 ⟶ 1,817:
It took 0.3 to execute
</pre>
 
=={{header|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)
<langsyntaxhighlight lang="cpp">#if !defined __ALGORITHMS_H__
#define __ALGORITHMS_H__
 
Line 818 ⟶ 1,879:
} //namespace rosetta
 
#endif //!defined __ALGORITHMS_H__</langsyntaxhighlight>
Here is the implementation of the algorithms. The c'tor of each class tells us the algorithm which will be used. (algorithms.cpp)
<langsyntaxhighlight lang="cpp">#include <iostream>
using std::cout;
using std::endl;
Line 920 ⟶ 1,981:
product *= (double(n - (k - i)) / i);
return (unsigned long long)(floor(product + 0.5));
}</langsyntaxhighlight>
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)
<langsyntaxhighlight lang="cpp">#if !defined __TESTER_H__
#define __TESTER_H__
 
Line 947 ⟶ 2,008:
} //namespace rosetta
 
#endif //!defined __TESTER_H__</langsyntaxhighlight>
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)
<langsyntaxhighlight lang="cpp">#include "algorithms.h"
#include "tester.h"
using namespace rosetta::catalanNumbers;
Line 960 ⟶ 2,021:
Test<15, CatalanNumbersRecursiveSum>::Do();
return 0;
}</langsyntaxhighlight>
{{out}}
(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)
Line 1,028 ⟶ 2,089:
C(15) = 9694845
</pre>
 
=={{header|Clojure}}==
<langsyntaxhighlight Clojurelang="clojure">(def ! (memoize #(apply * (range 1 (inc %)))))
 
(defn catalan-numbers-direct []
Line 1,046 ⟶ 2,106:
 
user> (take 15 (catalan-numbers-recursive))
(1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440)</langsyntaxhighlight>
=={{header|CLU}}==
<syntaxhighlight lang="clu">catalan = iter (amount: int) yields (int)
c: int := 1
for n: int in int$from_to(1, amount) do
yield(c)
c := (4*n-2)*c/(n+1)
end
end catalan
 
start_up = proc ()
po: stream := stream$primary_output()
for n: int in catalan(15) do
stream$putl(po, int$unparse(n))
end
end start_up</syntaxhighlight>
{{out}}
<pre>1
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440</pre>
 
=={{header|Common Lisp}}==
With all three methods defined.
<langsyntaxhighlight lang="lisp">(defun catalan1 (n)
;; factorial. CLISP actually has "!" defined for this
(labels ((! (x) (if (zerop x) 1 (* x (! (1- x))))))
Line 1,077 ⟶ 2,168:
for i from 1 to 3 do
(format t "~%Method ~d:~%" i)
(dotimes (i 16) (format t "C(~2d) = ~d~%" i (funcall f i))))</langsyntaxhighlight>
 
=={{header|Cowgol}}==
<syntaxhighlight lang="cowgol">include "cowgol.coh";
 
sub catalan(n: uint32): (c: uint32) is
c := 1;
var i: uint32 := 1;
while i <= n loop
c := (4*i-2)*c/(i+1);
i := i+1;
end loop;
end sub;
 
var i: uint8 := 0;
while i < 15 loop
print("catalan(");
print_i8(i);
print(") = ");
print_i32(catalan(i as uint32));
print_nl();
i := i+1;
end loop;</syntaxhighlight>
{{out}}
<pre>catalan(0) = 1
catalan(1) = 1
catalan(2) = 2
catalan(3) = 5
catalan(4) = 14
catalan(5) = 42
catalan(6) = 132
catalan(7) = 429
catalan(8) = 1430
catalan(9) = 4862
catalan(10) = 16796
catalan(11) = 58786
catalan(12) = 208012
catalan(13) = 742900
catalan(14) = 2674440</pre>
 
=={{header|Crystal}}==
{{trans|Ruby}}
<syntaxhighlight lang="ruby">require "big"
require "benchmark"
 
def factorial(n : BigInt) : BigInt
(1..n).product(1.to_big_i)
end
 
def factorial(n : Int32 | Int64)
factorial n.to_big_i
end
 
# direct
 
def catalan_direct(n)
factorial(2*n) / (factorial(n + 1) * factorial(n))
end
 
# recursive
 
def catalan_rec1(n)
return 1 if n == 0
(0...n).reduce(0) do |sum, i|
sum + catalan_rec1(i) * catalan_rec1(n - 1 - i)
end
end
 
def catalan_rec2(n)
return 1 if n == 0
2*(2*n - 1) * catalan_rec2(n - 1) / (n + 1)
end
 
# performance and results
 
Benchmark.bm do |b|
b.report("catalan_direct") { 16.times { |n| catalan_direct(n) } }
b.report("catalan_rec1") { 16.times { |n| catalan_rec1(n) } }
b.report("catalan_rec2") { 16.times { |n| catalan_rec2(n) } }
end
 
puts "\n direct rec1 rec2"
16.times { |n| puts "%2d :%9d%9d%9d" % [n, catalan_direct(n), catalan_rec1(n), catalan_rec2(n)] }
</syntaxhighlight>
 
{{out}}
<pre>
# with --release flag
# Using: i7-6700HQ, 3.5GHz
user system total real
catalan_direct 0.000026 0.000052 0.000078 ( 0.000074)
catalan_rec1 0.139766 0.001143 0.140909 ( 0.141418)
catalan_rec2 0.000003 0.000000 0.000003 ( 0.000003)
 
direct rec1 rec2
0 : 1 1 1
1 : 1 1 1
2 : 2 2 2
3 : 5 5 5
4 : 14 14 14
5 : 42 42 42
6 : 132 132 132
7 : 429 429 429
8 : 1430 1430 1430
9 : 4862 4862 4862
10 : 16796 16796 16796
11 : 58786 58786 58786
12 : 208012 208012 208012
13 : 742900 742900 742900
14 : 2674440 2674440 2674440
15 : 9694845 9694845 9694845
</pre>
 
=={{header|D}}==
<langsyntaxhighlight lang="d">import std.stdio, std.algorithm, std.bigint, std.functional, std.range;
 
auto product(R)(R r) { return reduce!q{a * b}(1.BigInt, r); }
Line 1,099 ⟶ 2,301:
foreach (cats; TypeTuple!(cats1, cats2, cats3))
cats.take(15).writeln;
}</langsyntaxhighlight>
{{out}}
<pre>[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]</pre>
=={{header|Delphi}}==
See [https://www.rosettacode.org/wiki/Catalan_numbers#Pascal Pascal].
=={{header|EasyLang}}==
<syntaxhighlight lang="text">
func catalan n .
if n = 0
return 1
.
return 2 * (2 * n - 1) * catalan (n - 1) div (1 + n)
.
for i = 0 to 14
print catalan i
.
</syntaxhighlight>
 
=={{header|EchoLisp}}==
{{incorrect|Echolisp|series starts 1, 1, 2, ...}}
<lang scheme>
<syntaxhighlight lang="scheme">
(lib 'sequences)
(lib 'bigint)
Line 1,144 ⟶ 2,361:
(for ((c C3) (i 15)) (write c))
→ 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</syntaxhighlight>
</lang>
=={{header|EDSAC order code}}==
The Catalan numbers are here computed by the second method, as a sum of products.
The program illustrates a difficulty with multiplying integers on the EDSAC,
which was designed to work with fixed-point numbers in the range [-1, 1).
When we store a 35-bit integer A, we are really storing A*(2^-34).
As long as integer arithmetic is confined to addition and subtraction, this scaling can be ignored.
But if we multiply two 35-bit integers A and B, the result is really A*B*(2^-68),
and needs to be multiplied by 2^34 to get the same scaling as for A and B.
<syntaxhighlight lang="edsac">
[Calculation of Catalan numbers.
EDSAC program, Initial Orders 2.]
 
[Define where to store the list of Catalan numbers.]
T 54 K [store address in location 54, so that values
are accessed by code letter C (for Catalan)]
P 200 F [<------ address here]
 
[Modification of library subroutine P7.
Prints signed integer up to 10 digits, right-justified.
54 storage locations; working position 4D.
Must be loaded at an even address.
Input: Number is at 0D.]
T 56 K
GKA3FT42@A47@T31@ADE10@T31@A48@T31@SDTDH44#@NDYFLDT4DS43@TF
H17@S17@A43@G23@UFS43@T1FV4DAFG50@SFLDUFXFOFFFSFL4FT4DA49@T31@
A1FA43@G20@XFP1024FP610D@524D!FO46@O26@XFO46@SFL8FT4DE39@
 
[Main routine]
T 120 K [load at 120]
G K [set @ (theta) to load address]
[Variables]
[0] P F [index of Catalan number]
[Constants]
[1] P 7 D [maximum index required]
[2] P D [single-word 1]
[3] P 2 F [to change addresses by 2]
[4] H #C [these 3 are used to manufacture EDSAC orders]
[5] T #C
[6] V #C
[7] K 4096 F [(1) add to change T order into H order
(2) teleprinter null]
[8] # F [figures shift]
[9] ! F [space]
[10] @ F [carriage return]
[11] & F [line feed]
 
[Enter with acc = 0]
[12] O 8 @ [set teleprinter to figures]
T 4 D [clear 5F and sandwich bit]
A 2 @ [load single-word 1]
T 4 F [store as double word at 4D; clear acc]
[Here with index in acc, Catalan number in 4D]
[16] U @ [store index]
L 1 F [times 4 by shifting]
A 5 @ [make T order to store Catalan number]
U 27 @ [plant in code]
A 7 @ [make H order with same address]
U 45 @ [plant in code]
S 47 @ [make A order with same address]
T 34 @ [plant in code]
A 6 @ [load V order for start of list]
T 46 @ [plant in code]
A 4 D [Catalan number from temp store]
[27] T #C [store in list (manufactured order)]
T D [clear 1F and sandwich bit]
A @ [load single-word index]
T F [store as double word at 0D]
[31] A 31 @ [for return from print subroutine]
G 56 F [print index]
O 9 @ [followed by space]
[34] A #C [load Catalan number (manufactured order)]
T D [to 0D for printing]
[36] A 36 @ [for return from print subroutine]
G 56 F [print Catalan number]
O 10 @ [followed by new line]
O 11 @
T 4 D [clear partial sum]
A @ [load index]
S 1 @ [reached the maximum?]
E 64 @ [if so, jump to exit]
[Inner loop to compute sum of products C{i}*C(n-1}]
[44] T F [clear acc]
[45] H #C [C{n-i} to mult reg (manufactured order)]
[46] V #C [acc := C{i}*C{n-i} (manufactiured order)]
[Multiply product by 2^34 (see preamble). The 'L F' order is
also exploited above to convert an H order into an A order.]
[47] L F [shift acc left by 13 (the maximum available)]
L F [shift 13 more]
L 64 F [shift 8 more, total 34]
A 4 D [add partial sum]
T 4 D [update partial sum]
A 46 @ [inc i in V order]
A 3 @
T 46 @
A 45 @ [dec (n - i) in H order]
S 3 @
U 45 @
S 4 @ [is (n - i) now negative?]
E 44 @ [if not, loop back]
[Here with latest Catalan number in temp store 4D]
T F [clear acc]
A @ [load index]
A 2 @ [add 1]
E 16 @ [back to start of outer loop]
[64] O 7 @ [exit; print null to flush teleprinter buffer]
Z F [stop]
E 12 Z [define entry point]
P F [acc = 0 on entry]
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
<lang Eiffel>
class
APPLICATION
Line 1,185 ⟶ 2,529:
 
 
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,204 ⟶ 2,548:
2674440
</pre>
 
=={{header|Elixir}}==
{{trans|Erlang}}
<langsyntaxhighlight lang="elixir">defmodule Catalan do
def cat(n), do: div( factorial(2*n), factorial(n+1) * factorial(n) )
Line 1,229 ⟶ 2,572:
end
 
Catalan.test</langsyntaxhighlight>
 
{{out}}
Line 1,240 ⟶ 2,583:
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440]
</pre>
 
=={{header|Erlang}}==
<langsyntaxhighlight lang="erlang">-module(catalan).
 
-export([test/0]).
Line 1,271 ⟶ 2,613:
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]]).</langsyntaxhighlight>
{{out}}
<pre>
Line 1,281 ⟶ 2,623:
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440]
</pre>
 
=={{header|ERRE}}==
<syntaxhighlight lang="text">PROGRAM CATALAN
 
PROCEDURE CATALAN(N->RES)
Line 1,298 ⟶ 2,639:
END FOR
END PROGRAM
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,318 ⟶ 2,659:
15 = 9694845
</pre>
 
 
=={{header|Euphoria}}==
<langsyntaxhighlight Euphorialang="euphoria">--Catalan number task from Rosetta Code wiki
--User:Lnettnay
 
Line 1,343 ⟶ 2,682:
for i = 0 to 15 do
? catalan(i)
end for</langsyntaxhighlight>
{{out}}
<pre>
Line 1,363 ⟶ 2,702:
9694845
</pre>
 
=={{header|F_Sharp|F#}}==
<syntaxhighlight lang="fsharp">
<p>In the REPL (with 3rd equation):</p>
<pre>> Seq.unfold(fun (c,n) -> let cc = 2*(2*n-1)*c/(n+1) in Some(c,(cc,n+1))) (1,1) |> Seq.take 15 |> Seq.iter (printf "%i, ");;
</syntaxhighlight>
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, val it : unit = ()
{{out}}
<pre>
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440,
</pre>
 
=={{header|Factor}}==
The first method:
This is the last solution, memoized by using arrays. Run in scratchpad.
<syntaxhighlight lang ="factor">USING: next (kernel seqmath --math.combinatorics newseqprettyprint );
 
: catalan ( n -- n ) [ 1 + recip ] [ 2 * ] [ nCk * ] tri ;
 
15 [ catalan . ] each-integer</syntaxhighlight>
{{out}}
<pre>
1
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440
</pre>
 
The last method, memoized by using arrays.
<syntaxhighlight lang="factor">USING: kernel math prettyprint sequences ;
 
: next ( seq -- newseq )
[ ] [ last ] [ length ] tri
[ 2 * 1 - 2 * ] [ 1 + ] bi /
* suffix ;
 
: Catalan ( n -- seq ) V{ 1 } swap 1 - [ next ] times ;
15 Catalan .
V{
1
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440
}</lang>
 
15 Catalan .</syntaxhighlight>
{{out}}
Similar to above.
=={{header|Fantom}}==
{{incorrect|Fantom|series starts 1, 1, 2, ...}}
<lang fantom>class Main
<syntaxhighlight lang="fantom">class Main
{
static Int factorial (Int n)
Line 1,448 ⟶ 2,802:
}
}
}</langsyntaxhighlight>
22! exceeds the range of Fantom's Int class, so the first technique fails afer n=10
<pre>
Line 1,467 ⟶ 2,821:
15 -2 9694845 9694845
</pre>
=={{header|Fermat}}==
 
<syntaxhighlight lang="fermat">Func Catalan(n)=(2*n)!/((n+1)!*n!).;
for i=1 to 15 do !Catalan(i);!' ' od;</syntaxhighlight>
{{out}}<pre>
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</pre>
=={{header|Forth}}==
<langsyntaxhighlight lang="forth">: catalan ( n -- ) 1 swap 1+ 1 do dup cr . i 2* 1- 2* i 1+ */ loop drop ;</langsyntaxhighlight>
 
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
<langsyntaxhighlight lang="fortran">program main
!=======================================================================================
implicit none
Line 1,516 ⟶ 2,874:
 
!=======================================================================================
end function catalan_numbers</langsyntaxhighlight>
{{out}}
<pre>
Line 1,539 ⟶ 2,897:
===============
</pre>
 
=={{header|FreeBASIC}}==
<lang freebasic>' FB 1.05.0 Win64
 
Function factorial(n As UInteger) As UInteger
If n = 0 Then Return 1
Return n * factorial(n - 1)
End Function
 
Function catalan1(n As UInteger) As UInteger
Dim prod As UInteger = 1
For i As UInteger = n + 2 To 2 * n
prod *= i
Next
Return prod / factorial(n)
End Function
 
Function catalan2(n As UInteger) As UInteger
If n = 0 Then Return 1
Dim sum As UInteger = 0
For i As UInteger = 0 To n - 1
sum += catalan2(i) * catalan2(n - 1 - i)
Next
Return sum
End Function
 
Function catalan3(n As UInteger) As UInteger
If n = 0 Then Return 1
Return catalan3(n - 1) * 2 * (2 * n - 1) \ (n + 1)
End Function
 
Print "n", "First", "Second", "Third"
Print "-", "-----", "------", "-----"
Print
For i As UInteger = 0 To 15
Print i, catalan1(i), catalan2(i), catalan3(i)
Next
Print
Print "Press any key to quit"
Sleep</lang>
 
{{out}}
<pre>
n First Second Third
- ----- ------ -----
 
0 1 1 1
1 1 1 1
2 2 2 2
3 5 5 5
4 14 14 14
5 42 42 42
6 132 132 132
7 429 429 429
8 1430 1430 1430
9 4862 4862 4862
10 16796 16796 16796
11 58786 58786 58786
12 208012 208012 208012
13 742900 742900 742900
14 2674440 2674440 2674440
15 9694845 9694845 9694845
</pre>
 
=={{header|Frink}}==
Frink includes efficient algorithms for calculating arbitrarily-large binomial coefficients and automatically caches factorials.
<langsyntaxhighlight lang="frink">catalan[n] := binomial[2n,n]/(n+1)
for n = 0 to 15
println[catalan[n]]</langsyntaxhighlight>
 
=={{header|FunL}}==
<langsyntaxhighlight lang="funl">import integers.choose
import util.TextTable
 
Line 1,631 ⟶ 2,924:
t.row( i, catalan(i), catalan2(i), catalan3(i) )
println( t )</langsyntaxhighlight>
 
{{out}}
Line 1,657 ⟶ 2,950:
+----+------------+---------+-----------+
</pre>
 
=={{header|Fōrmulæ}}==
 
{{FormulaeEntry|page=https://formulae.org/?script=examples/Catalan_numbers}}
 
'''Solution'''
 
'''Direct definition'''
 
[[File:Fōrmulæ - Catalan numbers 01.png]]
 
[[File:Fōrmulæ - Catalan numbers 02.png]]
 
'''Direct definition (alternative)'''
 
The expression <math>\frac{(2n)!}{(n+1)!\,n!}</math> turns out to be equals to <math>\prod_{k=2}^{n}\frac{n + k}{k}</math>
 
[[File:Fōrmulæ - Catalan numbers 03.png]]
 
(same result)
 
'''No directly defined'''
 
Recursive definitions are easy to write, but extremely inefficient (specially the first one).
 
Because a list is intended to be get, the list of previous values can be used as a form of memoization, avoiding recursion.
 
The next function make use of the "second" form of recursive definition (without recursion):
 
[[File:Fōrmulæ - Catalan numbers 04.png]]
 
[[File:Fōrmulæ - Catalan numbers 05.png]]
 
(same result)
 
=={{header|GAP}}==
<langsyntaxhighlight lang="gap">Catalan1 := n -> Binomial(2*n, n) - Binomial(2*n, n - 1);
 
Catalan2 := n -> Binomial(2*n, n)/(n + 1);
Line 1,689 ⟶ 3,016:
List([0 .. 14], Catalan4);
# Same output for all four:
# [ 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440 ]</langsyntaxhighlight>
 
=={{header|Go}}==
Direct:
<langsyntaxhighlight lang="go">package main
 
import (
Line 1,705 ⟶ 3,031:
fmt.Println(c.Div(b.Binomial(n*2, n), c.SetInt64(n+1)))
}
}</langsyntaxhighlight>
{{out}}
<pre>
Line 1,724 ⟶ 3,050:
2674440
</pre>
Recursive (alternative):
<syntaxhighlight lang="go">
package main
 
import (
"fmt"
"math/big"
)
 
func c(n int64) *big.Int {
if n == 0 {
return big.NewInt(1)
} else {
var t1, t2, t3, t4, t5, t6 big.Int
t1.Mul(big.NewInt(2), big.NewInt(n))
t2.Sub(&t1, big.NewInt(1))
t3.Mul(big.NewInt(2), &t2)
t4.Add(big.NewInt(n), big.NewInt(1))
t5.Mul(&t3, c(n-1))
t6.Div(&t5, &t4)
return &t6
}
}
 
func main() {
for n := int64(1); n < 16; n++ {
fmt.Println(c(n))
}
}
</syntaxhighlight>
{{out}}
<pre>
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440
9694845
</pre>
=={{header|Groovy}}==
<syntaxhighlight lang="groovy">
<lang Groovy>
class Catalan
{
Line 1,750 ⟶ 3,123:
}
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,770 ⟶ 3,143:
</pre>
=={{header|Harbour}}==
<langsyntaxhighlight lang="visualfoxpro">
PROCEDURE Main()
LOCAL i
Line 1,788 ⟶ 3,161:
 
RETURN nCatalan
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,808 ⟶ 3,181:
5: 9694845
</pre>
 
=={{header|Haskell}}==
<langsyntaxhighlight lang="haskell">-- Three infinite lists, corresponding to the three definitions in the problem
-- definitions in the problem statement.
 
cats1 :: [Integer]
cats1 = map (\n -> product [n+2..2*n] `div` product [1..n]) [0..]
cats1 =
(div . product . (enumFromTo . (2 +) <*> (2 *)))
<*> (product . enumFromTo 1) <$> [0 ..]
 
cats2 :: [Integer]
cats2 = 1 : map (\n -> sum $ zipWith (*) (reverse (take n cats2)) cats2) [1..]
cats2 =
1 :
fmap
(\n -> sum (zipWith (*) (reverse (take n cats2)) cats2))
[1 ..]
 
cats3 :: [Integer]
cats3 = scanl (\c n -> c*2*(2*n-1) `div` (n+1)) 1 [1..]
cats3 =
scanl
(\c n -> c * 2 * (2 * n - 1) `div` succ n)
1
[1 ..]
 
main :: IO ()
main = mapM_ (print . take 15) [cats1, cats2, cats3]</lang>
main = mapM_ (print . take 15) [cats1, cats2, cats3]</syntaxhighlight>
{{out}}
<pre>[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440]
<pre>
[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]</pre>
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440]
</pre>
 
=={{header|Icon}} and {{header|Unicon}}==
<langsyntaxhighlight Iconlang="icon">procedure main(arglist)
every writes(catalan(i0 to 14)," ")
end
 
Line 1,835 ⟶ 3,218:
static M
initial M := table()
n=0 & return 1
 
if n > 0 then
return (n = 1) | \M[n] | ( M[n] := (2*(2*n-1)*catalan(n-1))/(n+1))
end</langsyntaxhighlight>
{{out}}
<pre>1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre>
 
=={{header|J}}==
<langsyntaxhighlight lang="j"> ((! +:) % >:) i.15x
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440</langsyntaxhighlight>
 
=={{header|Java}}==
Replace double inexact computations with BigInteger implementation.
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"). [[Category:Memoization]]
<syntaxhighlight lang="java">
<lang java5>import java.util.HashMap;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
 
public class CatalanCatlanNumbers {
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 public static doublevoid factmain(longString[] nargs) {
Catlan f1 = new Catlan1();
if(facts.containsKey(n)){
Catlan f2 = new Catlan2();
return facts.get(n);
Catlan f3 = new Catlan3();
}
System.out.printf(" Formula 1 Formula 2 Formula 3%n");
double fact = 1;
for (long iint n = 20 ; in <= n15 ; in++ ) {
System.out.printf("C(%2d) = %,12d %,12d %,12d%n", n, f1.catlin(n), f2.catlin(n), f3.catlin(n));
fact *= i; //could be further optimized, but it would probably be ugly
}
}
}
facts.put(n, fact);
return fact;
private static interface Catlan {
}
public BigInteger catlin(long n);
}
private static class Catlan1 implements Catlan {
 
// C(n) = (2n)! / (n+1)!n!
private static double catI(long n){
@Override
if(!catsI.containsKey(n)){
public BigInteger catlin(long n) {
catsI.put(n, fact(2 * n)/(fact(n+1)*fact(n)));
List<Long> numerator = new ArrayList<>();
}
for ( long k = n+2 ; k <= 2*n ; k++ ) {
return catsI.get(n);
numerator.add(k);
}
}
private static double catR1(long n){
List<Long> denominator = new ArrayList<>();
if(catsR1.containsKey(n)){
for ( long k = 2 ; k <= n ; k++ ) {
return catsR1.get(n);
denominator.add(k);
}
}
double sum = 0;
for(int i = 0; i < n; i++){
for ( int i = numerator.size()-1 ; i >= 0 ; i-- ) {
sum += catR1(i) * catR1(n - 1 - i);
for ( int j = denominator.size()-1 ; j >= 0 ; j-- ) {
}
if ( denominator.get(j) == 1 ) {
catsR1.put(n, sum);
continue;
return sum;
}
}
if ( numerator.get(i) % denominator.get(j) == 0 ) {
long val = numerator.get(i) / denominator.get(j);
private static double catR2(long n){
numerator.set(i, val);
if(!catsR2.containsKey(n)){
denominator.remove(denominator.get(j));
catsR2.put(n, ((2.0*(2*(n-1) + 1))/(n + 1)) * catR2(n-1));
if ( val == 1 ) {
}
break;
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>
{{out}}
<pre>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</pre>
 
BigInteger catlin = BigInteger.ONE;
for ( int i = 0 ; i < numerator.size() ; i++ ) {
catlin = catlin.multiply(BigInteger.valueOf(numerator.get(i)));
}
for ( int i = 0 ; i < denominator.size() ; i++ ) {
catlin = catlin.divide(BigInteger.valueOf(denominator.get(i)));
}
return catlin;
}
}
private static class Catlan2 implements Catlan {
 
private static Map<Long,BigInteger> CACHE = new HashMap<>();
static {
CACHE.put(0L, BigInteger.ONE);
}
// C(0) = 1, C(n+1) = sum(i=0..n,C(i)*C(n-i))
@Override
public BigInteger catlin(long n) {
if ( CACHE.containsKey(n) ) {
return CACHE.get(n);
}
BigInteger catlin = BigInteger.ZERO;
n--;
for ( int i = 0 ; i <= n ; i++ ) {
//System.out.println("n = " + n + ", i = " + i + ", n-i = " + (n-i));
catlin = catlin.add(catlin(i).multiply(catlin(n-i)));
}
CACHE.put(n+1, catlin);
return catlin;
}
}
private static class Catlan3 implements Catlan {
 
private static Map<Long,BigInteger> CACHE = new HashMap<>();
static {
CACHE.put(0L, BigInteger.ONE);
}
// C(0) = 1, C(n+1) = 2*(2n-1)*C(n-1)/(n+1)
@Override
public BigInteger catlin(long n) {
if ( CACHE.containsKey(n) ) {
return CACHE.get(n);
}
BigInteger catlin = BigInteger.valueOf(2).multiply(BigInteger.valueOf(2*n-1)).multiply(catlin(n-1)).divide(BigInteger.valueOf(n+1));
CACHE.put(n, catlin);
return catlin;
}
}
 
}
</syntaxhighlight>
{{out}}
<pre>
Formula 1 Formula 2 Formula 3
C( 0) = 1 1 1
C( 1) = 1 1 1
C( 2) = 2 2 2
C( 3) = 5 5 5
C( 4) = 14 14 14
C( 5) = 42 42 42
C( 6) = 132 132 132
C( 7) = 429 429 429
C( 8) = 1,430 1,430 1,430
C( 9) = 4,862 4,862 4,862
C(10) = 16,796 16,796 16,796
C(11) = 58,786 58,786 58,786
C(12) = 208,012 208,012 208,012
C(13) = 742,900 742,900 742,900
C(14) = 2,674,440 2,674,440 2,674,440
C(15) = 9,694,845 9,694,845 9,694,845
</pre>
=={{header|JavaScript}}==
 
<lang javascript><html><head><title>Catalan</title></head>
===Procedural===
<syntaxhighlight lang="javascript"><html><head><title>Catalan</title></head>
<body><pre id='x'></pre><script type="application/javascript">
function disp(x) {
Line 1,992 ⟶ 3,391:
disp(i + '\t' + cata1(i) + '\t' + cata2(i) + '\t' + cata3(i));
 
</script></body></html></langsyntaxhighlight>
{{out}}
<pre> meth1 meth2 meth3
Line 2,011 ⟶ 3,410:
14 2674440 2674440 2674440
15 9694845 9694845 9694845</pre>
 
===Functional===
 
Defining an infinite list:
 
<syntaxhighlight lang="javascript">(() => {
"use strict";
 
// ----------------- CATALAN NUMBERS -----------------
 
// catalansDefinitionThree :: [Int]
const catalansDefinitionThree = () =>
// An infinite sequence of Catalan numbers.
scanlGen(
c => n => Math.floor(
(2 * c * pred(2 * n)) / succ(n)
)
)(1)(
enumFrom(1)
);
 
 
// ---------------------- TEST -----------------------
// main :: IO ()
const main = () =>
take(15)(
catalansDefinitionThree()
);
 
 
// --------------------- GENERIC ---------------------
 
// enumFrom :: Enum a => a -> [a]
const enumFrom = function* (n) {
// An infinite sequence of integers,
// starting with n.
let v = n;
 
while (true) {
yield v;
v = 1 + v;
}
};
 
 
// pred :: Int -> Int
const pred = x =>
x - 1;
 
 
// scanlGen :: (b -> a -> b) -> b -> Gen [a] -> [b]
const scanlGen = f =>
// The series of interim values arising
// from a catamorphism over an infinite list.
startValue => function* (gen) {
let
a = startValue,
x = gen.next();
 
yield a;
while (!x.done) {
a = f(a)(x.value);
yield a;
x = gen.next();
}
};
 
 
// succ :: Int -> Int
const succ = x =>
1 + x;
 
 
// take :: Int -> [a] -> [a]
// take :: Int -> String -> String
const take = n =>
// The first n elements of a list,
// string of characters, or stream.
xs => Array.from({
length: n
}, () => {
const x = xs.next();
 
return x.done ? [] : [x.value];
}).flat();
 
 
// MAIN ---
return JSON.stringify(main(), null, 2);
})();</syntaxhighlight>
{{Out}}
<pre>[
1,
1,
2,
5,
14,
42,
132,
429,
1430,
4862,
16796,
58786,
208012,
742900,
2674440
]</pre>
 
=={{header|jq}}==
Line 2,018 ⟶ 3,525:
that formula is used (a) to define a function for computing a single Catalan number; (b) to define a function for generating a sequence of Catalan numbers; and (c) to write a single expression for generating a sequence of Catalan numbers using jq's builtin "recurse/1" filter.
==== Compute a single Catalan number====
<langsyntaxhighlight lang="jq">def catalan:
if . == 0 then 1
elif . < 0 then error("catalan is not defined on \(.)")
else (2 * (2*. - 1) * ((. - 1) | catalan)) / (. + 1)
end;</langsyntaxhighlight>
'''Example 1'''
<langsyntaxhighlight lang="jq">(range(0; 16), 100) as $i | $i | catalan | [$i, .]</langsyntaxhighlight>
{{Out}}
<div style="overflow:scroll; height:150px;">
<langsyntaxhighlight lang="sh">$ jq -M -n -c -f Catalan_numbers.jq
[0,1]
[1,1]
Line 2,045 ⟶ 3,552:
[15,9694845]
[100,8.96519947090131e+56]
</langsyntaxhighlight></div>
 
==== Generate a sequence of Catalan numbers ====
<langsyntaxhighlight lang="jq">def catalan_series(max):
def _catalan: # state: [n, catalan(n)]
if .[0] > max then empty
Line 2,056 ⟶ 3,563:
end;
[0,1] | _catalan;
</syntaxhighlight>
</lang>
'''Example 2''':
<syntaxhighlight lang ="jq">catalan_series(15)</langsyntaxhighlight>
{{Out}}
As above for 0 to 15.
==== An expression to generate Catalan numbers ====
<syntaxhighlight lang="jq">
<lang jq>
[0,1]
| recurse( if .[0] == 15 then empty
else .[1] as $c | (.[0] + 1) | [ ., (2 * (2*. - 1) * $c) / (. + 1) ]
end )</langsyntaxhighlight>
{{out}}
As above for 0 to 15.
=={{header|Julia}}==
{{works with|Julia|0.6}}
 
<syntaxhighlight lang="julia">catalannum(n::Integer) = binomial(2n, n) ÷ (n + 1)
 
@show catalannum.(1:15)
@show catalannum(big(100))</syntaxhighlight>
 
=={{header|Julia}}==
<lang julia>Catalan(n::Integer) = div(binomial(2n, n), n+1)</lang>
{{out}}
<pre>catalannum.(1:15) = [1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]
<pre>julia> [Catalan(n) for n=1:15]
catalannum(big(100)) = 896519947090131496687170070074100632420837521538745909320</pre>
15-element Array{Int64,1}:
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440
9694845
 
julia> Catalan(big(100))
896519947090131496687170070074100632420837521538745909320
</pre>
(In the second example, we have used arbitrary-precision integers to avoid overflow for large Catalan numbers.)
 
=={{header|K}}==
<langsyntaxhighlight 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</langsyntaxhighlight>
 
=={{header|Kotlin}}==
{{works with|Java|1.7.0}}
{{works with|Kotlin|1.1.4}}
<langsyntaxhighlight lang="scala">abstract class Catalan {
abstract operator fun invoke(n: Int) : Double
 
Line 2,156 ⟶ 3,648:
println()
}
}</langsyntaxhighlight>
{{out}}
<pre> 1 1 1
Line 2,175 ⟶ 3,667:
9694845 9694845 9694845</pre>
 
=={{header|Liberty BASICLambdatalk}}==
{{trans|Javascript}}
<lang lb>print "non-recursive version"
print catNonRec(5)
for i = 0 to 15
print i;" = "; catNonRec(i)
next
print
 
<h3>1) catalan1</h3>
print "recursive version"
print catRec(5)
for i = 0 to 15
print i;" = "; catRec(i)
next
print
 
<syntaxhighlight lang="scheme">
print "recursive with memoisation"
{def catalan1
redim cats(20) 'clear the array
{def fac {lambda {:n} {* {S.serie 1 :n}}}}
print catRecMemo(5)
{lambda {:n}
for i = 0 to 15
{floor {+ {/ {fac {* 2 :n}} {fac {+ :n 1}} {fac :n}} 0.5}}}}
print i;" = "; catRecMemo(i)
-> catalan1
next
print
 
{S.map catalan1 {S.serie 1 15}}
-> 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</syntaxhighlight>
 
<h3>2) catalan2</h3>
wait
 
<syntaxhighlight lang="scheme">
function catNonRec(n) 'non-recursive version
{def catalan2
catNonRec=1
{def catalan2.sum
for i=1 to n
{lambda {:n :a :s :i}
catNonRec=((2*((2*i)-1))/(i+1))*catNonRec
{if next{= :i :n}
then {A.set! :n :s :a}
end function
else {catalan2.sum :n
:a
{+ :s {* {catalan2.loop :i :a}
{catalan2.loop {- :n :i 1} :a}}}
{+ :i 1}} }}}
{def catalan2.loop
{lambda {:n :a}
{if {= :n 0}
then 1
else {if {W.equal? {A.get :n :a} undefined}
then {A.get :n {catalan2.sum :n :a 0 0}}
else {A.get :n :a} }}}}
{lambda {:n}
{catalan2.loop :n {A.new}} }}
-> catalan2
 
{S.map catalan2 {S.serie 0 15}}
function catRec(n) 'recursive version
-> 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
if n=0 then
catRec=1
else
catRec=((2*((2*n)-1))/(n+1))*catRec(n-1)
end if
end function
 
</syntaxhighlight>
function catRecMemo(n) 'recursive version with memoisation
 
if n=0 then
<h3>3) catalan3</h3>
catRecMemo=1
 
else
<syntaxhighlight lang="scheme">
if cats(n-1)=0 then 'call it recursively only if not already calculated
{def catalan3
prev = catRecMemo(n-1)
{def catalan3.loop
else
{lambda {:n :a}
prev = cats(n-1)
{if {= :n end if0}
then 1
catRecMemo=((2*((2*n)-1))/(n+1))*prev
else {if {W.equal? {A.get :n :a} undefined}
end if
then {A.get :n
cats(n) = catRecMemo 'memoisation for future use
{A.set! :n
end function</lang>
{/ {* {- {* 4 :n} 2}
{catalan3.loop {- :n 1} :a}}
{+ :n 1}}
:a}}
else {A.get :n :a}
}}}}
{lambda {:n}
{catalan3.loop :n {A.new}}}}
-> catalan3
 
{S.map catalan3 {S.serie 0 15}}
-> 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</syntaxhighlight>
 
<h3>4) Alternative for a vertical diplay</h3>
 
<syntaxhighlight lang="scheme">
 
{style
td { text-align:right;
font-family:monospace;
}
}
 
{table
{tr {td} {td cat1} {td cat2} {td cat3}}
{S.map {lambda {:i} {tr {td :i}
{td {catalan1 :i}}
{td {catalan2 :i}}
{td {catalan3 :i}}}}
{S.serie 0 15}}
}
 
cat1 cat2 cat3
0 1 1 1
1 1 1 1
2 2 2 2
3 5 5 5
4 14 14 14
5 42 42 42
6 132 132 132
7 429 429 429
8 1430 1430 1430
9 4862 4862 4862
10 16796 16796 16796
11 58786 58786 58786
12 208012 208012 208012
13 742900 742900 742900
14 2674440 2674440 2674440
15 9694845 9694845 9694845
 
</syntaxhighlight>
 
=={{header|langur}}==
{{trans|Perl}}
<syntaxhighlight lang="langur">val .factorial = fn(.x) { if(.x < 2: 1; .x x self(.x - 1)) }
 
val .catalan = fn(.n) { .factorial(2 x .n) / .factorial(.n+1) / .factorial(.n) }
 
for .i in 0..15 {
writeln $"\.i:2;: \(.catalan(.i):10)"
}
 
writeln "10000: ", .catalan(10000)</syntaxhighlight>
 
{{out}}
<pre> 0: 1
1: 1
2: 2
3: 5
4: 14
5: 42
6: 132
7: 429
8: 1430
9: 4862
10: 16796
11: 58786
12: 208012
13: 742900
14: 2674440
15: 9694845
10000: 224537812493385215633593584257360578701103586219365887773293713835854436588700534490998102719114320210209905393799589701149327326500953702713977513001838761306936534407802585494454599941773729984591764542782202886796997833276495496514760245912220654267091568311812071300891219894022165175451441066691435091975969499731921675488934120638046514134965974069039677192984714638704528752769863567952620334847707274529741976558104236293861846622622783294667505268651205024766408784881872997404042356319626323351089169906635603513309014645157443570842822082866699012415455339518777770781742052837799476906230350785959040487158118992753484022865373274100095762968510625236915280143408460651206678398725681703811505423791566261735329550627967717189932855983913468867794806585863794483869239933179341394259456515091026456652770409848702116046445406995085092488210998732255656992243441519938747425554228724734242623566663631968254490897214106655375215196762710825001305055093871863518797311135688370964194817463890187212845332422257193414201244344808864449873736345425670715824582633802476282521798739438044652622163657359012681653473214512797365047989922327391063907061792126264420963262176161781711086630089636828211837643128677915076724947168653050318426339007489738275045346257959685376480042860870398232333705506506342394485443047987642390287346746539674780326188825579548593281319807827279403944008553690033855132088140116099772393778770685018936338194366302053586633406848404622048675525765095697363909787189635178694239275237185046710057476484117945279786897787624602379494797322427251542758312638233073625857897083435831841717971137851874666094337671443717108457737153283641719103639784923520519013700030680553564442331411313831920775983175313709250333784211385811480015293165463406576311626295629412110652218717603537723650144357966952842696678735624157616428716812764985074925414219421312810089785108621126934245959900367104035334200067714905754827856122801987429837706493130435832752072139392743006620396370486473952500144779413596417260472218266529167783118015414918168260722824885550181735638670588682513610805160133611349864194033776132438535863120087679096358696928233598996870302136347936567444208209125300149683552369341937471817860835774359234009557030148123353114950735217736514617017504851011193104728986836180908987352236659629183725016607437110422583156042941955830763092095074443334625318588569114114087985404048889671202396824806275701581378689568449507132793603852731445602923990458926101180821029108808623323378547869169352237448925371763574346501610378415722137519019474474794069155118626291447578558908522430436148987521551911541787974276591708584289036595642180860178815462862735993859177180582760389253540408842580225467216988321950591728369194164290645992782274919561096308372635908842325870580231011459216934235078490764707633348336131667313582584404397290232519769625777374165187949140092779343812345117947306771376053099536367169631889642304360871187460737580808157222861127968703067542270175460553478533349238111434409526724363429611803844595968793121871649699680963646793415774160274520010905236593324062464542927011227158945796188186430711399250096518886617184049325827319276468018789191520522185358895653192882843061349706085770767046601045697944646638311930027354235643643713545212361580694059553720806659066661496416423676930095857438882302891350789287291844752601744462789158506243012088536936184422120232369244564444689340142897415432231452353338115944183447986470689449043710051589958391273681116292415738776171575775695905846247205522469202801517417551374761549677412720803623129527503286287755308576386461385928958587649159872019202866614901547860974883963007792442796064165417207167072370586790722366932349325253877744621251386864069101337572557790214048760202008337611577675840153696735860276810033694744314488435390547908483357054897387317002405793108554524629034558098886977538473481750772616164313845337139245688079995996839933620829828339492800825536599964878893947278408890351634126931068657027524005795713514365098086505030570362785115155293306343520969872400876180105031975302255898787642403303027682634969586730202117121076117629457710028105378124677420093990476071697970354661002217702623344454780740808459286778553016318604430682610618871098652904537323336381304469735192868285840882036271136058499391069436145426450229039329475974178236465920534171895204155964515055983303017823692138977622016292722019365841360360274557488926673754175222061483328914099598663902320310143583379354121664996173733086613692927391384486261610892314450463841637667054196985332620403539011932606618414419229492637564924726411270720189611019154677281846409387514072618176832310721327819277699943226895919915049652045449281057471199978267843961724883768772155477073354744908923995448752333726740642292872107500458349718026322755698226793850983280706045951407323891263270928264657562125955511946782954645656015480418543664557515041692091317941000997342935512311493290722434384401250133402934163457264794261787386862382738330195237770190998115114193014769006071380834085352290585937952429981509893303796306071520571655936820282768086579891336876000368502562579738337809071051261343359121744773055264455701014137255399929760233753812017596045145926791136761130783810840502248142803073720015451941006030172192834375431286154255159659778817089767964922549014569972777126726537787896968876337799235679125368824867754881036161730805613471278633981478858113141202728303435218970292775366288829203013873713349923690394124920402725698544786016048685431525811047414746045227535216327530901827040588505255466803793791888002231571686068617764292584075135236237044383334893874602177596602979234717936820827427229615827657960492946059695301906791494260652411424538532836730097985187522379068364429583532675896349363295120431429006688249818006722311568902288350452581968418068616818268667067741994472455501649753611708445979082338902214467454627107888156489438584617793175431865532382711812960546611287516640
</pre>
 
=={{header|Logo}}==
<syntaxhighlight lang="logo">to factorial :n
output ifelse [less? :n 1] 1 [product :n factorial difference :n 1]
end
to choose :n :r
output quotient factorial :n product factorial :r factorial difference :n :r
end
to catalan :n
output product (quotient sum :n 1) choose product 2 :n :n
end
 
repeat 15 [print catalan repcount]</syntaxhighlight>
{{out}}
<pre>
1
non-recursive version
1
2
5
14
42
132
0 = 1
429
1 = 1
1430
2 = 2
4862
3 = 5
16796
4 = 14
58786
5 = 42
208012
6 = 132
742900
7 = 429
2674440</pre>
8 = 1430
=={{header|Logtalk}}==
9 = 4862
10 = 16796
11 = 58786
12 = 208012
13 = 742900
14 = 2674440
15 = 9694845
 
For this task it is instructive to show a more general-purpose interface for sequences and an implementation of it for Catalan numbers.
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
 
First, <code>loader.lgt</code>:
recursive with memoisation
 
42
<syntaxhighlight lang="logtalk">
0 = 1
:- initialization((
1 = 1
2 = % 2libraries
logtalk_load(dates(loader)),
3 = 5
logtalk_load(meta(loader)),
4 = 14
logtalk_load(types(loader)),
5 = 42
6 = % 132application
logtalk_load(seqp),
7 = 429
logtalk_load(catalan),
8 = 1430
logtalk_load(catalan_test)
9 = 4862
)).
10 = 16796
</syntaxhighlight>
11 = 58786
 
12 = 208012
The interface is defined in <code>seqp.lgt</code> as a protocol:
13 = 742900
 
14 = 2674440
<syntaxhighlight lang="logtalk">
15 = 9694845</pre>
:- protocol(seqp).
 
:- public(init/0). % reset to a beginning state if meaningful
 
:- public(nth/2). % get the nth value of the sequence
 
:- public(to_nth/2). % get from the start to the nth value of the sequence as a list
 
:- end_protocol.
</syntaxhighlight>
 
The implementation of a Catalan sequence generator is in <code>catalan.lgt</code>:
 
<syntaxhighlight lang="logtalk">
:- object(catalan, implements(seqp)).
 
:- private(catalan/2).
:- dynamic(catalan/2).
 
% Public interface.
 
init :- retractall(catalan(_,_)). % flush any memoized results
 
nth(N, V) :- \+ catalan(N, V), catalan_(N, V), !. % generate iff it's not been memoized
nth(N, V) :- catalan(N, V), !. % otherwise use the memoized version
 
to_nth(N, L) :-
integer::sequence(0, N, S), % generate a list of 0 to N
meta::map(nth, S, L). % map the nth/2 predicate to the list for all Catalan numbers up to N
 
% Local helper predicates.
 
catalan_(N, V) :-
N > 0, % calculate
N1 is N - 1,
N2 is N + 1,
catalan_(N1, V1), % via a recursive call
V is V1 * 2 * (2 * N - 1) // N2,
assertz(catalan(N, V)). % and memoize the result
catalan_(0, 1).
 
:- end_object.
</syntaxhighlight>
 
This is a memoizing implementation whose impact we will check in the test. The <code>init/0</code> predicate flushes any memoized results.
 
The test driver is a simple one that generates the first fifteen Catalan numbers four times, comparing times with and without memoization. From <code>catalan_test.lgt</code>:
 
<syntaxhighlight lang="logtalk">
:- object(catalan_test).
 
:- public(run/0).
 
run :-
% put the object into a known initial state
catalan::init,
 
% first 15 Catalan numbers, record duration.
time_operation(catalan::to_nth(15, C1), D1),
 
% first 15 Catalan numbers again, twice, recording duration.
time_operation(catalan::to_nth(15, C2), D2),
time_operation(catalan::to_nth(15, C3), D3),
 
% reset the object again
catalan::init,
 
% first 15 Catalan numbers, record duration.
time_operation(catalan::to_nth(15, C4), D4),
 
% ensure the results were the same each time
C1 = C2, C2 = C3, C3 = C4,
 
% write the results and durations of each run
write(C1), write(' '), write(D1), nl,
write(C2), write(' '), write(D2), nl,
write(C3), write(' '), write(D3), nl,
write(C4), write(' '), write(D4), nl.
% visual inspection should show all results the same
% first and final durations should be much larger
 
:- meta_predicate(time_operation(0, *)).
 
time_operation(Goal, Duration) :-
time::cpu_time(Before),
call(Goal),
time::cpu_time(After),
Duration is After - Before.
 
:- end_object.
</syntaxhighlight>
 
 
{{Out}}
 
The session at the top-level looks like this:
<pre>
?- {loader}.
% ... messages elided ...
% (0 warnings)
true.
 
?- catalan_test::run.
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845] 0.001603
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845] 0.000306
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845] 0.00026
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845] 0.001346
true.
</pre>
 
This test shows:
 
# The <code>nth/2</code> predicate works (since <code>to_nth/2</code> is implemented in terms of it).
# The <code>to_nth/2</code> predicate works.
# Memoization generates a speedup of between ~4.5× to ~6.2× over generating from scratch.
 
=={{header|Lua}}==
<langsyntaxhighlight Lualang="lua">-- recursive with memoization
local catalan = { [0] = 1 }
setmetatable(catalan, {
__index = function(c, n)
c[n] = c[n - 1] * 2 * (2 * n - 1) / (n + 1)
return c[n]
end
})
)
 
for i = 0, 14 do
print(string.format("%d", catalan[i]))
end</langsyntaxhighlight>
{{out}}
<pre>1
1
1
2
Line 2,320 ⟶ 4,005:
2674440</pre>
 
=={{header|MAD}}==
 
<syntaxhighlight lang="mad"> NORMAL MODE IS INTEGER
DIMENSION C(15)
C(0) = 1
THROUGH CALC, FOR N=1, 1, N.GE.15
CALC C(N) = ((4*N-2)*C(N-1))/(N+1)
THROUGH SHOW, FOR N=0, 1, N.GE.15
SHOW PRINT FORMAT CFMT,N,C(N)
 
VECTOR VALUES CFMT=$2HC(,I2,4H) = ,I7*$
END OF PROGRAM </syntaxhighlight>
 
{{out}}
 
<pre>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</pre>
=={{header|Maple}}==
<langsyntaxhighlight Maplelang="maple">CatalanNumbers := proc( n::posint )
return seq( (2*i)!/((i + 1)!*i!), i = 0 .. n - 1 );
end proc:
CatalanNumbers(15);
</syntaxhighlight>
</lang>
Output:
<pre>
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440
</pre>
 
 
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<langsyntaxhighlight Mathematicalang="mathematica">CatalanN[n_Integer /; n >= 0] := (2 n)!/((n + 1)! n!)</langsyntaxhighlight>
{{out|Sample Output}}
<langsyntaxhighlight Mathematicalang="mathematica">TableForm[CatalanN/@Range[0,15]]
//TableForm=
1
Line 2,353 ⟶ 4,067:
742900
2674440
9694845</langsyntaxhighlight>
 
=={{header|MATLAB}} / {{header|Octave}}==
<langsyntaxhighlight MATLABlang="matlab">function n = catalanNumberscatalanNumber(n)
for i = (1:length(n))
n(i) = (1/(n(i)+1))*nchoosek(2*n(i),n(i));
end
end</langsyntaxhighlight>
The following version iscomputes fullyat vectorizedthe andsame doestime notthe requiren afirst loopCatalan numbers (including C0).
<langsyntaxhighlight MATLABlang="matlab">function n = catalanNumbers(n)
n = arrayfun[1 cumprod(@(n)prod(n+12:4:24*n-6) ./prod (12:n+1), n)];
end</langsyntaxhighlight>
{{out|Sample Output}}
<syntaxhighlight lang="matlab">>> catalanNumber(14)
<lang MATLAB>>> catalanNumbers(14)
 
ans =
Line 2,372 ⟶ 4,085:
2674440
 
>> catalanNumbers((0:17)18)'
 
ans =
Line 2,393 ⟶ 4,106:
9694845
35357670
129644790</langsyntaxhighlight>
 
The following version uses the identity Ln(x!)=Gammaln(x+1) and prod(1:x)=sum(ln(1:x))
<syntaxhighlight lang="matlab">
CatalanNumber=@(n) round(exp(gammaln(2*n+1)-sum(gammaln([n+2 n+1]))));
</syntaxhighlight>
{{out|Sample Output}}
<syntaxhighlight lang="matlab">>>CatalanNumber(10)
 
ans =
 
16796
 
>> num2str(CatalanNumber(20))
 
ans =
 
'6564120420'
</syntaxhighlight>
=={{header|Maxima}}==
<langsyntaxhighlight 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$
Line 2,406 ⟶ 4,136:
makelist(cata2(n), n, 0, 14);
 
/* both return [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440] */</langsyntaxhighlight>
=={{header|Miranda}}==
<syntaxhighlight lang="miranda">main :: [sys_message]
main = [Stdout (lay (map (show . catalan) [0..14]))]
 
catalan :: num->num
=={{header|Nim}}==
catalan 0 = 1
<lang nim>import strutils
catalan n = (4*n - 2) * catalan (n - 1) div (n + 1)</syntaxhighlight>
{{out}}
<pre>1
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440</pre>
 
=={{header|Modula-2}}==
proc binomial(m, n): auto =
<syntaxhighlight lang="modula2">MODULE CatalanNumbers;
result = 1
FROM FormatString IMPORT FormatString;
var
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;
d = m - n
n = n
m = m
if d > n:
n = d
 
PROCEDURE binomial(m,n : LONGCARD) : LONGCARD;
while m > n:
VAR r,d : LONGCARD;
result *= m
BEGIN
dec m
r := 1;
while d > 1 and (result mod d) == 0:
d result := resultm div- dn;
IF d>n dec dTHEN
n := d;
d := m - n;
END;
WHILE m>n DO
r := r * m;
DEC(m);
WHILE (d>1) AND NOT (r MOD d # 0) DO
r := r DIV d;
DEC(d)
END
END;
RETURN r
END binomial;
 
PROCEDURE catalan1(n : LONGCARD) : LONGCARD;
BEGIN
RETURN binomial(2*n,n) DIV (1+n)
END catalan1;
 
PROCEDURE catalan2(n : LONGCARD) : LONGCARD;
VAR i,sum : LONGCARD;
BEGIN
IF n>1 THEN
sum := 0;
FOR i:=0 TO n-1 DO
sum := sum + catalan2(i) * catalan2(n - 1 - i)
END;
RETURN sum
ELSE
RETURN 1
END
END catalan2;
 
PROCEDURE catalan3(n : LONGCARD) : LONGCARD;
BEGIN
IF n#0 THEN
RETURN 2 *(2 * n - 1) * catalan3(n - 1) DIV (1 + n)
ELSE
RETURN 1
END
END catalan3;
 
VAR
blah : LONGCARD = 123;
buf : ARRAY[0..63] OF CHAR;
i : LONGCARD;
BEGIN
FormatString("\tdirect\tsumming\tfrac\n", buf);
WriteString(buf);
FOR i:=0 TO 15 DO
FormatString("%u\t%u\t%u\t%u\n", buf, i, catalan1(i), catalan2(i), catalan3(i));
WriteString(buf)
END;
ReadChar
END CatalanNumbers.</syntaxhighlight>
 
=={{header|Nim}}==
<syntaxhighlight lang="nim">import math
import strformat
 
proc catalan1(n: int): autoint =
binomialbinom(2 * n, n) div (n + 1)
 
proc catalan2(n: int): autoint =
if n == 0:
result =return 1
for i in 0 .. <n:
result += catalan2(i) * catalan2(n - 1 - i)
 
proc catalan3(n: int): int =
if n > 0: 2 * (2 * n - 1) * catalan3(n - 1) div (1 + n)
else: 1
 
for i in 0..15:
echo align($&"{i, :7),} " ", align(${catalan1(i), :7),} " ", align(${catalan2(i), :7),} " ", align(${catalan3(i), :7)}"</langsyntaxhighlight>
 
Output:
{{out}}
<pre> 0 1 1 1
1 1 1 1
Line 2,459 ⟶ 4,265:
14 2674440 2674440 2674440
15 9694845 9694845 9694845</pre>
 
=={{header|OCaml}}==
<syntaxhighlight lang="ocaml">let imp_catalan n =
<lang OCaml>
let catalan :let int refreturn = ref 01 in
for i = 1 to n do
Printf.printf "%d ," 1 ;
return := !return * 2 * (2 * i - 1) / (i + 1)
for i = 2 to 9 do
done;
let nm : int ref = ref 1 in
!return
let den : int ref = ref 1 in
 
for k = 2 to i do
let rec catalan = function
nm := (!nm)*(i+k);
| 0 -> 1
den := (!den)*k;
| n -> catalan :=(n - 1) * 2 * (!nm2 * n - 1) / (!den)n ;+ 1)
 
done;
let memoize f =
print_int (!catalan); print_string "," ;
let cache = Hashtbl.create 20 in
done;;
fun n ->
match Hashtbl.find_opt cache n with
| None ->
let x = f n in
Hashtbl.replace cache n x;
x
| Some x -> x
 
let catalan_cache = Hashtbl.create 20
 
let rec memo_catalan n =
if n = 0 then 1 else
match Hashtbl.find_opt catalan_cache n with
| None ->
let x = memo_catalan (n - 1) * 2 * (2 * n - 1) / (n + 1) in
Hashtbl.replace catalan_cache n x;
x
| Some x -> x
 
let () =
</lang>
if not !Sys.interactive then
let bench label f n times =
let start = Unix.gettimeofday () in
begin
for i = 1 to times do f n done;
let stop = Unix.gettimeofday () in
Printf.printf "%s (%d runs) : %.3f\n"
label times (stop -. start)
end in
let show f g h f' n =
for i = 0 to n do
Printf.printf "%2d %7d %7d %7d %7d\n"
i (f i) (g i) (h i) (f' i)
done
in
List.iter (fun (l, f) -> bench l f 15 10_000_000)
["imperative", imp_catalan;
"recursive", catalan;
"hand-memoized", memo_catalan;
"memoized", (memoize catalan)];
show imp_catalan catalan memo_catalan (memoize catalan) 15
</syntaxhighlight>
{{out}}
<pre>$ ocaml unix.cma catalan.ml
<pre>
imperative (10000000 runs) : 3.420
1 ,2,5,14,42,132,429,1430,4862(upto 9 numbers only)
recursive (10000000 runs) : 3.821
</pre>
hand-memoized (10000000 runs) : 0.531
memoized (10000000 runs) : 0.515
0 1 1 1 1
1 1 1 1 1
2 2 2 2 2
3 5 5 5 5
4 14 14 14 14
5 42 42 42 42
6 132 132 132 132
7 429 429 429 429
8 1430 1430 1430 1430
9 4862 4862 4862 4862
10 16796 16796 16796 16796
11 58786 58786 58786 58786
12 208012 208012 208012 208012
13 742900 742900 742900 742900
14 2674440 2674440 2674440 2674440
15 9694845 9694845 9694845 9694845
 
$ ocamlopt -O2 unix.cmxa catalan.ml -o catalan
$ ./catalan
imperative (10000000 runs) : 2.020
recursive (10000000 runs) : 2.283
hand-memoized (10000000 runs) : 0.159
memoized (10000000 runs) : 0.167
...</pre>
=={{header|Oforth}}==
 
<syntaxhighlight lang Oforth="oforth">: catalan(n) n ifZero: [ 1 ] else: [ catalan(n 1-) 2 n * 1- *m 2) * n 1+ / ] ;</lang>
n ifZero: [ 1 ] else: [ catalan( n 1- ) 2 n * 1- * 2 * n 1+ / ] ;</syntaxhighlight>
 
{{out}}
<pre>
import: mapping
seqFrom(0, 15) map(#catalan) .
seqFrom(0, 15) map( #catalan ) .
[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]
</pre>
 
=={{header|ooRexx}}==
Three versions of this.
<langsyntaxhighlight ooRexxlang="oorexx">loop i = 0 to 15
say "catI("i") =" .catalan~catI(i)
say "catR1("i") =" .catalan~catR1(i)
Line 2,572 ⟶ 4,444:
catR2[n] = res
end
return res</langsyntaxhighlight>
{{out}}
<pre>catI(0) = 1
Line 2,622 ⟶ 4,494:
catR1(15) = 9694845
catR2(15) = 9694845</pre>
 
=={{header|PARI/GP}}==
Memoization is not worthwhile; PARI has fast built-in facilities for calculating binomial coefficients and factorials.
<langsyntaxhighlight lang="parigp">catalan(n)=binomial(2*n,n+1)/n</langsyntaxhighlight>
A second version:
<langsyntaxhighlight lang="parigp">catalan(n)=(2*n)!/(n+1)!/n!</langsyntaxhighlight>
Naive version with binary splitting:
<langsyntaxhighlight lang="parigp">catalan(n)=prod(k=n+2,2*n,k)/prod(k=2,n,k)</langsyntaxhighlight>
Naive version:
<langsyntaxhighlight lang="parigp">catalan(n)={
my(t=1);
for(k=n+2,2*n,t*=k);
for(k=2,n,t/=k);
t
};</langsyntaxhighlight>
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:
<langsyntaxhighlight lang="parigp">vector(15,n,catalan(n))</langsyntaxhighlight>
 
=={{header|Pascal}}==
<langsyntaxhighlight lang="pascal">Program CatalanNumbers(output);
 
function catalanNumber1(n: integer): double;
Line 2,659 ⟶ 4,529:
for number := 0 to 14 do
writeln (number:3, round(catalanNumber1(number)):9);
end.</langsyntaxhighlight>
{{out}}
<pre>
Line 2,681 ⟶ 4,551:
14 2674440
</pre>
 
=={{header|Perl}}==
<langsyntaxhighlight lang="perl">sub factorial { my $f = 1; $f *= $_ for 2 .. $_[0]; $f; }
sub catalan {
my $n = shift;
Line 2,689 ⟶ 4,558:
}
 
print "$_\t@{[ catalan($_) ]}\n" for 0 .. 20;</langsyntaxhighlight>
For computing up to 20 ish, memoization is not needed. For much bigger numbers, this is faster:
<langsyntaxhighlight lang="perl">my @c = (1);
sub catalan {
use bigint;
Line 2,698 ⟶ 4,567:
 
# most of the time is spent displaying the long numbers, actually
print "$_\t", catalan($_), "\n" for 0 .. 10000;</langsyntaxhighlight>
 
That has two downsides: high memory use and slow access to an isolated large value. Using a fast binomial function can solve both these issues. The downside here is if the platform doesn't have the GMP library then binomials won't be fast.
{{libheader|ntheory}}
<langsyntaxhighlight lang="perl">use ntheory qw/binomial/;
sub catalan {
my $n = shift;
binomial(2*$n,$n)/($n+1);
}
print "$_\t", catalan($_), "\n" for 0 .. 10000;</langsyntaxhighlight>
 
=={{header|Perl 6}}==
{{works with|Rakudo|2015.12}}
The recursive formulas are easily written into a constant array, either:
 
<lang perl6>constant Catalan = 1, { [+] @_ Z* @_.reverse } ... *;</lang>
 
or
 
<lang perl6>constant Catalan = 1, |[\*] (2, 6 ... *) Z/ 2 .. *;</lang>
 
In both cases, the sixteen first values can be seen with:
<lang perl6>.say for Catalan[^15];</lang>
{{out}}
<pre>1
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440</pre>
 
=={{header|Phix}}==
See also [[Catalan_numbers/Pascal%27s_triangle#Phix]] which may be faster.
<lang Phix>
<!--<syntaxhighlight lang="phix">(phixonline)-->
-- returns inf/-nan for n>85, and needs the rounding for n>=14, accurate to n=29
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
function catalan1(integer n)
<span style="color: #000080;font-style:italic;">-- returns inf/-nan for n&gt;85, and needs the rounding for n&gt;=14, accurate to n=29</span>
return floor(factorial(2*n)/(factorial(n+1)*factorial(n))+0.5)
<span style="color: #008080;">function</span> <span style="color: #000000;">catalan1</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
end function
<span style="color: #008080;">return</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">factorial</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)/(</span><span style="color: #7060A8;">factorial</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)*</span><span style="color: #7060A8;">factorial</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">))+</span><span style="color: #000000;">0.5</span><span style="color: #0000FF;">)</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
-- returns inf for n>519, accurate to n=30:
function catalan2(integer n) -- NB: very slow!
<span style="color: #000080;font-style:italic;">-- returns inf for n&gt;519, accurate to n=30:</span>
atom res = not n
<span style="color: #008080;">function</span> <span style="color: #000000;">catalan2</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- NB: very slow!</span>
n -= 1
<span style="color: #004080;">atom</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">not</span> <span style="color: #000000;">n</span>
for i=0 to n do
<span style="color: #000000;">n</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
res += catalan2(i)*catalan2(n-i)
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
end for
<span style="color: #000000;">res</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">catalan2</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">catalan2</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>
return res
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end function
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
-- returns inf for n>514, accurate to n=30:
function catalan3(integer n)
<span style="color: #000080;font-style:italic;">-- returns inf for n&gt;514, accurate to n=30:</span>
if n=0 then return 1 end if
<span style="color: #008080;">function</span> <span style="color: #000000;">catalan3</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
return 2*(2*n-1)/(1+n)*catalan3(n-1)
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end function
<span style="color: #008080;">return</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">*(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)/(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">+</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">catalan3</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
for i=0 to 15 do
printf(1,"%2d: %10d %10d %10d\n",{i,catalan1(i),catalan2(i),catalan3(i)})
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">),</span><span style="color: #000000;">16</span><span style="color: #0000FF;">),</span>
end for
<span style="color: #000000;">times</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)</span>
 
<span style="color: #008080;">for</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">4</span> <span style="color: #008080;">do</span>
-- An explicitly memoized version of what seems to be the best, and the one that really needed it:
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
-- (and in fact it turned out to be faster than similarly memoized versions of 1 and 3, when atom)
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">15</span> <span style="color: #008080;">do</span>
-- I also converted this to use bigatoms.
<span style="color: #008080;">switch</span> <span style="color: #000000;">t</span> <span style="color: #008080;">do</span>
 
<span style="color: #008080;">case</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">catalan1</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>
include builtins\bigatom.e
<span style="color: #008080;">case</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">3</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">catalan2</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>
 
<span style="color: #008080;">case</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">4</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">catalan3</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>
sequence c2cache = {}
<span style="color: #008080;">case</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">;</span> <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%2d: %10d %10d %10d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">switch</span>
function catalan2bc(integer n) -- very fast!
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
object r -- result (a bigatom)
<span style="color: #008080;">if</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">=</span><span style="color: #000000;">4</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if n<=0 then return BA_ONE end if
<span style="color: #000000;">times</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
if n<=length(c2cache) then
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
r = c2cache[n]
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"times:%8s %10s %10s\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">times</span><span style="color: #0000FF;">)</span>
if r!=0 then return r end if
<!--</syntaxhighlight>-->
else
{{out}}
c2cache &= repeat(0,n-length(c2cache))
end if
r = BA_ZERO
for i=0 to n-1 do
r = ba_add(r,ba_multiply(catalan2bc(i),catalan2bc(n-1-i)))
end for
c2cache[n] = r
return r
end function
 
atom t0 = time() -- (this last call only)
string sc100 = ba_sprint(catalan2bc(100))
printf(1,"100: %s (%3.2fs)\n",{sc100,time()-t0})</lang>
{{out}}
<pre>
0: 1 1 1
Line 2,811 ⟶ 4,637:
14: 2674440 2674440 2674440
15: 9694845 9694845 9694845
times: 0s 1.6s 0s
100: 896519947090131496687170070074100632420837521538745909320 (0.42s)
</pre>
As expected, catalan2() is by far the slowest, so let's memoise that one!
 
=== memoized recursive gmp version ===
{{libheader|Phix/mpfr}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #000000;">builtins</span><span style="color: #0000FF;">\</span><span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">c2cache</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">catalan2m</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- very fast!</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">r</span> <span style="color: #000080;font-style:italic;">-- result (a [cached/shared] mpz)
-- (nb: modifying result will mess up cache)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c2cache</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">c2cache</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">r</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">c2cache</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c2cache</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">catalan2m</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">),</span><span style="color: #000000;">catalan2m</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">-</span><span style="color: #000000;">i</span><span style="color: #0000FF;">))</span>
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_free</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">c2cache</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">r</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">r</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">15</span> <span style="color: #008080;">do</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">catalan2m</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)))</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"0..15: %s\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #008000;">","</span><span style="color: #0000FF;">))</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"100: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">catalan2m</span><span style="color: #0000FF;">(</span><span style="color: #000000;">100</span><span style="color: #0000FF;">))})</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
0..15: 1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845
100: 896519947090131496687170070074100632420837521538745909320
</pre>
=={{header|PHP}}==
<langsyntaxhighlight lang="php"><?php
 
class CatalanNumbersSerie
Line 2,847 ⟶ 4,713:
echo "$i = $r\r\n";
}
?></langsyntaxhighlight>
{{out}}
<pre>
Line 2,867 ⟶ 4,733:
15 = 9694845
</pre>
<syntaxhighlight lang="php">
<?php
$n = 15;
$t[1] = 1;
foreach (range(1, $n+1) as $i) {
foreach (range($i, 1-1) as $j) {
$t[$j] += $t[$j - 1];
}
$t[$i +1] = $t[$i];
foreach (range($i+1, 1-1) as $j) {
$t[$j] += $t[$j -1];
}
print ($t[$i+1]-$t[$i])."\t";
}
</syntaxhighlight>
{{out}}
<pre>
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670
</pre>
=={{header|Picat}}==
{{works with|Picat}}
<syntaxhighlight lang="picat">
table
factorial(0) = 1.
 
factorial(N) = N * factorial(N - 1).
 
catalan1(N) = factorial(2 * N) // (factorial(N + 1) * factorial(N)).
 
catalan2(0) = 1.
 
catalan2(N) = 2 * (2 * N - 1) * catalan2(N - 1) // (N + 1).
 
main =>
foreach (I in 0..14)
printf("%d. %d = %d\n", I, catalan1(I), catalan2(I))
end.
</syntaxhighlight>
{{out}}
<pre>
0. 1 = 1
1. 1 = 1
2. 2 = 2
3. 5 = 5
4. 14 = 14
5. 42 = 42
6. 132 = 132
7. 429 = 429
8. 1430 = 1430
9. 4862 = 4862
10. 16796 = 16796
11. 58786 = 58786
12. 208012 = 208012
13. 742900 = 742900
14. 2674440 = 2674440
</pre>
=={{header|PicoLisp}}==
<langsyntaxhighlight PicoLisplang="picolisp"># Factorial
(de fact (N)
(if (=0 N)
Line 2,901 ⟶ 4,822:
(catalanDir N)
(catalanRec N)
(catalanAlt N) ) )</langsyntaxhighlight>
{{out}}
<pre> 0 => 1 1 1
Line 2,918 ⟶ 4,839:
13 => 742900 742900 742900
14 => 2674440 2674440 2674440</pre>
 
=={{header|PL/0}}==
{{trans|Tiny BASIC}}
Integers are limited to 32767 so only the first ten Catalan numbers can be represented. To avoid internal overflow, the program subtracts something clever from <code>c</code> and then adds it back at the end.
<syntaxhighlight lang="pascal">
var n, c, i;
begin
n := 0; c := 1;
! c;
while n <= 9 do
begin
n := n + 1;
i := 0;
while c > 0 do
begin
c := c - (n + 1);
i := i + 1
end;
c := 2 * (2 * n - 1) * c / (n + 1);
c := c + 2 * i * (2 * n - 1);
! c
end;
end.
</syntaxhighlight>
{{out}}
<pre>
1
1
2
5
14
42
132
429
1430
4862
16796
</pre>
 
=={{header|PL/I}}==
<langsyntaxhighlight PLlang="pl/Ii">catalan: procedure options (main); /* 23 February 2012 */
declare (i, n) fixed;
 
Line 2,938 ⟶ 4,897:
end c;
 
end catalan;</langsyntaxhighlight>
{{out}}
<pre>
Line 2,965 ⟶ 4,924:
6564120420
</pre>
 
=={{header|PlainTeX}}==
<langsyntaxhighlight lang="tex">\newcount\n
\newcount\r
\newcount\x
Line 2,988 ⟶ 4,946:
\advance\x by 1\ifnum\x<15\repeat
 
\bye</langsyntaxhighlight>
 
=={{header|PowerShell}}==
<syntaxhighlight lang="powershell">
<lang PowerShell>
function Catalan([uint64]$m) {
function fact([bigint]$n) {
Line 3,002 ⟶ 4,959:
}
0..15 | foreach {"catalan($_): $(catalan $_)"}
</syntaxhighlight>
</lang>
<b>Output:</b>
<pre>
Line 3,025 ⟶ 4,982:
===An Alternate Version===
This version could easily be modified to work with big integers.
<syntaxhighlight lang="powershell">
<lang PowerShell>
function Get-CatalanNumber
{
Line 3,077 ⟶ 5,034:
}
}
</syntaxhighlight>
</lang>
Get the first fifteen Catalan numbers as a PSCustomObject:
<syntaxhighlight lang="powershell">
<lang PowerShell>
0..14 | Get-CatalanNumber
</syntaxhighlight>
</lang>
{{Out}}
<pre>
Line 3,103 ⟶ 5,060:
</pre>
To return only the array of Catalan numbers:
<syntaxhighlight lang="powershell">
<lang PowerShell>
(0..14 | Get-CatalanNumber).CatalanNumber
</syntaxhighlight>
</lang>
{{Out}}
<pre>
Line 3,124 ⟶ 5,081:
2674440
</pre>
 
=={{header|Prolog}}==
{{Works with|SWI-Prolog}}
<langsyntaxhighlight Prologlang="prolog">catalan(N) :-
length(L1, N),
L = [1 | L1],
Line 3,143 ⟶ 5,099:
 
my_write(N, V) :-
format('~w : ~w~n', [N, V]).</langsyntaxhighlight>
{{out}}
<pre> ?- catalan(15).
Line 3,163 ⟶ 5,119:
15 : 9694845
true .
</pre>
 
=={{header|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>
{{out|Sample Output}}
<pre>
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
</pre>
 
Line 3,233 ⟶ 5,125:
 
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
{{Works with|Python|3}}
<syntaxhighlight lang="python">from math import factorial
import functools
 
 
def memoize(func):
cache = {}
 
def memoized(key):
# Returned, new, memoized version of decorated function
Line 3,249 ⟶ 5,145:
def fact(n):
return factorial(n)
 
 
def cat_direct(n):
return fact(2 * n) // fact(n + 1) // fact(n)
 
 
@memoize
@memoize
def catR1(n):
return ( 1 if n == 0 else (
else sum( catR1(i) * catR1(n - 1 - i) for i in range(n))
)
for i in range(n) ) )
 
 
@memoize
@memoize
def catR2(n):
return ( 1 if n == 0 else (
else ( ( 4 * n - 2 ) * catR2( n - 1) ) // ( n + 1 ) )
)
 
 
Line 3,268 ⟶ 5,168:
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)</langsyntaxhighlight>
{{out|Sample Output}}
<pre>CAT_DIRECT CATR1 CATR2
Line 3,296 ⟶ 5,195:
2674440 2674440 2674440</pre>
 
=={{header|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>
 
The third definition is directly expressible, as an infinite series, in terms of '''itertools.accumulate''':
<syntaxhighlight lang="python">'''Catalan numbers'''
 
from itertools import accumulate, chain, count, islice
 
 
# catalans3 :: [Int]
def catalans3():
'''Infinite sequence of Catalan numbers
'''
def go(c, n):
return 2 * c * pred(2 * n) // succ(n)
 
return accumulate(
chain([1], count(1)), go
)
 
 
# ------------------------- TEST -------------------------
# main :: IO ()
def main():
'''Catalan numbers, definition 3'''
print("Catalans 1-15:\n")
print(
'\n'.join([
f'{n:>10}' for n
in islice(catalans3(), 15)
])
)
 
 
# ----------------------- GENERIC ------------------------
 
# pred :: Int -> Int
def pred(n):
'''Predecessor function'''
return n - 1
 
 
# succ :: Int -> Int
def succ(n):
'''Successor function'''
return 1 + n
 
 
# MAIN ---
if __name__ == '__main__':
main()</syntaxhighlight>
{{Out}}
<pre>Catalans 1-15:
 
1
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440</pre>
=={{header|Quackery}}==
 
<syntaxhighlight lang="quackery"> [ 1 over times [ over i 1+ + * ] nip ] is 2n!/n! ( n --> n )
 
[ times [ i 1+ / ] ] is /n! ( n --> n )
 
[ dup 2n!/n! swap 1+ /n! ] is catalan ( n --> n )
 
15 times [ i^ dup echo say " : " catalan echo cr ]</syntaxhighlight>
 
{{out}}
 
<pre>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
</pre>
=={{header|R}}==
<syntaxhighlight lang="r">catalan <- function(n) choose(2*n, n)/(n + 1)
catalan(0:15)
[1] 1 1 2 5 14 42 132 429 1430
[10] 4862 16796 58786 208012 742900 2674440 9694845</syntaxhighlight>
=={{header|Racket}}==
<langsyntaxhighlight lang="racket">#lang racket
(require planet2)
; (install "this-and-that") ; uncomment to install
Line 3,314 ⟶ 5,307:
(* (catalan i) (catalan (- m i 1))))))
(map catalan (range 1 15))</langsyntaxhighlight>
{{out}}
<pre>
'(1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440)
</pre>
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2015.12}}
The recursive formulas are easily written into a constant array, either:
 
<syntaxhighlight lang="raku" line>constant Catalan = 1, { [+] @_ Z* @_.reverse } ... *;</syntaxhighlight>
 
or
 
<syntaxhighlight lang="raku" line>constant Catalan = 1, |[\*] (2, 6 ... *) Z/ 2 .. *;
 
 
# In both cases, the sixteen first values can be seen with:
.say for Catalan[^16];</syntaxhighlight>
{{out}}
<pre>1
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440</pre>
=={{header|REXX}}==
===version 1===
Line 3,329 ⟶ 5,351:
has been rearranged to:
:::::::: <big> (n+1) * [fact(n) **2] </big>
<langsyntaxhighlight lang="rexx">/*REXX program calculates and displays Catalan numbers using four different methods. */
parse arg LO HI . /*obtain optional arguments from the CL*/
if LO=='' | LO=="," then do; HI=15; LO=0; end /*No args? Then use a range of 0 ──► 15*/
Line 3,351 ⟶ 5,373:
Cat2: procedure expose c.; parse arg n; $=0; if c.n\==. then return c.n
do k=0 for n; $=$ + Cat2(k) * Cat2(n-k-1); end
c.n=$; return $ /*use a memoization technique.*/</langsyntaxhighlight>
'''output''' &nbsp; when using the input of: &nbsp; <tt> 0 &nbsp; 16 </tt>
<pre>
Line 3,384 ⟶ 5,406:
 
::* For Catalan numbers &nbsp; 1 ──► 200:
::::* method &nbsp; '''1A''' &nbsp; is about &nbsp; '''50''' times slower than method &nbsp; '''3'''
::::* method &nbsp; '''1B''' &nbsp; is about '''100''' times slower than method &nbsp; '''3'''
::::* method &nbsp; '''2''' &nbsp; &nbsp; is about &nbsp; '''85''' times slower than method &nbsp; '''3'''
 
::* For Catalan numbers &nbsp; 1 ──► 300:
::::* method &nbsp; '''1A''' &nbsp; is about '''100''' times slower than method &nbsp; '''3'''
::::* method &nbsp; '''1B''' &nbsp; is about '''200''' times slower than method &nbsp; '''3'''
::::* method &nbsp; '''2''' &nbsp; &nbsp; is about '''200''' times slower than method &nbsp; '''3'''
Method &nbsp; '''3''' &nbsp; is really quite fast; &nbsp; even in the thousands range, computation time is still quite reasonable.
 
===version 2===
Implements the 3 methods shown in the task description
<langsyntaxhighlight lang="rexx">/* REXX ---------------------------------------------------------------
* 01.07.2014 Walter Pachl
*--------------------------------------------------------------------*/
Line 3,446 ⟶ 5,468:
f=f*i
End
Return f</langsyntaxhighlight>
{{out}}
<pre> n c1.n c2.n c3.n
Line 3,471 ⟶ 5,493:
20 6564120420 6564120420 6564120420
n c1.n c2.n c3.n</pre>
 
=={{header|Ring}}==
<langsyntaxhighlight lang="ring">
for n = 1 to 15
see catalan(n) + nl
Line 3,482 ⟶ 5,503:
cat = 2 * (2 * n - 1) * catalan(n - 1) / (n + 1)
return cat
</syntaxhighlight>
</lang>
Output:
<pre>
Line 3,501 ⟶ 5,522:
9694845
</pre>
=={{header|RPL}}==
 
{{works with|Halcyon Calc|4.2.7}}
=={{header|Ring}}==
{| class="wikitable"
<lang ring>
! Code
for n = 1 to 15
! Comments
see catalan(n) + nl
|-
next
|
≪
'''IFERR''' R→B '''THEN END'''
'''IF''' DUP #1 ≠
'''THEN'''
DUP 2 * 1 - 2 * OVER 1 - →CAT * SWAP 1 + /
'''END'''
≫ ''''→CAT'''' STO
|
''( n -- C(n) )''
Ignore the conversion error if n is already a binary integer
C(1) = 1
Divide by (n+1) at the end to stay in the integer world
func catalan n
if n = 0 return 1 ok
cat = 2 * (2 * n - 1) * catalan(n - 1) / (n + 1)
|}
return cat
To speed up execution, additions can be preferred to multiplications by replacing <code>2 *</code> with <code>DUP +</code>.
</lang>
The following piece of code will deliver what is required:
Output:
≪ 1 { } '''DO''' OVER →CAT B→R + SWAP 1 + SWAP '''UNTIL''' OVER 15 > '''END''' ≫ EVAL
{{out}}
<pre>
1: { 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 }
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440
9694845
</pre>
 
=={{header|Ruby}}==
<syntaxhighlight lang="ruby">def factorial(n)
{{libheader|RubyGems}}
<lang ruby>def factorial(n)
(1..n).reduce(1, :*)
end
Line 3,548 ⟶ 5,568:
def catalan_rec1(n)
return 1 if n == 0
(0...n).inject(0) sum{|sum, i| sum + catalan_rec1(i) * catalan_rec1(n-1-i)}
end
 
Line 3,572 ⟶ 5,592:
 
puts "\n direct rec1 rec2"
16.times {|n| puts "%2d :%9d%9d%9d" % [n, catalan_direct(n), catalan_rec1(n), catalan_rec2(n)]}</langsyntaxhighlight>
The output shows the dramatic difference memoizing makes.
<pre>
Line 3,599 ⟶ 5,619:
15 : 9694845 9694845 9694845
</pre>
 
=={{header|Run BASIC}}==
<lang Runbasic>FOR i = 1 TO 15
PRINT i;" ";catalan(i)
NEXT
FUNCTION catalan(n)
catalan = 1
if n <> 0 then catalan = ((2 * ((2 * n) - 1)) / (n + 1)) * catalan(n - 1)
END FUNCTION</lang>
<pre>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</pre>
 
=={{header|Rust}}==
<langsyntaxhighlight lang="rust">fn c_n(n: u64) -> u64 {
match n {
0 => 1,
Line 3,637 ⟶ 5,632:
println!("c_n({}) = {}", i, c_n(i));
}
}</langsyntaxhighlight>
 
{{out}}
Line 3,656 ⟶ 5,651:
c(14) = 2674440
c(15) = 9694845</pre>
 
=={{header|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))
 
Simple and straightforward. Noticeably out of steam without memoizing at about 5000.
def main(args: Array[String]) {
<syntaxhighlight lang="scala">
for (n <- 1 to 15) {
object CatalanNumbers {
def main(args: Array[String]): Unit = {
for (n <- 0 to 15) {
println("catalan(" + n + ") = " + catalan(n))
}
}
 
}</lang>
def catalan(n: BigInt): BigInt = factorial(2 * n) / (factorial(n + 1) * factorial(n))
 
def factorial(n: BigInt): BigInt = BigInt(1).to(n).foldLeft(BigInt(1))(_ * _)
}
</syntaxhighlight>
{{out}}
<pre>
catalan(0) = 1
catalan(1) = 1
catalan(2) = 2
Line 3,685 ⟶ 5,684:
catalan(13) = 742900
catalan(14) = 2674440
catalan(15) = 9694845</pre>
</pre>
 
=={{header|Scheme}}==
Tail recursive implementation.
<langsyntaxhighlight lang="scheme">(define (catalan m)
(let loop ((c 1)(n 0))
(if (not (eqv? n m))
Line 3,696 ⟶ 5,695:
(loop (* (/ (* 2 (- (* 2 (+ n 1)) 1)) (+ (+ n 1) 1)) c) (+ n 1) )))))
 
(catalan 15)</langsyntaxhighlight>
{{out}}
<pre>0: 1
Line 3,713 ⟶ 5,712:
13: 742900
14: 2674440</pre>
 
=={{header|Seed7}}==
<langsyntaxhighlight lang="seed7">$ include "seed7_05.s7i";
include "bigint.s7i";
 
Line 3,725 ⟶ 5,723:
writeln((2_ * n) ! n div succ(n));
end for;
end func;</langsyntaxhighlight>
{{out}}
<pre>
Line 3,745 ⟶ 5,743:
9694845
</pre>
 
=={{header|Sidef}}==
<langsyntaxhighlight lang="ruby">func f(i) { i==0 ? 1 : (i * f(i-1)) }
func c(n) { f(2*n) / f(n) / f(n+1) }</langsyntaxhighlight>
With memoization:
<langsyntaxhighlight lang="ruby">func c(n) is cached {
n == 0 ? 1 : (c(n-1) * (4 * n - 2) / (n + 1))
}</langsyntaxhighlight>
 
Calling the function:
<langsyntaxhighlight lang="ruby">15.times { |i|
say "#{i}\t#{c(i)}"
}</langsyntaxhighlight>
{{out}}
<pre>
Line 3,776 ⟶ 5,773:
14 2674440
</pre>
 
=={{header|smart BASIC}}==
-- [http://rosettacode.org/wiki/User:Sarossell Scott A. Rossell, 12-29-16]
 
<lang qbasic>PRINT "Recursive:"!PRINT
FOR n = 0 TO 15
PRINT n,"#######":catrec(n)
NEXT n
PRINT!PRINT
 
PRINT "Non-recursive:"!PRINT
FOR n = 0 TO 15
PRINT n,"#######":catnonrec(n)
NEXT n
 
END
DEF catrec(x)
IF x = 0 THEN
temp = 1
ELSE
n = x
temp = ((2*((2*n)-1))/(n+1))*catrec(n-1)
END IF
catrec = temp
END DEF
 
DEF catnonrec(x)
temp = 1
FOR n = 1 TO x
temp = (2*((2*n)-1))/(n+1)*temp
NEXT n
catnonrec = temp
END DEF</lang>
 
=={{header|Standard ML}}==
<langsyntaxhighlight lang="sml">(*
* val catalan : int -> int
* Returns the nth Catalan number.
Line 3,843 ⟶ 5,806:
* 2674440
* 9694845
*)</langsyntaxhighlight>
=={{header|Stata}}==
 
<syntaxhighlight lang="stata">clear
set obs 15
gen catalan=1 in 1
replace catalan=catalan[_n-1]*2*(2*_n-3)/_n in 2/l
list, noobs noh</syntaxhighlight>
 
'''Output'''
 
<pre> +---------+
| 1 |
| 1 |
| 2 |
| 5 |
| 14 |
|---------|
| 42 |
| 132 |
| 429 |
| 1430 |
| 4862 |
|---------|
| 16796 |
| 58786 |
| 208012 |
| 742900 |
| 2674440 |
+---------+</pre>
=={{header|Swift}}==
 
{{trans|Rust}}
<syntaxhighlight lang="swift">func catalan(_ n: Int) -> Int {
switch n {
case 0:
return 1
case _:
return catalan(n - 1) * 2 * (2 * n - 1) / (n + 1)
}
}
 
for i in 1..<16 {
print("catalan(\(i)) => \(catalan(i))")
}
</syntaxhighlight>
 
{{out}}
<pre>
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
</pre>
=={{header|Tcl}}==
<langsyntaxhighlight lang="tcl">package require Tcl 8.5
 
# Memoization wrapper
Line 3,864 ⟶ 5,890:
$n == 0 ? 1 : 2 * (2*$n - 1) * catalan($n - 1) / ($n + 1)
}}
}</langsyntaxhighlight>
Demonstration:
<langsyntaxhighlight lang="tcl">for {set i 0} {$i < 15} {incr i} {
puts "C_$i = [expr {catalan($i)}]"
}</langsyntaxhighlight>
{{out}}
<pre>
Line 3,896 ⟶ 5,922:
</pre>
 
== {{header|TI-83 BASICTypeScript}} ==
{{trans|GW-BASIC}}
This problem is perfectly suited for a TI calculator.
<syntaxhighlight lang="javascript">
<lang TI-83 BASIC>:For(I,1,15
// Catalan numbers
:Disp (2I)!/((I+1)!I!
var c: number[] = [1];
:End</lang>
console.log(`${0}\t${c[0]}`);
for (n = 0; n < 15; n++) {
c[n + 1] = 0;
for (i = 0; i <= n; i++)
c[n + 1] = c[n + 1] + c[i] * c[n - i];
console.log(`${n + 1}\t${c[n + 1]}`);
}
</syntaxhighlight>
{{out}}
<pre> 1
0 1
2
1 1
4
2 2
14
3 5
42
4 14
132
5 42
429
6 132
1430
7 429
4862
8 1430
16796
9 4862
58786
10 16796
208012
11 58786
742900
12 208012
2674440
13 742900
9694845
14 2674440
Done</pre>
15 9694845
</pre>
 
=={{header|Ursala}}==
<langsyntaxhighlight lang="ursala">#import std
#import nat
 
Line 3,927 ⟶ 5,963:
#cast %nL
 
t = catalan* iota 16</langsyntaxhighlight>
{{out}}
<pre><
Line 3,946 ⟶ 5,982:
2674440,
9694845></pre>
=={{header|Vala}}==
<syntaxhighlight lang="vala">namespace CatalanNumbers {
public class CatalanNumberGenerator {
private static double factorial(double n) {
if (n == 0)
return 1;
return n * factorial(n - 1);
}
public double first_method(double n) {
const double top_multiplier = 2;
return factorial(top_multiplier * n) / (factorial(n + 1) * factorial(n));
}
 
public double second_method(double n) {
=={{header|VBA}}==
if (n == 0) {
<lang vb>Public Sub Catalan1(n As Integer)
return 1;
'Computes the first n Catalan numbers according to the first recursion given
}
Dim Cat() As Long
Dim double sum As= Long0;
double i = 0;
for (; i <= (n - 1); i++) {
sum += second_method(i) * second_method((n - 1) - i);
}
return sum;
}
 
public double third_method(double n) {
ReDim Cat(n)
if (n == 0) {
Cat(0) = 1
For i = 0 To n - return 1;
sum = 0 }
return ((2 * (2 * n - 1)) / (n + 1)) * third_method(n - 1);
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
 
void main() {
Public Sub Catalan2(n As Integer)
CatalanNumberGenerator generator = new CatalanNumberGenerator();
'Computes the first n Catalan numbers according to the second recursion given
DateTime initial_time;
Dim Cat() As Long
DateTime final_time;
TimeSpan ts;
 
stdout.printf("Direct Method\n");
stdout.printf(" n%9s\n", "C_n");
stdout.printf("............\n");
initial_time = new DateTime.now();
for (double i = 0; i <= 15; i++) {
stdout.printf("%2s %8s\n", i.to_string(), Math.ceil(generator.first_method(i)).to_string());
}
final_time = new DateTime.now();
ts = final_time.difference(initial_time);
stdout.printf("............\n");
stdout.printf("Time Elapsed: %s μs\n", ts.to_string());
 
stdout.printf("\nRecursive Method 1\n");
ReDim Cat(n)
stdout.printf(" n%9s\n", "C_n");
Cat(0) = 1
stdout.printf("............\n");
For i = 1 To n
initial_time = new DateTime.now();
Cat(i) = 2 * Cat(i - 1) * (2 * i - 1) / (i + 1)
for (double i = 0; i <= 15; i++) {
Next i
stdout.printf("%2s %8s\n", i.to_string(), Math.ceil(generator.second_method(i)).to_string());
Debug.Print
For i = 0 To n}
final_time = new DateTime.now();
Debug.Print i, Cat(i)
ts = final_time.difference(initial_time);
Next
stdout.printf("............\n");
End Sub</lang>
stdout.printf("Time Elapsed: %s μs\n", ts.to_string());
{{out|Result}}
 
stdout.printf("\nRecursive Method 2\n");
stdout.printf(" n%9s\n", "C_n");
stdout.printf("............\n");
initial_time = new DateTime.now();
for (double i = 0; i <= 15; i++) {
stdout.printf("%2s %8s\n", i.to_string(), Math.ceil(generator.third_method(i)).to_string());
}
final_time = new DateTime.now();
ts = final_time.difference(initial_time);
stdout.printf("............\n");
stdout.printf("Time Elapsed: %s μs\n", ts.to_string());
 
}
}</syntaxhighlight>
{{out}}
<pre>
Direct Method
Catalan1 15
n C_n
............
0 1
1 1
2 2
3 5
4 14
5 42
6 132
7 429
8 1430
9 4862
10 16796
11 58786
12 208012
13 742900
14 2674440
15 9694845
............
Time Elapsed: 132 μs
 
Recursive Method 1
n C_n
............
0 1
1 1
2 2
3 5
4 14
5 42
6 132
7 429
8 1430
9 4862
10 16796
11 58786
12 208012
13 742900
14 2674440
15 9694845
............
Time Elapsed: 130430 μs
 
Recursive Method 2
0 1
1n 1 C_n
............
2 2
30 5 1
41 14 1
52 42 2
63 132 5
74 429 14
85 1430 42
96 4862 132
107 16796 429
118 58786 1430
129 208012 4862
10 16796
13 742900
11 58786
14 2674440
12 208012
15 9694845
13 742900
14 2674440
15 9694845
............
Time Elapsed: 76 μs
</pre>
(Expect same result with "Catalan2 15")
 
=={{header|VBScriptV (Vlang)}}==
{{trans|Go}}
<lang vb>
<syntaxhighlight lang="v (vlang)">import math.big
Function catalan(n)
catalan = factorial(2*n)/(factorial(n+1)*factorial(n))
End Function
 
fn main() {
Function factorial(n)
mut b:= big.zero_int
If n = 0 Then
for n := i64(0); n < 15; n++ {
Factorial = 1
b = big.integer_from_i64(n)
Else
b = (b*big.two_int).factorial()/(b.factorial()*(b*big.two_int-b).factorial())
For i = n To 1 Step -1
println(b/big.integer_from_i64(n+1))
If i = n Then
}
factorial = n
}</syntaxhighlight>
Else
{{out}}
factorial = factorial * i
End If
Next
End If
End Function
 
'Find the first 15 Catalan numbers.
For j = 1 To 15
WScript.StdOut.Write j & " = " & catalan(j)
WScript.StdOut.WriteLine
Next
</lang>
 
{{Out}}
<pre>
1
1 = 1
1
2 = 2
2
3 = 5
5
4 = 14
14
5 = 42
42
6 = 132
132
7 = 429
429
8 = 1430
1430
9 = 4862
4862
10 = 16796
16796
11 = 58786
58786
12 = 208012
208012
13 = 742900
742900
14 = 2674440
2674440
15 = 9694845
</pre>
 
=={{header|Wortel}}==
<langsyntaxhighlight lang="wortel">; the following number expression calculcates the nth Catalan number
#~ddiFSFmSoFSn
; which stands for: dup dup inc fac swap fac mult swap double fac swap divide
; to get the first 15 Catalan numbers we map this function over a list from 0 to 15
!*#~ddiFSFmSoFSn @til 15
; returns [1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674439.9999999995]</langsyntaxhighlight>
=={{header|Wren}}==
{{libheader|Wren-fmt}}
{{libheader|Wren-math}}
<syntaxhighlight lang="wren">import "./fmt" for Fmt
import "./math" for Int
var catalan = Fn.new { |n|
if (n < 0) Fiber.abort("Argument must be a non-negative integer")
var prod = 1
var i = n + 2
while (i <= n * 2) {
prod = prod * i
i = i + 1
}
return prod / Int.factorial(n)
}
 
var catalanRec
catalanRec = Fn.new { |n| (n != 0) ? 2 * (2 * n - 1) * catalanRec.call(n - 1) / (n + 1) : 1 }
 
System.print(" n Catalan number")
System.print("------------------")
for (i in 0..15) System.print("%(Fmt.d(2, i)) %(catalan.call(i))")
System.print("\nand again using a recursive function:\n")
for (i in 0..15) System.print("%(Fmt.d(2, i)) %(catalanRec.call(i))")</syntaxhighlight>
 
{{out}}
<pre>
n Catalan number
------------------
0 1
1 1
2 2
3 5
4 14
5 42
6 132
7 429
8 1430
9 4862
10 16796
11 58786
12 208012
13 742900
14 2674440
15 9694845
 
and again using a recursive function:
 
0 1
1 1
2 2
3 5
4 14
5 42
6 132
7 429
8 1430
9 4862
10 16796
11 58786
12 208012
13 742900
14 2674440
15 9694845
</pre>
 
=={{header|XLISP}}==
<syntaxhighlight lang="lisp">(defun catalan (n)
(if (= n 0)
1
(* (/ (* 2 (- (* 2 n) 1)) (+ n 1)) (catalan (- n 1))) ) )
 
(defun range (x y)
(cons x
(if (< x y)
(range (+ x 1) y) ) ) )
 
(print (mapcar catalan (range 0 14)))</syntaxhighlight>
{{out}}
<pre>(1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440)</pre>
=={{header|XPL0}}==
<langsyntaxhighlight XPL0lang="xpl0">code CrLf=9, IntOut=11;
int C, N;
[C:= 1;
Line 4,068 ⟶ 6,257:
IntOut(0, C); CrLf(0);
];
]</langsyntaxhighlight>
{{out}}
<pre>
Line 4,090 ⟶ 6,279:
=={{header|zkl}}==
Uses GMP to calculate big factorials.
<langsyntaxhighlight lang="zkl">var BN=Import("zklBigNum");
fcn catalan(n){
BN(2*n).factorial() / BN(n+1).factorial() / BN(n).factorial();
Line 4,098 ⟶ 6,287:
println("%2d --> %,d".fmt(n, catalan(n)));
}
println("%2d --> %,d".fmt(100, catalan(100)));</langsyntaxhighlight>
And an iterative solution at works up to the limit of 64 bit ints (n=33). Would be 35 but need to avoid factional intermediate results.
<langsyntaxhighlight lang="zkl">fcn catalan(n){ (1).reduce(n,fcn(p,n){ 2*(2*n-1)*p/(n+1) },1) }</langsyntaxhighlight>
{{out}}
<pre>
Line 4,121 ⟶ 6,310:
100 --> 896,519,947,090,131,496,687,170,070,074,100,632,420,837,521,538,745,909,320
</pre>
 
=={{header|ZX Spectrum Basic}}==
{{trans|C}}
<langsyntaxhighlight lang="zxbasic">10 FOR i=0 TO 15
20 LET n=i: LET m=2*n
30 LET r=1: LET d=m-n
Line 4,136 ⟶ 6,324:
110 STOP
120 DEF FN m(a,b)=a-INT (a/b)*b: REM Modulus function
</syntaxhighlight>
</lang>
Langurmonkey
1,006

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/172250...364131"