# Sequences

### Topics

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

*C _{n}* = number of ways to grammatically arrange

*n*pairs of parentheses.

The numbers *C _{n}* 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 *C _{n}* ways. These are the same Catalan numbers

*C*we saw with the parentheses example.

_{n}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 *n*^{th} Catalan number is given by

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