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.

Pages: 1 2

6 Responses to “Motzkin Numbers”

  1. matthew said

    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

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

    motz s = head s : motz (diffs s) -- first element of successive differences
    
  3. matthew said

    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

    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

    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

    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]
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: