Numeros De Catalan

Catalan Numbers
Tom Davis
tomrdavis@earthlink.net http://www.geometer.org/mathcircles November 24, 2010 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. Later in the document we will derive relationships and explicit formulas for the Catalan numbers in many different ways.1 Problems
1.1 Balanced Parentheses
Suppose you have n pairs of parentheses and you would like to form valid groupings of them, where “valid” means that each open parenthesis has a matching closed parenthesis. For example, “(()())” is valid, but “())()(” is not. How many groupings are there for each value of n? Perhaps a more precise definition of the problem would be this: A string ofparentheses is valid if there are an equal number of open and closed parentheses and if you begin at the left as you move to the right, add 1 each time you pass an open and subtract 1 each time you pass a closed parenthesis, then the sum is always non-negative. Table 1 shows the possible groupings for 0 ≤ n ≤ 5. n = 0: n = 1: n = 2: n = 3: n = 4:
* () ()(), (()) ()()(), ()(()), (())(), (()()), ((()))()()()(), ()()(()), ()(())(), ()(()()), ()((())), (())()(), (())(()), (()())(), ((()))(), (()()()), (()(())), ((())()), ((()())), (((()))) ()()()()(), ()()()(()), ()()(())(), ()()(()()), ()()((())), ()(())()(), ()(())(()), ()(()())(), ()((()))(), ()(()()()), ()(()(())), ()((())()), ()((()())), ()(((()))), (())()()(), (())()(()), (())(())(), (())(()()), (())((())), (()())()(), (()())(()), ((()))()(),((()))(()), (()()())(), (()(()))(), ((())())(), ((()()))(), (((())))(), (()()()()), (()()(())), (()(())()), (()(()())), (()((()))), ((())()()), ((())(())), ((()())()), (((()))()), ((()()())), ((()(()))), (((())())), (((()()))), ((((()))))

1 way 1 way 2 ways 5 ways 14 ways

n = 5:

42 ways

Table 1: Balanced Parentheses * It is useful and reasonable to define the count for n = 0 to be 1,since there is exactly one way of arranging zero parentheses: don’t write anything. It will become clear later that this is exactly the right interpretation. 1

1.2 Mountain Ranges
How many “mountain ranges” can you form with n upstrokes and n downstrokes that all stay above the original line? If, as in the case above, we consider there to be a single mountain range with zero strokes, Table 2gives a list of the possibilities for 0 ≤ n ≤ 3: n = 0: n = 1: n = 2: n = 3: * /\ /\ /\/\, / \ /\ /\ /\ /\/\ / \ /\/\/\, /\/ \, / \/\, / \, / \ Table 2: Mountain Ranges Note that these must match the parenthesis-groupings above. The “(” corresponds to “/” and the “) to “\”. The mountain ranges for n = 4 and n = 5 have been omitted to save space, but there are 14 and 42 of them, respectively. It is agood exercise to draw the 14 versions with n = 4. In our formal definition of a valid set of parentheses, we stated that if you add one for open parentheses and subtract one for closed parentheses that the sum would always remain non-negative. The mountain range interpretation is that the mountains will never go below the horizon. 1 way 1 way 2 ways 5 ways

1.3 Diagonal-Avoiding Paths
In a gridof n × n squares, how many paths are there of length 2n that lead from the upper left corner to the lower right corner that do not touch the diagonal dotted line from upper left to lower right? In other words, how many paths stay on or above the main diagonal?

/

/\ /\/\ \/ \

Figure 1: Corresponding Path and Range This is obviously the same question as in the example above, with themountain ranges running diagonally. In Figure 1 we can see how one such path corresponds to a mountain range. Another equivalent statement for this problem is the following. Suppose two candidates for election, A and B, each receive n votes. The votes are drawn out of the voting urn one after the other. In how many ways can the votes be drawn such that candidate A is never behind candidate B?

2...