Chapter 33

The Narayana Numbers

In Example 5.6(a), we learned how each Fibonacci number can be expressed as a sum of binomial coefficients. A somewhat similar situation arises for the Catalan numbers by way of the Narayana numbers. Named after the Indian mathematician Tadepalli Venkata Narayana, the Narayana numbers are defined as follows:

img

Table 33.1 provides the values of N(n, k) for 1 ≤ kn ≤ 7.

Table 33.1

img

The last column of Table 33.1 suggests that for n ≥ 1,

img

We shall prove that this is indeed the case! Before we do so, however, we would like to know if the individual summands—namely, N(n, k)—have any combinatorial significance. The answer is a resounding “Yes!” The following will provide interpretations of the Narayana numbers for some of the examples we have encountered for the Catalan numbers.

Example 33.1:

1. In Fig. 33.1, we have the five lattice paths from (0, 0) to (3, 3) that never rise above the line y = x. We first encountered these paths in Fig. 19.2 of Example 19.1. Here we see that there is 1 = N(3, 1) such path with one turn—where there is an R followed by a U. Also, there are 3 = N(3, 2) paths with two such turns, and 1 = N(3, 3) path with three such turns. ...

Get Fibonacci and Catalan Numbers: An Introduction now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.