We have changed our privacy policy. In addition, we use cookies on our website for various purposes. By continuing on our website, you consent to our use of cookies. You can learn about our practices by reading our privacy policy.
© 2016 Shmoop University, Inc. All rights reserved.


I Like Abstract Stuff; Why Should I Care?

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.


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:

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


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.

People who Shmooped this also Shmooped...