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 19

A First Example: A Formula for the Catalan Numbers

In this chapter, we shall find an example where the Catalan numbers arise. This example will deal with lattice paths in the Cartesian plane and it will provide us with the means to determine a formula for the Catalan numbers. In addition, we shall learn how the Catalan numbers are related to certain entries in Pascal's triangle.

Example 19.1 Let us start at the point (0, 0) in the xy -plane and consider two types of steps:

equation

We want to count the number of ways we can travel from (0, 0) to (4, 4) using such steps—one unit to the right or one unit up. Consequently, any such path will be made up of four R's and four U's. Since we can arrange four R's and four U's in

equation

ways, this tells us that there are 70 such paths from (0, 0) to (4, 4). These paths are often referred to as lattice paths. In parts (a), (b), (c), and (e) of Fig. 19.1 we find four of these 70 possible lattice paths.

Now suppose that we once again start at the point (0, 0) in the xy-plane and travel to the point (4, 4) using the same types of steps—namely, four R's and four U's. But this time there is a catch! As we progress from (0, 0) to (4, 4), we can never travel above the line y = x. We will touch the line at (0, 0) and (4, 4), and perhaps at (1, 1), (2, ...

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