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:


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


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


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.