O'Reilly logo

Fibonacci and Catalan Numbers: An Introduction by Ralph P. Grimaldi

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

No credit card required

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 ...

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

Start Free Trial

No credit card required