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 26

Sequences and a Generating Tree

In this chapter we shall investigate a collection of sequences that are counted by the Catalan numbers. Examples related to these sequences are also examined. We start with the following.

Example 26.1: For n ≥ 1, let a1, a2, . . ., an be a nondecreasing sequence of positive integers where aii for all 1 ≤ in. When n = 1, there is only one such sequence—namely, 1. There are two such sequences for n = 2: they are 1, 1 and 1, 2.

For n = 3, we shall set up a one-to-one correspondence between the lists of three 1's and three −1's in Fig. 20.4 (in Example 20.6) and the sequences of positive integers a1, a2, a3 where a1 ≤ 1, a2 ≤ 2, and a3 ≤ 3. Start with the list 1, 1, 1, − 1, − 1, − 1. For each 1 in this list, count the number of −1's in the list to the left of this 1. We find the following:

img

We realize that 1, 1, 1 is one of the sequences (of length 3) that we are counting for the case of n = 3.

Next consider the second list in Fig. 20.4—that is, the list 1, 1, − 1, 1, − 1, − 1. Counting the −1's to the left of each of the three 1's, as we did above, we have 213

img

For the other three lists, we obtain the corresponding three sequences:

img

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