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.

7 Responses to “Catalan’s Triangle”

Rutger said

September 19, 2017 at 10:30 AM

def catalan_triangle(depth, current):
	print(current)
	if depth != 0:
		next = [1]
		for i in range(1,len(current)):
			next.append(current[i])
			next[i] += next[i-1]
		next.append(next[-1])
		catalan_triangle(depth-1, next)

catalan_triangle(6, [1])


# [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]

Paul said

September 19, 2017 at 11:09 AM

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

Sochima Biereagu said

September 21, 2017 at 6:32 PM

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;
}

Sochima Biereagu, KodeJuice said
September 21, 2017 at 6:36 PM
^^^ Javascript solution
```
console.log(
  catalan_triangle(4)
);

/*
1
1 1
1 2 2
1 3 5 5
*/
```

Daniel said

September 22, 2017 at 9:21 PM

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:

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
1 9 44 154 429 1001 2002 3432 4862 4862

Sochima Biereagu said

September 24, 2017 at 10:17 AM

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
*/

matthew said

September 25, 2017 at 9:57 PM

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

[0, 1]
[0, 1, 1]
[0, 1, 2, 1]
[0, 1, 3, 3, 1]
[0, 1, 4, 6, 4, 1]
[0, 1, 5, 10, 10, 5, 1]
[0, 1, 6, 15, 20, 15, 6, 1]
[0, 1, 7, 21, 35, 35, 21, 7, 1]
[0, 1, 8, 28, 56, 70, 56, 28, 8, 1]
[0, 1, 9, 36, 84, 126, 126, 84, 36, 9, 1]
[0, 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1]
[0, 1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1]
[0, 1, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1]
[0, 1, 13, 78, 286, 715, 1287, 1716, 1716, 1287, 715, 286, 78, 13, 1]
[0, 1, 14, 91, 364, 1001, 2002, 3003, 3432, 3003, 2002, 1001, 364, 91, 14, 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)))

[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]

Programming Praxis