Chapter 20
Some Further Initial Examples
Although we now have a formula for Cn, the nth Catalan number, things here will prove to be somewhat different from what we did when we first encountered the Fibonacci numbers. Unlike what we saw in Part One, at this point we do not have any type of recurrence relation for the Catalan numbers.
When we questioned whether a new problem was another example of the Fibonacci numbers (sometimes shifted one or two subscripts), we always made an effort to count the structures in our new situation by means of the second-order linear recurrence relation satisfied by the Fibonacci numbers. However, for the Catalan numbers, at least at the start, we shall have to take a different approach. This will be accomplished by setting up a one-to-one correspondence (or bijection) between the elements in our new example and those of an example whose elements we already know are counted by the Catalan numbers. Although we presently know only one example where the Catalan numbers arise, we shall soon find several others.
Example 20.1 Let us start by counting all balanced strings made up of n left parentheses and n right parentheses, where the number of right parentheses never exceeds the number of left parentheses, as the string is read from left to right. For example, if n = 3, we are interested in counting strings like ()()() and (())() but not (()))( or ())((). The five balanced strings made up from three left parentheses and three right parentheses are shown ...
