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.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
9 Comments »

9 Responses to “Motzkin Numbers”

  1. matthew said
    September 14, 2021 at 7:29 PM

    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₁):

    1 2 5 14 42 132 ..
1 3 9 28 90 ..
2 6 19 62 ..
4 13 43 ..
9 30 ..
21 ..

    so in Haskell:

    import Data.List (inits)

-- Generate Catalan numbers
cat = map f (inits cat) where
  f [] = 1
  f s = sum (zipWith (*) s (reverse s))

-- Sequence differences
diffs s = zipWith (-) (tail s) s
motz s = head s : moz (diffs s) -- first element of successive differences

main = print (take 10 (motz (tail cat)))
-- [1,1,2,4,9,21,51,127,323,835]
  2. matthew said
    September 14, 2021 at 7:37 PM

    Of course, that should have been motz, not moz:

    motz s = head s : motz (diffs s) -- first element of successive differences
  3. matthew said
    September 14, 2021 at 7:46 PM

    Or maybe this is better as we avoid explicit recursion:

    motz s = unfoldr f s where f s = Just(head s, diffs s)
  4. Daniel said
    September 15, 2021 at 5:06 AM

    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:

    1
1
2
4
9
21
51
127
323
835
  5. matthew said
    September 15, 2021 at 12:25 PM

    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]
  6. matthew said
    September 15, 2021 at 6:17 PM

    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]
  7. matthew said
    September 20, 2021 at 5:08 PM

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

  9. matthew said
    September 30, 2021 at 7:21 AM 
    Prelude Data.List> f a b n = ((2*n+1)*a+(3*n-3)*b)`div`(n+2)
Prelude Data.List> s = 1:1:zipWith3 f (tail s) s [2..]
Prelude Data.List> take 10 s
[1,1,2,4,9,21,51,127,323,835]

Leave a comment