Catalan numbers/Pascal's triangle
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.
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
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
<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
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
<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:
->cn 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 ->
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, as required by the task description, but see Catalan_numbers#jq for better alternatives.
<lang jq># Warning: jq uses IEEE 754 64-bit arithmetic,
- so the algorithm loses precision for n > 30 and fails completely for n > 510.
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.bak [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:
ans = 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
Nimrod
<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
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
<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:
<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:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670 129644790 477638700 1767263190 6564120420
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
<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>
<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>
- 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
<lang rexx>/*REXX program obtains Catalan numbers from Pascal's triangle. */ numeric digits 200 /*might have large Catalan nums. */ parse arg N .; if N== then N=15 /*Any args? No, then use default*/ @.=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 end /*i* /*stick a fork in it, we're done.*/</lang>
output when using the default input:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
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
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
zkl
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)