## 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

### 9 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 ..
```

```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],[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]
```
7. matthew said

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

8. matthew said
```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]
```