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 ai ≤ i for all 1 ≤ i ≤ n. 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:
