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

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