Motzkin Numbers
September 14, 2021
The comments at A001006 make this easy:
(define (a001006 k) ; first k terms
(let loop ((a 0) (b 1) (n 1) (k k) (ms (list)))
(if (zero? k) (reverse ms)
(let* ((ms (cons (/ b n) ms))
(n (+ n 1))
(c (/ (+ (* 3 (- n 1) n a)
(* (+ n n -1) n b))
(* (+ n 1) (- n 1)))))
(loop b c n (- k 1) ms)))))
I might be weird, but I love clicking through the sequences at OEIS and learning about new things. You can run today’s program at https://ideone.com/bTWbli.
Programming Praxis 
Welcome back! Retirement is good, I recommend it.
Richard P. Stanley tells us that the Motzkin numbers are the first elements of successive differences of the Catalan numbers (counting from C₁):
so in Haskell:
Of course, that should have been motz, not moz:
Or maybe this is better as we avoid explicit recursion:
Here’s a solution in Python.
def motzkin(): x, y, n = 1, 0, 1 while True: yield x x, y, n = (3 * (n - 1) * y + (2 * n + 1) * x) // (n + 2), x, n + 1 m = motzkin() for _ in range(10): print(next(m))Output:
We are also told that Motzkin numbers count lists of {-1,0,-1}, length n, such that partial sums are >= 0, total sum == 0, so let’s have a function that generates all such lists and count the result:
-- [] -- [0] -- [0,0],[1,-1] -- [0,0,0],[0,1,-1],[1,0,-1],[1,-1,0], -- [0,0,0,0],[0,1,-1,0],[1,0,-1,0],[1,-1,0,0], f :: Int -> Int -> [[Int]] f 0 0 = [[]] f n m | m < 0 = [] | n < m = [] | otherwise = map (0:) (f (n-1) m) ++ map (1:) (f (n-1) (m+1)) ++ map(-1:) (f (n-1) (m-1)) main = print (f 4 0) >> -- [[0,0,0,0],[0,0,1,-1],[0,1,0,-1],[0,1,-1,0],[1,0,0,-1], -- [1,0,-1,0],[1,1,-1,-1],[1,-1,0,0],[1,-1,1,-1]] print [length (f n 0) | n <- [0..10]] -- [1,1,2,4,9,21,51,127,323,835,2188]Another nice connection with the Catalan numbers (https://oeis.org/A000108 – “This is probably the longest entry in the OEIS, and rightly so.”) – comment out the ‘0’ clause in the definition of f and apply to 2n instead of n:
f 0 0 = [[]] f n m | m < 0 = [] | n < m = [] | otherwise = --map (0:) (f (n-1) m) ++ map (1:) (f (n-1) (m+1)) ++ map(-1:) (f (n-1) (m-1)) main = print [length (f (2*n) 0) | n <- [0..10]] --[1,1,2,5,14,42,132,429,1430,4862,16796]Another Catalan connection: the Motzkin numbers count the number of correctly parenthesized words of length 2n, constructed from “((“,”()” and “))” (just substitute for 1,0,-1 in previous sequences), so Motzkin(n) <= Catalan(n).
A couple of solutions in Racket.