Motzkin Numbers
September 14, 2021
[ I’ve had a couple of readers ask where I have been. I put in my retirement papers at work a few months ago, and will retire at the end of 2021. That sounds good, but setting up my post-retirement finances, learning about Medicare (it’s a huge mess) and deciding what to do with the rest of my life has been exhausting, and I still have a job to do. Here’s a simple exercise; I’ll try to be more regular about posting in future weeks. — Phil ]
Your task is to write a program to generate Motzkin Numbers (A001006). If you don’t like Motzkin numbers, pick any other sequence from the OEIS. 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.
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.