Catalan numbers/Pascal's triangle: Difference between revisions

Content added Content deleted

Inline

Revision as of 18:15, 13 November 2014

The task is to print out the first 15 Catalan numbers by extracting them from Pascal's triangle, see Catalan Numbers and the Pascal Triangle. This enables calculation of Catalan Numbers using only addition and subtraction. See Catalan's Triangle for a Number Triangle that generates Catalan Numbers using only addition.

Related Tasks: Pascal's triangle

360 Assembly

For maximum compatibility, this program uses only the basic instruction set. <lang 360asm>CATALAN CSECT

        USING  CATALAN,R13,R12

SAVEAREA B STM-SAVEAREA(R15)

        DC     17F'0'
        DC     CL8'CATALAN'

STM STM R14,R12,12(R13)

        ST     R13,4(R15)
        ST     R15,8(R13)
        LR     R13,R15
        LA     R12,4095(R13)
        LA     R12,1(R12)

---- CODE

        LA     R0,1
        ST     R0,T            t(1)=1
        LA     R4,0            ix:i=1
        LA     R6,1            by 1
        LH     R7,N            to n

LOOPI BXH R4,R6,ENDLOOPI loop i

        LR     R5,R4           ix:j=i+1
        LA     R5,2(R5)        i+2
        LA     R8,0
        BCTR   R8,0            by -1 
        LA     R9,1            to 2

LOOP1J BXLE R5,R8,ENLOOP1J loop j

        LR     R10,R5          j
        BCTR   R10,0
        SLA    R10,2
        L      R2,T(R10)       r2=t(j)  
        LR     R1,R10          j
        SH     R1,=H'4'
        L      R3,T(R1)        r3=t(j-1)
        AR     R2,R3           r2=r2+r3 
        ST     R2,T(R10)       t(j)=t(j)+t(j-1)
        B      LOOP1J

ENLOOP1J EQU *

        LR     R1,R4           i
        BCTR   R1,0
        SLA    R1,2
        L      R3,T(R1)        t(i)
        LA     R1,4(R1)
        ST     R3,T(R1)        t(i+1)
        LR     R5,R4           ix:j=i+2
        LA     R5,3(R5)        i+3
        LA     R8,0
        BCTR   R8,0            by -1 
        LA     R9,1            to 2

LOOP2J BXLE R5,R8,ENLOOP2J loop j

        LR     R10,R5          j
        BCTR   R10,0
        SLA    R10,2
        L      R2,T(R10)       r2=t(j)  
        LR     R1,R10          j
        SH     R1,=H'4'
        L      R3,T(R1)        r3=t(j-1)
        AR     R2,R3           r2=r2+r3 
        ST     R2,T(R10)       t(j)=t(j)+t(j-1)
        B      LOOP2J

ENLOOP2J EQU *

        LR     R1,R4           i
        BCTR   R1,0
        SLA    R1,2
        L      R2,T(R1)        t(i)
        LA     R1,4(R1)
        L      R3,T(R1)        t(i+1)
        SR     R3,R2
        CVD    R3,P            
        UNPK   Z,P
        MVC    C,Z
        OI     C+L'C-1,X'F0'
        MVC    WTOBUF(8),C+8
        WTO    MF=(E,WTOMSG)		  
        B      LOOPI

ENDLOOPI EQU *

---- END CODE

        CNOP   0,4
        L      R13,4(0,R13)
        LM     R14,R12,12(R13)
        XR     R15,R15
        BR     R14

---- DATA

N DC H'15' T DC 17F'0' P DS PL8 Z DS ZL16 C DS CL16 WTOMSG DS 0F

        DC     H'80'
        DC     H'0'

WTOBUF DC CL80' '

        YREGS  
        END</lang>

Output:

Ada

Uses package Pascal from the Pascal triangle solution[[1]]

<lang Ada>with Ada.Text_IO, Pascal;

procedure Catalan is

  Last: Positive := 15;   
  Row: Pascal.Row := Pascal.First_Row(2*Last+1);

begin

  for I in 1 .. Last loop
     Row := Pascal.Next_Row(Row);
     Row := Pascal.Next_Row(Row);
     Ada.Text_IO.Put(Integer'Image(Row(I+1)-Row(I+2)));
  end loop;

end Catalan;</lang>

Output:

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

AutoHotkey

Works with: AutoHotkey_L

<lang AutoHotkey>/* Generate Catalan Numbers // // smgs: 20th Feb, 2014

/

Array := [], Array[2,1] := Array[2,2] := 1 ; Array inititated and 2nd row of pascal's triangle assigned INI := 3 ; starts with calculating the 3rd row and as such the value Loop, 31 ; every odd row is taken for calculating catalan number as such to obtain 15 we need 2n+1 { if ( A_index > 2 ) { Loop, % A_INDEX { old := ini-1, index := A_index, index_1 := A_index + 1 Array[ini, index_1] := Array[old, index] + Array[old, index_1] Array[ini, 1] := Array[ini, ini] := 1 line .= Array[ini, A_index] " " } ;~ MsgBox % line ; gives rows of pascal's triangle ; calculating every odd row starting from 1st so as to obtain catalan's numbers if ( mod(ini,2) != 0) { StringSplit, res, line, %A_Space% ans := res0//2, ans_1 := ans++ result := result . res%ans_1% - res%ans% " " } line := ini++ } } MsgBox % result</lang>

Produces:

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

Batch File

<lang dos> @echo off setlocal ENABLEDELAYEDEXPANSION rem t(0:n+1) set n=15 set /A nn=n+1 for /L %%i in (0,1,%nn%) do set t.%%i=0 set t.1=1 for /L %%i in (1,1,%n%) do (

   set /A ip=%%i+1
   for /L %%j in (%%i,-1,1) do (
       set /A jm=%%j-1

set /A t.%%j=t.%%j+t.!jm! )

   set /A t.!ip!=t.%%i	  
   for /L %%j in (!ip!,-1,1) do (
       set /A jm=%%j-1

set /A t.%%j=t.%%j+t.!jm! )

   set /A ci=t.!ip!-t.%%i

rem echo %%i !ci! echo !ci!

) pause

</lang>

Output:

C++

<lang cpp>// Generate Catalan Numbers // // Nigel Galloway: June 9th., 2012 //

include <iostream>

int main() {

 const int N = 15;
 int t[N+2] = {0,1};
 for(int i = 1; i<=N; i++){
   for(int j = i; j>1; j--) t[j] = t[j] + t[j-1];
   t[i+1] = t[i];
   for(int j = i+1; j>1; j--) t[j] = t[j] + t[j-1];
   std::cout << t[i+1] - t[i] << " ";
 }
 return 0;

}</lang>

Produces:

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

D

Translation of: C++

<lang d>void main() {

   import std.stdio;

   enum uint N = 15;
   uint[N + 2] t;
   t[1] = 1;

   foreach (immutable i; 1 .. N + 1) {
       foreach_reverse (immutable j; 2 .. i + 1)
           t[j] += t[j - 1];
       t[i + 1] = t[i];
       foreach_reverse (immutable j; 2 .. i + 2)
           t[j] += t[j - 1];
       write(t[i + 1] - t[i], ' ');
   }

}</lang>

Output:

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

Icon and Unicon

The following works in both languages. It avoids computing elements in Pascal's triangle that aren't used.

<lang unicon>link math

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

end</lang>

Sample run:

J

<lang j> Catalan=. }:@:(}.@:((<0 1)&|:) - }:@:((<0 1)&|:@:(2&|.)))@:(i. +/\@]^:[ #&1)@:(2&+)</lang>

Example use:

<lang j> Catalan 15 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845

</lang>

A structured derivation of Catalan follows:

<lang j> o=. @: NB. Composition of verbs (functions)

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

1 1 1 1 1 1 2 3 4 5 1 3 6 10 15 1 4 10 20 35 1 5 15 35 70

  ( MiddleDiagonal=. (<0 1)&|: )               o PascalTriangle 5

1 2 6 20 70

  ( AdjacentLeft=.   MiddleDiagonal o (2&|.) ) o PascalTriangle 5

1 4 15 1 5

  ( Catalan=. }: o (}. o MiddleDiagonal - }: o AdjacentLeft) o PascalTriangle o (2&+) f. ) 5

1 2 5 14 42

  Catalan

}:@:(}.@:((<0 1)&|:) - }:@:((<0 1)&|:@:(2&|.)))@:(i. +/\@]^:[ #&1)@:(2&+)</lang>

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. <lang jq>def binomial(n; k):

 if k > n / 2 then binomial(n; n-k)
 else reduce range(1; k+1) as $i (1; . * (n - $i + 1) / $i)
 end;

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

def catalan_by_pascal: . as $n | binomial(2*$n; $n) - binomial(2*$n; $n-1);</lang>

Example:

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

Output:

<lang sh>$ jq -n -c -f Catalan_numbers_Pascal.jq [0,0] [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] [30,3814986502092304] [31,14544636039226880] [510,5.491717746183512e+302] [511,null]</lang>

Mathematica

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. <lang Mathematica>nextrow[lastrow_] := Module[{output},

 output = ConstantArray[1, Length[lastrow] + 1];
 Do[
  outputi + 1 = lastrowi + lastrowi + 1;
  , {i, 1, Length[lastrow] - 1}];
 output
 ]

pascaltriangle[size_] := NestList[nextrow, {1}, size] catalannumbers[length_] := Module[{output, basetriangle},

 basetriangle = pascaltriangle[2 length];
 list1 = basetriangle# *2 + 1, # + 1 & /@ Range[length];
 list2 = basetriangle# *2 + 1, # + 2 & /@ Range[length];
 list1 - list2
 ]

(* testing *) catalannumbers[15]</lang>

Output:

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

MATLAB / Octave

<lang MATLAB>p = pascal(17); diag(p(2:end-1,2:end-1))-diag(p,2)</lang>

Output:

Nimrod

Translation of: Python

<lang nimrod>const n = 15 var t = newSeq[int](n + 2)

t[1] = 1 for i in 1..n:

 for j in countdown(i, 1): t[j] += t[j-1]
 t[i+1] = t[i]
 for j in countdown(i+1, 1): t[j] += t[j-1]
 stdout.write t[i+1] - t[i], " "</lang>

Output:

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

Pascal

<lang pascal>type

 tElement = Uint64;

var

 Catalan : array[0..50] of tElement;

procedure GetCatalan(L:longint); var

 PasTri : array[0..100] of tElement;
 j,k: longInt;

begin

 l := l*2;
 PasTri[0] := 1;
 j    := 0;
 while (j<L) do
 begin
   inc(j);
   k := (j+1) div 2;
   PasTri[k] :=PasTri[k-1];
   For k := k downto 1 do
     inc(PasTri[k],PasTri[k-1]);
   IF NOT(Odd(j)) then
   begin
     k := j div 2;
     Catalan[k] :=PasTri[k]-PasTri[k-1];
   end;
 end;

end;

var

 i,l: longint;

Begin

 l := 15;
 GetCatalan(L);
 For i := 1 to L do
   Writeln(i:3,Catalan[i]:20);

end.</lang>

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

PARI/GP

<lang parigp>vector(15,n,binomial(2*n,n)-binomial(2*n,n+1))</lang>

Output:

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

Perl

Translation of: C++

<lang Perl>use constant N => 15; my @t = (0, 1); for(my $i = 1; $i <= N; $i++) {

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

}</lang>

Output:

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

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

Library: ntheory

<lang Perl>use ntheory qw/binomial/; print join(" ", map { binomial( 2*$_, $_) / ($_+1) } 1 .. 1000), "\n";</lang>

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

Perl 6

<lang perl6>constant @pascal = [1], -> @p { [0, @p Z+ @p, 0] } ... *;

constant @catalan = gather for 2, 4 ... * -> $ix {

   my @row := @pascal[$ix];
   my $mid = +@row div 2;
   take [-] @row[$mid, $mid+1]

}

.say for @catalan[^20];</lang>

Output:

PicoLisp

<lang PicoLisp>(de bino (N K)

  (let f
     '((N)
        (if (=0 N) 1 (apply * (range 1 N))) )
     (/
        (f N)
        (* (f (- N K)) (f K)) ) ) )

(for N 15

 (println
    (-
       (bino (* 2 N) N)
       (bino (* 2 N) (inc N)) ) ) )

(bye)</lang>

Python

Translation of: C++

<lang python>>>> n = 15 >>> t = [0] * (n + 2) >>> t[1] = 1 >>> for i in range(1, n + 1): for j in range(i, 1, -1): t[j] += t[j - 1] t[i + 1] = t[i] for j in range(i + 1, 1, -1): t[j] += t[j - 1] print(t[i+1] - t[i], end=' ')

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

Works with: Python version 2.7

<lang python>def catalan_number(n):

   nm = dm = 1
   for k in range(2, n+1):
     nm, dm = ( nm*(n+k), dm*k )
   return nm/dm

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

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

Racket

lang racket

(define (next-half-row r)

 (define r1 (for/list ([x r] [y (cdr r)]) (+ x y)))
 `(,(* 2 (car r1)) ,@(for/list ([x r1] [y (cdr r1)]) (+ x y)) 1 0))

(let loop ([n 15] [r '(1 0)])

 (cons (- (car r) (cadr r))
       (if (zero? n) '() (loop (sub1 n) (next-half-row r)))))

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

</lang>

REXX

explicit subscripts

All of the REXX program examples can handle arbitrary large numbers. <lang rexx>/*REXX program obtains Catalan numbers from Pascal's triangle. */ parse arg N .; if N== then N=15 /*Any args? No, then use default*/ numeric digits max(9,N%2+N%8) /*can handle huge Catalan numbers*/ @.=0; @.1=1 /*stem array default; 1st value.*/

 do i=1  for N;                         ip=i+1
                do j=i   by -1  for N;  jm=j-1;  @.j=@.j+@.jm;  end /*j*/
 @.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.*/
 end   /*i*/                          /*stick a fork in it, we're done.*/</lang>

Output:

when using the default input

implicit subscripts

<lang rexx>/*REXX program obtains/displays Catalan numbers from Pascal's triangle.*/ parse arg N .; if N== then N=15 /*Any args? No, then use default*/ numeric digits max(9,N%2+N%8) /*can handle huge Catalan numbers*/ @.=0; @.1=1 /*stem array default; 1st value.*/

 do i=1  for N;   ip=i+1
                do j=i   by -1  for N;  @.j=@.j+@(j-1);   end  /*j*/
 @.ip=@.i;      do k=ip  by -1  for N;  @.k=@.k+@(k-1);   end  /*k*/
 say  @.ip-@.i                        /*display the Ith Catalan number.*/
 end   /*i*/

exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────@ subroutine────────────────────────*/ @: parse arg !; return @.! /*return the value of @.[arg(1)]*/</lang> output is the same as the 1^st version.

using binomial coefficients

<lang rexx>/*REXX program obtains/displays Catalan numbers from Pascal's triangle.*/ parse arg N .; if N== then N=15 /*Any args? No, then use default*/ numeric digits max(9,N*4) /*can handle huge Catalan numbers*/

    do j=1  for N                     /* [↓]  show   N  Catalan numbers*/
    say  comb(j+j,j) % (j+1)          /*display the Jth Catalan number.*/
    end   /*j*/

exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────! (factorial) function──────────────*/ !: procedure; parse arg z; _=1; do j=1 for arg(1); _=_*j; end; return _ /*──────────────────────────────────COMB (binomial coefficient) function*/ comb: procedure; parse arg x,y; if x=y then return 1; if y>x then return 0 if x-y<y then y=x-y; _=1; do j=x-y+1 to x; _=_*j; end; return _/!(y)</lang> output is the same as the 1^st version.

binomial coeff., memoized

This REXX version uses memoization for the calculation of factorials. <lang rexx>/*REXX program obtains/displays Catalan numbers from Pascal's triangle.*/ parse arg N .; if N== then N=15 /*Any args? No, then use default*/ numeric digits max(9,N*4) /*can handle huge Catalan numbers*/ !.=.

    do j=1  for N                     /* [↓]  show   N  Catalan numbers*/
    say  comb(j+j,j) % (j+1)          /*display the Jth Catalan number.*/
    end   /*j*/

exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────! (factorial) function──────────────*/ !: procedure expose !.; parse arg z; if !.z\==. then return !.z; _=1

     do j=1  for arg(1); _=_*j; end;        !.z=_;       return _

/*──────────────────────────────────COMB (binomial coefficient) function*/ comb: procedure expose !.; parse arg x,y; if x=y then return 1 if y>x then return 0 if x-y<y then y=x-y; _=1; do j=x-y+1 to x; _=_*j; end; return _/!(y)</lang> output is the same as the 1^st version.

Run BASIC

<lang runbasic>n = 15 dim t(n+2) t(1) = 1 for i = 1 to n

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

print t(i+1) - t(i);" "; next i</lang>

Output:

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

Ruby

<lang tcl>def catalan(num)

 t = [0, 1] #grows as needed
 1.upto(num).map do |i|
   i.downto(1){|j| t[j] += t[j-1]}
   t[i+1] = t[i]
   (i+1).downto(1) {|j| t[j] += t[j-1]}
   t[i+1] - t[i]
 end

end

puts catalan(15).join(", ")</lang>

Output:

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

VBScript

To run in console mode with cscript. <lang vbscript>dim t() if Wscript.arguments.count=1 then

 n=Wscript.arguments.item(0)

else

 n=15

end if redim t(n+1) 't(*)=0 t(1)=1 for i=1 to n

 ip=i+1
 for j = i to 1 step -1 
   t(j)=t(j)+t(j-1)
 next 'j
 t(i+1)=t(i)
 for j = i+1 to 1 step -1 
   t(j)=t(j)+t(j-1)
 next 'j
 Wscript.echo t(i+1)-t(i)

next 'i</lang>

Scilab

<lang>n=15 t=zeros(1,n+2) t(1)=1 for i=1:n

 for j=i+1:-1:2 
   t(j)=t(j)+t(j-1)
 end
 t(i+1)=t(i)
 for j=i+2:-1:2
   t(j)=t(j)+t(j-1)
 end
 disp(t(i+1)-t(i))

end</lang>

Output:

Seed7

<lang seed7>$ include "seed7_05.s7i";

const proc: main is func

 local
   const integer: N is 15;
   var array integer: t is [] (1) & N times 0;
   var integer: i is 0;
   var integer: j is 0;
 begin
   for i range 1 to N do
     for j range i downto 2 do
       t[j] +:= t[j - 1];
     end for;
     t[i + 1] := t[i];
     for j range i + 1 downto 2 do
       t[j] +:= t[j - 1];
     end for;
     write(t[i + 1] - t[i] <& " ");
   end for;
   writeln;
 end func;</lang>

Output:

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

Tcl

<lang tcl>proc catalan n {

   set result {}
   array set t {0 0 1 1}
   for {set i 1} {[set k $i] <= $n} {incr i} {

for {set j $i} {$j > 1} {} {incr t($j) $t([incr j -1])} set t([incr k]) $t($i) for {set j $k} {$j > 1} {} {incr t($j) $t([incr j -1])} lappend result [expr {$t($k) - $t($i)}]

   }
   return $result

}

puts [catalan 15]</lang>

Output:

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

TI-83 BASIC

<lang ti83b>"CATALAN 15→N seq(0,I,1,N+2)→L1 1→L1(1) For(I,1,N) For(J,I+1,2,-1) L1(J)+L1(J-1)→L1(J) End L1(I)→L1(I+1) For(J,I+2,2,-1) L1(J)+L1(J-1)→L1(J) End Disp L1(I+1)-L1(I) End</lang>

Output:

zkl

Translation of: PARI/GP

using binomial coefficients.

<lang zkl>fcn binomial(n,k){ (1).reduce(k,fcn(p,i,n){ p*(n-i+1)/i },1,n) } (1).pump(15,List,fcn(n){ binomial(2*n,n)-binomial(2*n,n+1) })</lang>

Output:

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