## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

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: 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: ## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required