O'Reilly logo

Fibonacci and Catalan Numbers: An Introduction by Ralph P. Grimaldi

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

3. img

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required