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.

Advertisements

Pages: 1 2

7 Responses to “Catalan’s Triangle”

  1. Rutger said
    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]
    
  2. Paul said

    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))
    
  3. 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;
    }
    
  4. ^^^ Javascript solution

    console.log(
      catalan_triangle(4)
    );
    
    /*
    1
    1 1
    1 2 2
    1 3 5 5
    */
    
    
  5. Daniel said

    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
    
  6. 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
    */
    
  7. matthew said

    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]
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: