Massachusetts Institute of Technology Handout 48 6.042J/18.062J: Mathematics for Computer Science November 6, 1998 Professors N. Lynch and S. Devadas

Problem for Recitation 9 (11/6/98)

Problem 1. We consider an ingenious approach to counting well-matched parenthesis strings.

For example, (()((())())) is well-matched. On the other hand, no string that begins with a right parenthesis or ends with a left parenthesis can be well-matched; neither can any proper prefix of a well-matched string be well-matched.

We want to compute the number, S_{n}, of such well-matched parenthesis strings of length 2n. It’s easy to check that S_{1} = 1, S_{2} = 1, S_{3} = 2. With a little case analysis, the only well-matched strings of 8 parentheses are

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

so S_{4} = 5.

The team problem develops an ingenious combinatorial approach to arrive at a simple formula for S_{n}. Our approach will involve considering paths in the plane from a point (x_{1}, y_{1}) to (x_{2}, y_{2}) for x_{i}, y_{i} ∈ ℤ, where each step in the path is at a ±45 degree angle, increasing the x-coordinate by 1 and the y-coordinate by ±1. For example, a path might start at (1, 1) and make seven steps to the successive points (2, 0), (3, −1), (4, 0), (5, 1), (6, 2), (7, 1), (8, 0) as in Figure 1.

(a) Explain why the number of well-matched parenthesized strings of length 2n is the same as the number of paths from (0, 0) to (2n, 0) which only touch the x-axis at their endpoints. (That is, if 0 < i < 2n and (i, j) is a point on the path, then j > 0.)

(b) How many paths are there from (x_{1}, y_{1}) to (x_{2}, y_{2})? (Express the answer as a binomial coefficient.)

(c) For y_{1}, y_{2} > 0, show that the number of paths from (x_{1}, y_{1}) to (x_{2}, y_{2}) which touch or cross the x-axis is equal to the number of paths from (x_{1}, −y_{1}) to (x_{2}, y_{2}). See Figure 2.

(d) Conclude that the number of well-matched strings of 2n parentheses equals the n − 1st Catalan number

\frac{1}{n}\binom{2n − 2}{n − 1}.

Handout 48: Problem for Recitation 9 (11/6/98) 2

(x_1, y_1)

(x_2, y_2)

Figure 1: A path from (1, 1) to (8, 0). (x_{1}, y_{1}) (x_{1}, −y_{1})

(x_{2}, y_{2})

Figure 2: Reflection of the initial part of a path.