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

^^^ Javascript solution

Here’s a solution in C99.

Output:

C solution

An nice way to construct Catalan’s triangle is to first construct Pascal’s triangle:

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: