Catalan numbers. Sequence of balanced parentheses. A legal sequence of parentheses is one in which the parentheses can be properly matched (each opening parenthesis should be matched to a closing one that lies further to its right). For instance, $()(())$ is a legal sequence of parentheses.
I should calculate the number of legal sequences of length $2n$. The answer is $C_n = {2n \choose n} - {2n \choose n + 1}$. How can it be proved without recurrence and induction?
 A: ${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}$.  
