© 2014 Shmoop University, Inc. All rights reserved.
 

Topics

Introduction to Sequences - At A Glance:

It's possible to arrive at the same sequence of numbers from different directions by solving different problems.

Sample Problem

How many ways are there to arrange n pairs of parentheses in a way that makes grammatical sense? Something like

)(

doesn't make grammatical sense.

Answer.

When n = 1 there's only one way to arrange them:

()

When n = 2 there are two ways:

()(), (())

When n = 3 there are five ways:

()()(), ((())), (())(), ()(()), (()())

Let

Cn = number of ways to grammatically arrange n pairs of parentheses.

The numbers Cn for n ≥ 0 are called the Catalan numbers.

Sample Problem

How many ways are there to get from the point (0,0) to the point (n,n) if every step is either up one or to the right one and we can't go over the line y = x?

Answer. When n = 1 there's only one way. We go right 1, then up 1:

When n = 2 there are 2 ways:

When n = 3 there are 5 ways:

In general, there are Cn ways. These are the same Catalan numbers Cn we saw with the parentheses example.

Catalan numbers count a lot of things, some of which don't seem to have anything to do with each other. It's tricky to come up with the formula from scratch, but the nth Catalan number is given by

For more information, you can look up the Catalan Numbers on the On-Line Encyclopedia of Integer Sequences here.

Advertisement
Advertisement
back to top