Fibonacci and Catalan Numbers: An Introduction

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 a₁, a₂, . . ., a_n be a nondecreasing sequence of positive integers where a_i ≤ 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 a₁, a₂, a₃ where a₁ ≤ 1, a₂ ≤ 2, and a₃ ≤ 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: