15
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Thanks will keep it in mind $\endgroup$ Commented Nov 9, 2018 at 13:24

1 Answer 1

26
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ I just want to say a big "Thank you" 4 years later, because I searched extensively and this is the only comprehensive explanation of the problem, that I found. The up/right movement formulation of the problem is easier, because you can visually see the bijection. Thus, I had a hard time "translating" it into a solution for the bracket formulation. $\endgroup$ Commented Dec 7, 2022 at 14:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .