Catalan numbers/Pascal's triangle: Difference between revisions

<!-- '''http://milan.milanovic.org/math/english/fibo/fibo4.html is broken. -->

* &nbsp; [http://mathworld.wolfram.com/CatalansTriangle.html Catalan's Triangle] for a Number Triangle that generates Catalan Numbers using only addition.

 

;Related Tasks:

[[Pascal's triangle]]

<br><br>

=={{header|11l}}==

{{trans|Python}}

V t = [0] * (n + 2)

t[1] = 1

L(j) (i + 1 .< 1).step(-1)

t[j] += t[j - 1]

{{out}}

<pre>

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

</pre>

=={{header|360 Assembly}}==

For maximum compatibility, this program uses only the basic instruction set.

USING CATALAN,R13,R12

SAVEAREA B STM-SAVEAREA(R15)

WTOBUF DC CL80' '

YREGS

{{out}}

<pre style="height:20ex">00000001

02674440

09694845</pre>

 

=={{header|Ada}}==

 

Uses package Pascal from the Pascal triangle solution[[http://rosettacode.org/wiki/Pascal%27s_triangle#Ada]]

 

 

procedure Catalan is

Ada.Text_IO.Put(Integer'Image(Row(I+1)-Row(I+2)));

end loop;

 

{{out}}

 

<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre>

=={{header|ALGOL 68}}==

{{trans|C++}}

[ 0 : n + 1 ]INT t;

t[0] := 0;

FOR j FROM i+1 BY -1 TO 2 DO t[j] := t[j] + t[j-1] OD;

print( ( whole( t[i+1] - t[i], 0 ), " " ) )

{{out}}

<pre>

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

</pre>

=={{header|ALGOL W}}==

% print the first 15 Catalan numbers from Pascal's triangle %

integer n;

end for_c

end

{{out}}

<pre>

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

</pre>

=={{header|APL}}==

⍝ Based heavily on the J solution

CATALAN←{¯1↓↑-/1 ¯1↓¨(⊂⎕IO+0 0)⍉¨0 2⌽¨⊂(⎕IO-⍨⍳N){+\⍣⍺⊢⍵}⍤0 1⊢1⍴⍨N←⍵+2}

{{out}}

<pre>

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

</pre>

 

=={{header|AutoHotkey}}==

{{works with|AutoHotkey_L}}

//

// smgs: 20th Feb, 2014

}

}

{{out|Produces}}

<pre>

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

</pre>

 

=={{header|Batch File}}==

setlocal ENABLEDELAYEDEXPANSION

set n=15

)

)

{{Out}}

<pre style="height:20ex">1

2674440

9694845</pre>

=={{header|C}}==

//This code implements the print of 15 first Catalan's Numbers

//Formula used:

printf("1 ");

 

for (n=2; n<=N; ++n) {

//initializaing for products

return 0;

}

 

{{out}}

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

</pre>

=={{header|C++}}==

//

// Nigel Galloway: June 9th., 2012

}

return 0;

{{out|Produces}}

<pre>

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

</pre>

=={{header|Common Lisp}}==

 

"Return the n-th Catalan number"

(if (<= n 1) 1

 

(dotimes (n 15)

 

{{out}}

2674440

9694845</pre>

=={{header|D}}==

{{trans|C++}}

import std.stdio;

 

write(t[i + 1] - t[i], ' ');

}

{{out}}

<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 </pre>

 

=={{header|EchoLisp}}==

(define dim 100)

(define-syntax-rule (Tidx i j) (+ i (* dim j)))

(remember 'T #(1))

{{out}}

;; take elements on diagonal = Catalan numbers

(for ((i (in-range 0 16))) (write (T (Tidx i i))))

 

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

 

=={{header|Elixir}}==

def numbers(num) do

{result,_} = Enum.reduce(1..num, {[],{0,1}}, fn i,{list,t0} ->

end

 

 

{{out}}

</pre>

=={{header|Erlang}}==

-module(catalin).

-compile(export_all).

main()->

Ans=catl(1,2).

=={{header|ERRE}}==

PROGRAM CATALAN

 

END FOR

END PROGRAM

{{out}}

<pre>

15 9694845

</pre>

let mutable nm=uint64(1)

let mutable dm=uint64(1)

if(i<>15) then

printf ", "

=={{header|Factor}}==

IN: rosetta-code.catalan-pascal

 

[ dup midpoint@ dup 1 + 2array swap nths first2 - ] if

pprint bl

{{out}}

<pre>

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

</pre>

=={{header|FreeBASIC}}==

' compile with: fbc -s console

 

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>The first 15 Catalan numbers are

14: 2674440

15: 9694845</pre>

=={{header|Go}}==

{{trans|C++}}

 

import "fmt"

fmt.Printf("%2d : %d\n", i, t[i+1]-t[i])

}

 

{{out}}

15 : 9694845

</pre>

=={{header|Groovy}}==

{{trans|C}}

class Catalan

{

}

}

{{out}}

<pre>

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

</pre>

=={{header|Haskell}}==

As required by the task this implementation extracts the Catalan numbers from Pascal's triangle, rather

than calculating them directly. Also, note that it (correctly) produces [1, 1] as the first two numbers.

 

-- Pascal's triangle.

main = do

ns <- fmap (map read) getArgs :: IO [Int]

 

{{out}}

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

</pre>

=={{header|Icon}} and {{header|Unicon}}==

 

that aren't used.

 

 

procedure main(A)

limit := (integer(A[1])|15)+1

every write(right(binocoef(i := 2*seq(0)\limit,i/2)-binocoef(i,i/2+1),30))

 

Sample run:

->

</pre>

=={{header|J}}==

 

{{out|Example use}}

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

 

A structured derivation of Catalan follows:

 

( PascalTriangle=. i. ((+/\@]^:[)) #&1 ) 5

1 1 1 1 1

Catalan

=={{header|Java}}==

{{trans|C++}}

public static void main(String[] args) {

int N = 15;

}

}

 

<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre>

=={{header|JavaScript}}==

===ES5===

Iteration

{{trans|C++}}

for (var t = [0, 1], i = 1; i <= n; i++) {

for (var j = i; j > 1; j--) t[j] += t[j - 1];

for (var j = i + 1; j > 1; j--) t[j] += t[j - 1];

document.write(i == 1 ? '' : ', ', t[i + 1] - t[i]);

{{out}}

<pre>

{{Trans|Haskell}}

 

'use strict';

 

 

return tail(catalanSeries(16));

 

{{Out}}

=={{header|jq}}==

The first identity (C(2n,n) - C(2n, n-1)) given in the reference is used in accordance with the task description, but it would of course be more efficient to factor out C(2n,n) and use the expression C(2n,n)/(n+1). See also [[Catalan_numbers#jq]] for other alternatives.

''Warning'': jq uses IEEE 754 64-bit arithmetic,

so the algorithm used here for Catalan numbers loses precision for n > 30 and fails completely for n > 510.

if k > n / 2 then binomial(n; n-k)

else reduce range(1; k+1) as $i (1; . * (n - $i + 1) / $i)

 

# Direct (naive) computation using two numbers in Pascal's triangle:

 

'''Example''':

(range(0;16), 30, 31, 510, 511) | [., catalan_by_pascal]

{{Out}}

[0,0]

[1,1]

[31,14544636039226880]

[510,5.491717746183512e+302]

=={{header|Julia}}==

{{trans|Matlab}}

 

function pascal(n::Int)

end

 

 

{{out}}

<pre>catalan_num(15) = [1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]</pre>

=={{header|Kotlin}}==

 

import java.math.BigInteger

val n = 15

catalanFromPascal(n * 2)

 

{{out}}

15 : 9694845

</pre>

=={{header|Lua}}==

For each line of odd-numbered length from Pascal's triangle, print the middle number minus the one immediately to its right.

This solution is heavily based on the Lua code to generate Pascal's triangle from the page for that task.

local ret = {}

t[0], t[#t + 1] = 0, 0

end

 

{{out}}

<pre>1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440</pre>

We use & to pass by reference, here anarray, to sub, but because a sub can see anything in module we can change array name inside sub to same as triangle and we can remove arguments (including size).

 

Module CatalanNumbers {

Def Integer count, t_row, size=31

}

CatalanNumbers

{{out}}

<pre>

15: 9694845

</pre>

 

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

This builds the entire Pascal triangle that's needed and holds it in memory. Very inefficienct, but seems to be what is asked in the problem.

output = ConstantArray[1, Length[lastrow] + 1];

Do[

]

(* testing *)

{{out}}

<pre>{1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845}</pre>

=={{header|MATLAB}} / {{header|Octave}}==

 

p = pascal(n + 2);

{{Out}}

<pre>ans =

2674440

9694845</pre>

 

=={{header|Nim}}==

{{trans|Python}}

var t = newSeq[int](n + 2)

 

t[i+1] = t[i]

for j in countdown(i+1, 1): t[j] += t[j-1]

{{Out}}

<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 </pre>

=={{header|OCaml}}==

let catalan : int ref = ref 0 in

Printf.printf "%d ," 1 ;

print_int (!catalan); print_string "," ;

done;;

{{out}}

<pre>

1 ,2,5,14,42,132,429,1430,4862

</pre>

=={{header|Oforth}}==

 

 

: pascal( n -- [] )

 

: catalan( n -- m )

 

{{out}}

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

</pre>

=={{header|PARI/GP}}==

{{out}}

<pre>%1 = [1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]</pre>

=={{header|Pascal}}==

tElement = Uint64;

var

For i := 1 to L do

Writeln(i:3,Catalan[i]:20);

<pre> 1 1

2 2

 

</pre>

=={{header|Perl}}==

{{trans|C++}}

my @t = (0, 1);

for(my $i = 1; $i <= N; $i++) {

for(my $j = $i+1; $j>1; $j--) { $t[$j] += $t[$j-1] }

print $t[$i+1] - $t[$i], " ";

{{out}}

<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre>

After the 28th Catalan number, this overflows 64-bit integers. We could add <tt>use bigint;</tt> <tt>use Math::GMP ":constant";</tt> to make it work, albeit not at a fast pace. However we can use a module to do it much faster:

{{libheader|ntheory}}

 

The <tt>Math::Pari</tt> module also has a binomial, but isn't as fast and overflows its stack after 3400.

=={{header|Phix}}==

Calculates the minimum pascal triangle in minimum memory. Inspired by the comments in, but not the code of the FreeBasic example

{{out}}

<pre>

</pre>

Explanatory comments to accompany the above

--' 1 1 1 1 1 1

--' 1 2 3 4 5 6

-- 10 15 21

-- 35 56

 

{{out}}

<pre>

</pre>

=={{header|PicoLisp}}==

(let f

'((N)

(bino (* 2 N) N)

(bino (* 2 N) (inc N)) ) ) )

=={{header|PureBasic}}==

{{trans|C}}

Declare catalan()

 

Print(Str(cat)+" ")

Next

{{out}}

<pre>

1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre>

=={{header|Python}}==

{{trans|C++}}

>>> t = [0] * (n + 2)

>>> t[1] = 1

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

 

{{Works with|Python|2.7}}

nm = dm = 1

for k in range(2, n+1):

print [catalan_number(n) for n in range(1, 16)]

 

=={{header|Racket}}==

#lang racket

 

;; -> '(1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900

;; 2674440 9694845)

 

=={{header|REXX}}==

===explicit subscripts===

All of the REXX program examples can handle arbitrary large numbers.

parse arg N . /*Obtain the optional argument from CL.*/

if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/

@.ip=@.i; do k=ip by -1 for N; km=k-1; @.k=@.k+@.km; end /*k*/

say @.ip - @.i /*display the Ith Catalan number. */

'''output''' &nbsp; when using the default input:

<pre>

 

===implicit subscripts===

parse arg N . /*Obtain the optional argument from CL.*/

if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/

exit /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

'''output''' &nbsp; is the same as the 1^st version.

 

===using binomial coefficients===

parse arg N . /*Obtain the optional argument from CL.*/

if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

comb: procedure; parse arg x,y; if x=y then return 1; if y>x then return 0

'''output''' &nbsp; is the same as the 1^st version.

 

===binomial coefficients, memoized===

This REXX version uses memoization for the calculation of factorials.

parse arg N . /*Obtain the optional argument from CL.*/

if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

comb: procedure expose !.; parse arg x,y; if x=y then return 1; if y>x then return 0

'''output''' &nbsp; is the same as the 1^st version. <br><br>

=={{header|Ring}}==

n=15

cat = list(n+2)

see "" + (cat[i+1]-cat[i]) + " "

next

Output:

<pre>

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

</pre>

 

=={{header|Ruby}}==

t = [0, 1] #grows as needed

(1..num).map do |i|

end

 

{{out}}

<pre>

 

=={{header|Run BASIC}}==

dim t(n+2)

t(1) = 1

for j = i+1 to 1 step -1: t(j) = t(j) + t(j-1 : next j

print t(i+1) - t(i);" ";

{{out}}

<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 </pre>

=={{header|Rust}}==

 

fn main()

}

}

{{out}}

<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 </pre>

=={{header|Scala}}==

if (n <= 1) 1

else (0 until n).map(i => catalan(i) * catalan(n - i - 1)).sum

 

{{Out}}See it in running in your browser by [https://scastie.scala-lang.org/2ybpRZxCTOyrx3mIy8yIDw Scastie (JVM)].

=={{header|Scilab}}==

t=zeros(1,n+2)

t(1)=1

end

disp(t(i+1)-t(i))

{{out}}

<pre style="height:20ex"> 1.

2674440.

9694845. </pre>

=={{header|Seed7}}==

 

const proc: main is func

end for;

writeln;

 

{{out}}

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

</pre>

=={{header|Sidef}}==

{{trans|Ruby}}

var t = [0, 1]

(1..num).map { |i|

}

 

{{out}}

<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre>

=={{header|smart BASIC}}==

x = 15

DIM t(x+2)

NEXT m

PRINT n,"#######":t(n+1) - t(n)

=={{header|Tcl}}==

set result {}

array set t {0 0 1 1}

}

 

{{out}}

<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre>

=={{header|TI-83 BASIC}}==

15→N

seq(0,I,1,N+2)→L1

End

Disp L1(I+1)-L1(I)

{{out}}

<pre> 1

9694845

Done </pre>

 

=={{header|VBScript}}==

To run in console mode with cscript.

if Wscript.arguments.count=1 then

n=Wscript.arguments.item(0)

next 'j

Wscript.echo t(i+1)-t(i)

=={{header|Visual Basic}}==

{{trans|Rexx}}

{{works with|Visual Basic|VB6 Standard}}

Sub catalan()

Const n = 15

Next i

End Sub 'catalan

{{Out}}

<pre style="height:20ex">

2674440

9694845

</pre>

 

=={{header|zkl}}==

{{trans|PARI/GP}} using binomial coefficients.

{{out}}

<pre>

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

</pre>

=={{header|ZX Spectrum Basic}}==

{{trans|C++}}

20 DIM t(N+2)

30 LET t(2)=1

70 FOR j=i+1 TO 2 STEP -1: LET t(j)=t(j)+t(j-1): NEXT j

80 PRINT t(i+1)-t(i);" ";