The Catalan Numbers
In Chapter 5, we learnt that the number of shortest P–Q routes in the 2 × 4 rectangular grid of Figure 19.1 is, by (BP), equal to the number of 6-digit binary sequences with four 0’s and two 1’s. This is
Consider the case when O = (0,0) and A = (n,n), where n is a positive integer. By (19.1), the number of shortest O–A routes is given by 
As shown in Figure 19.3 (where n = 4), we observe that the 
shortest O-A routes can be divided into two groups: those that cross the diagonal y = x (see (i)) and those that do not (see (ii) and (iii)).
Figure 19.1
Figure 19.2
Figure 19.3
Around 1887, the French combinatorist Désiré André (1840-1917) studied the following problem.
For convenience, let us denote by f(n) the number of such nondiagonal-crossing shortest routes from O(0,0) to A(n, n). For n = 1,2,3, all such routes and the values of f(n) are shown in Table 19.1.
In what follows, we shall present André’s elegant idea in solving the problem.
By translating a route in the coordinate system one unit to the right as shown in Figure 19.4, we see that there is a 1-1 correspondence between the family of shortest routes from O(0, 0) to A(n, n) that do not cross y = x and the family of shortest routes from P(1,0) to Q(n + 1, n) that do not meet y = x.
Figure 19.4
Thus, by (BP), we have:
Now, let g(n) denote the number of shortest routes from P(1,0) to Q(n +1, n) that meet y = x. Clearly, f (n)+ g(n) is the number of shortest routes from P(1, 0) to Q(n + 1,n). Thus, by (19.1), we have:
Accordingly, to evaluate f (n), we may instead evaluate g(n).
But how to evaluate g(n)? Is it a less difficult problem? Let us first of all consider an example and make some observations.
Figure 19.5 shows a shortest route from P(1,0) to Q(8, 7) (here, n = 7) that meets y = x.
Imagine that we are now traversing the route from P to Q. Let X be the point where the route meets y = x for the first time (in Figure 19.5, X = (2,2)); note that such an X always exists. Consider the reflection of this part of the route from P to X with respect to y = x as shown in Figure 19.6. Beginning with this image of reflection and following the rest of the original shortest route from X to Q, we obtain a shortest route from P′(0,1) to Q(8, 7).
Figure 19.5
Figure 19.6
The reader may check that this reflection does provide a 1-1 correspondence between the family of shortest routes from P(1, 0) to Q(8, 7) that meet y = x and the family of shortest routes from P'(0,1) to Q(8, 7). Thus, by (BP) and (19.1),
In general, we have
Combining this with (19.4), we see that
That is:
In particular, f(1) = 1, f(2) = 2 and f(3) = 5, which agree with Figure 19.1.
The numbers
that have just been obtained above are called Catalan numbers (denoted by C(n)) after the Belgium mathematician Eugene Charles Catalan.
Catalan (1814-1894)
Indeed, around 1838, Catalan studied the following problem:
The ways of parenthesising x1 · x2……xn for n = 2,3,4 are shown in Table 19.2.
It turns out that the number of ways obtained are 1,2 and 5, and these are the first three Catalan numbers.
Let us proceed to present another problem which is equivalent to the one introduced by E. Just in The American Mathematics Monthly (76).
Table 19.2
Table 19.3 shows all such binary sequences for n = 1,2,3. Notice that the numbers of such sequences are again the first three Catalan numbers.
Table 19.3
The solution of Problem (A) given by André gives rise to the Catalan numbers 
The answers for the first three initial cases of Problems (B) and (C) are 1,2 and 5, which are Catalan numbers. Is it true that the answers for Problems (B) and (C) for general cases are also Catalan numbers?
Yes, they are! In Table 19.4, we exhibit, by examples, 1-1 correspondences among the routes for Problem (A), the ways of parenthesising x1 · x2 · … · xn for Problem (B) and the binary sequences for Problem (C); and we leave it to the reader to figure out the rules for the correspondences.
One of the more general problems of this type, known as the Ballot Problem, is stated below.
To find out the desired probability, the essential part of the solution is to find out the number of ways that X always stays ahead of Y throughout the counting of the votes. The problem is clearly an extension of Problems (A) and (C). Employing the ideas and techniques used to solve Problem (A), Andre solved in 1887 this more general problem. Indeed, the Ballot Problem was first posed and solved by Joseph Louis Francois Bertrand (1822-1900) in the same year 1887. The reader may refer to An Introduction to Probability Theory and Its Applications by W. Feller for more details.
It was said that in 1751, the Swiss mathematician Leonhard Euler (1707-1783) proposed to Christian Goldbach (1690-1764) the following problem which later became quite famous. The problem was solved by Johann Andreas von Segner (1704-1777) in 1758 and by Catalan in 1838 using different methods.
All the triangulations of an n-sided polygon, where n = 3,4, 5, are shown in Table 19.5. The reader may notice that the respective numbers of triangulations are the first three Catalan numbers.
Finally, let us introduce another interesting problem.
Table 19.5
Table 19.6
Table 19.6 shows all the ways for n = 1,2,3. Again, the numbers of ways are the first three Catalan numbers.
The reader is invited in the Exercise to show that the numbers of ways for Problems (D) and (E) are indeed Catalan numbers by establishing 1-1 correspondences between Problem (D) (respectively, (E) ) and any of Problems (A)-(C).
Exercise
19.1 Show that the numbers of ways for Problem (D) are Catalan numbers by establishing a 1-1 correspondence between Problem (D) and any of Problems (A)-(C).
19.2 Show that the numbers of ways for Problem (E) are Catalan numbers by establishing a 1-1 correspondence between Problem (E) and any of Problems (A)-(C).
19.3 Using Problem (D) (triangulation of polygons), prove geometrically the following recurrence relation:
19.4 A valid grouping of n pairs of parentheses is one where each open parenthesis has a matching closed parenthesis. For example, ()(()) is valid, but ()())( is not. Let P(n) be the number of valid groupings of n pairs of parentheses. Show that P(n) = C(n) by proving the recurrence relation:
19.5 A stack is a data structure where insertions and deletions take place at the top of the stack. The integers 1,2,...,n are in sequence in stack X with 1 on top. All the integers are to be moved to stack Z via stack Y. Let the stacks X, Y, Z be placed in order from left to right. A move from one stack to the stack on its immediate right is the deletion of the integer at the top of the left stack and the insertion of the same integer to the top of the right stack. After exactly 2n such moves, stacks X and Y will be empty and stack Z will contain a permutation of the integers 1,2,…,n.
(i) Show that if n = 3, the permutation (2,1,3) cannot be generated.
(ii) Find Pn, the number of permutations of 1,2,… ,n possible in stack Z.
19.6 Use the formula 
to obtain the following recurrence relation:
