medium Probability

Proper Parenthesization

A release-checked medium problem for training Combinations and Permutations, Recurrence Relations.

Question

Fix $n \geq 1$. We define a $\textit{proper parenthesization}$ of length $2n$ as a string of $($ and $)$ such that there are $n$ $($ and $n$ $)$ in the string and the number of $)$ never exceeds the number of $($ at any point. For example, with $n = 3$, $()()(), ((())),$ and $()(())$ are valid, while $())(()$ and $(((())$ are not valid. How many proper parenthesizations of length $2n$ are there? Solve this when $n = 6$.

Practice focus

This Probability problem is tagged Combinations and Permutations, Recurrence Relations. State the random variables and conditioning information explicitly, then check the result against boundary cases before opening hints or a solution.