Catalan’s Triangle
September 19, 2017
Since our exercise a week ago, I’ve been reading about Catalan numbers, primarily based on the references at OEIS. Catalan’s Triangle (A009766) is a number triangle
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
such that each element is equal to the one above plus the one to the left.
Your task is to write a program that calculates a Catalan triangle. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
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)))