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.
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] + t[j - 1]; t[i + 1] = t[i]; foreach_reverse (immutable j; 2 .. i + 2) t[j] = 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
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
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
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
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>
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
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