Counting Proper Parenthesizations (Catalan Numbers)
A *proper parenthesization* of length $2n$ is a string of $n$ left parentheses and $n$ right parentheses such that at every prefix, the number of right parentheses never exceeds the number of left parentheses.
For example, with $n = 3$: the strings $()()()$, $((()))$, and $()(())$ are valid, while $())(()$ and $(((())$ are not.
How many proper parenthesizations of length $2n$ are there? Compute the answer for $n = 6$.
Hints
- Count all strings with $n$ left and $n$ right parens first -- that's just $\binom{2n}{n}$. Then subtract the invalid ones.
- For invalid strings, find the first position where right parens exceed left parens. What happens if you flip every paren after that point?
- The reflection creates a bijection between invalid $(n, n)$ strings and all $(n-1, n+1)$ strings, giving $\binom{2n}{n+1}$ bad strings.
Worked Solution
How to Think About It: This is the classic Catalan number problem. The trick is to count the *bad* strings and subtract from the total. The total number of strings with $n$ left and $n$ right parentheses is $\binom{2n}{n}$ -- just choose which $n$ of the $2n$ positions are left parens. The hard part is counting invalid strings, and the elegant approach uses a reflection/bijection argument.
Quick Estimate: For $n = 6$, $\binom{12}{6} = 924$ total strings. The Catalan number is $\frac{1}{n+1}\binom{2n}{n} = \frac{924}{7} = 132$. So about $132/924 \approx 14\%$ of all balanced strings are valid -- which makes sense since the constraint is quite restrictive.
Approach: Use the reflection bijection (Andre's reflection principle) to count invalid strings.
Formal Solution:
Step 1: Total count. There are $2n$ positions, and we choose $n$ of them for left parentheses. The rest are right parentheses. Total: $\binom{2n}{n}$.
Step 2: Count invalid strings. A string is invalid if at some point the number of right parentheses exceeds the number of left parentheses. Consider the first position where this happens -- at that point, you have seen one more right paren than left paren.
Now apply the reflection trick: from that point onward, swap every left paren with a right paren and vice versa. Before the swap point, the parens are unchanged. After the swap, you've flipped one extra left paren to right (and one fewer right to left), so the new string has $(n+1)$ right parentheses and $(n-1)$ left parentheses.
This mapping is a bijection between invalid strings of type $(n, n)$ and *all* strings of type $(n-1, n+1)$. The number of such strings is:
$$\binom{2n}{n+1}$$
Step 3: Valid count.
$$C_n = \binom{2n}{n} - \binom{2n}{n+1} = \frac{(2n)!}{n! \, n!} - \frac{(2n)!}{(n+1)! \, (n-1)!}$$
Factor out:
$$C_n = \frac{(2n)!}{n! \, n!} \left(1 - \frac{n!}{(n+1)(n-1)!}\cdot\frac{n!}{n!}\right) = \frac{1}{n+1}\binom{2n}{n}$$
This is the $n$-th Catalan number.
Step 4: Evaluate at $n = 6$.
$$C_6 = \frac{1}{7}\binom{12}{6} = \frac{924}{7} = 132$$
Answer: The number of proper parenthesizations of length $2n$ is the $n$-th Catalan number $C_n = \frac{1}{n+1}\binom{2n}{n}$. For $n = 6$, the answer is $\boxed{132}$.
Intuition
The Catalan number formula $\frac{1}{n+1}\binom{2n}{n}$ appears everywhere in combinatorics -- counting binary trees, triangulations of polygons, monotone lattice paths that stay below the diagonal, and many more. The reflection bijection that proves it is one of the most beautiful arguments in discrete math: you show that every bad path corresponds uniquely to an unrestricted path in a shifted lattice, which is trivial to count. In quant interviews, Catalan numbers show up whenever you see a "never cross a boundary" constraint on a sequential process. The key mental move is: don't try to count valid objects directly; count everything and subtract the bad ones, using a clever bijection to make the bad ones easy to count.