Chapter 34
Related Number Sequences: The Motzkin Numbers, The Fine Numbers, and The Schröder Numbers
When dealing with the Fibonacci numbers we learned, in Example 12.5, about a closely related sequence of numbers called the Lucas numbers. These numbers are often considered “a first cousin” of the Fibonacci numbers.
Turning to the Catalan numbers, now we find several “first cousins” for this sequence of numbers.
Example 34.1 (The Motzkin Numbers): This sequence of numbers first appeared in Reference [28] and has consequently come to be called the sequence of Motzkin numbers, after the (German-born) American mathematician Theodore Samuel Motzkin (1908–1970).
For n ≥ 0, the nth Motzkin number Mn can be given by any of the following three formulas:
1. Mn = ∑ k≥0n2kCk
2. 
3. 
The first of these provides an immediate connection with the sequence of Catalan numbers. 283
One finds that the first 11 Motzkin numbers are 1, 1, 2, 4, 9, 21, 51, 127, 323, 835, and2188.
Two situations where the Motzkin numbers arise are as follows:
a. For n ≥ 0, Mn counts the number of ways one can draw chords between n points on the circumference of a circle, so that no two chords intersect on, or within the interior of, the circle. Note here that, unlike the situation in Example 32.3 (b) for the Catalan ...
