Catalan’s Triangle
September 19, 2017
Our solution comes in two parts: next-row takes a row and returns the next row, and catalan-triangle builds a complete triangle:
(define (next-row xs)
(let loop ((xs (cdr xs)) (ys (list 1)))
(if (null? xs) (reverse (cons (car ys) ys))
(loop (cdr xs) (cons (+ (car xs) (car ys)) ys)))))
(define (catalan-triangle n)
(let loop ((n n) (xs (list (list 1))))
(if (zero? n) (reverse xs)
(loop (- n 1) (cons (next-row (car xs)) xs)))))
Here’s an example:
> (catalan-triangle 8) ((1) (1 1) (1 2 2) (1 3 5 5) (1 4 9 14 14) (1 5 14 28 42 42) (1 6 20 48 90 132 132) (1 7 27 75 165 297 429 429) (1 8 35 110 275 572 1001 1430 1430))
The Catalan numbers march down the right spine of the triangle. You can run the program at https://ideone.com/FDzzog.
Another solution in Python using itertools.accumulate.
def catalan_triangle(): row = [1] while True: yield row row = list(accumulate(row+[0])) c = catalan_triangle() for i in range(6): print(next(c))function catalan_triangle(n){ let t = [[1]]; for (let i=s=0; i<n; i+=1,s=0){ t[t.length] = t[t.length-1].map(v=>s+=v).concat(s); } return t; }^^^ Javascript solution
Here’s a solution in C99.
#include <stdio.h> // Return size of triangle with specified number of rows. // size = n (n + 1) / 2 static int size(const int nrows) { int x = nrows; int y = nrows + 1; if (nrows % 2 == 0) x /= 2; else y /= 2; return x * y; } static void catalan_triangle(const int nrows, int* data) { int idx = 0; for (int i = 0; i < nrows; ++i) { for (int j = 0; j <= i; ++j) { if (j == 0) { data[idx] = 1; } else if (i == j) { data[idx] = data[idx-1]; } else { data[idx] = data[idx-1] + data[idx-i]; } ++idx; } } } static int num_digits(int x) { if (x == 0) return 1; int n = 0; while (x != 0) { ++n; x /= 10; } return n; } static void print_catalan_triangle(const int nrows, const int* data) { int idx = 0; const int n = size(nrows); int col_digits[nrows]; for (int i = 0; i < nrows; ++i) { for (int j = 0; j <= i; ++j) { if (i == j) { col_digits[j] = num_digits(data[n - nrows + j]); } if (j > 0) printf(" "); printf("%*d", col_digits[j], data[idx]); ++idx; } printf("\n"); } } int main(int argc, char* argv[]) { int nrows = 10; int n = size(nrows); int data[n]; catalan_triangle(nrows, data); print_catalan_triangle(nrows, data); }Output:
C solution
void catalan_triangle(int n){ int t[n]; t[0] = 1; for (int i=0,s=0; i<n; i+=1, s=0){ for (int j=0; j<i+1; j+=1){ printf("%d ", t[j]); t[j] = (s += t[j]); } t[i+1] = t[i]; puts(""); } } catalan_triangle(4); /* 1 1 1 1 2 2 1 3 5 5 */An nice way to construct Catalan’s triangle is to first construct Pascal’s triangle:
from operator import add p = [[0,1]] for i in range(14): p.append(map(add,p[-1]+[0],[0]+p[-1]))and then the Catalan elements are just differences of adjacent elements along diagonals, so, for example, 429 = 3432-3003 = 1716-1287 and 90 = 210-120:
for i in range(8): print(map (lambda j: p[i+j][j+1]-p[i+j][j], range(i+1)))