# 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?

• Thanks will keep it in mind Nov 9, 2018 at 13:24

$${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}$$.