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: