Catalan Numbers

Suppose you have n pairs of parentheses and you would like to form valid groupings of them, how many groupings are there for each value of n? How many “mountain ranges” can you form with n upstrokes and n downstrokes that all stay above the original line? What about counting the number of ways to triangulate a regular polygon with n + 2 sides? We begin with a set of problems that will be shown to be completely equivalent. The solution to each problem is the same sequence of numbers called the Catalan numbers.