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