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.