Catalan numbers. Sequence of balanced parentheses.

Solution 1:

${2n\choose n}$ counts the total number of collections of $n$ left and $n$ right parentheses. So if we can show that ${2n\choose n+1}$ is the number of ways to write those $n$ left and $n$ right parentheses in a way that is not legal, then we are done.

Note that a sequence is legal if when we read from left to right, we have always encountered at least as many left parentheses as right parentheses. Suppose a sequence $L$ is not legal. Then there is a least $k$ where there is a right parenthesis at position $k$ and equally many left and right parentheses before $k$ ( necessarily $\frac{k-1}{2}$ ). Now swap all left parentheses for right and all right for left in the first $k$ positions of $L$. This gives us a collection of $n+1$ left parentheses and $n-1$ right parentheses.

Conversely, let us say we are given a sequence $M$ of $n+1$ left parentheses and $n-1$ right parentheses, and let $k$ be the first position where there are more left parentheses up to that point than right. Flipping those parentheses gives us back a sequence of $n$ left parenthese and $n$ right parentheses that is not legal, because there are more right parentheses up to $k$ than left.

It should be clear that the second map and the first are inverses. Therefore, the number of illegal sequences of $n$ left and $n$ right parentheses is equal to the number of sequences, legal or not, of $n+1$ left and $n-1$ right parentheses, which is ${2n\choose n+1}$.

Therefore the number of legal sequences of parentheses is ${2n\choose n} - {2n\choose n+1}$.