## 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.

Pages: 1 2

### 7 Responses to “Catalan’s Triangle”

1. Rutger said
```def catalan_triangle(depth, current):
print(current)
if depth != 0:
next = 
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, 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 = 
while True:
yield row
row = list(accumulate(row+))

c = catalan_triangle()
for i in range(6):
print(next(c))
```
3. ```function catalan_triangle(n){
let t = [];
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 = 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):
```
```[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, 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]
```