This is how my professor derived it:

Taking the case of all valid arrangements of $n$ '(' and $n$ ')', he says that for every invalid arrangement, there will be a ')' at some $k^{th}$ position where the condition that number of '('s exceeds the number of ')'s is invalidated.

Then we can say that by switching all '(' with ')' and vice-versa after this $k^{th}$ position, we will get a bijective mapping to all possible permutations of $n-1$ '(' and $n+1$ ')'.

It is obvious that this is a one-one mapping, but I don't understand how this is an onto or exhaustive mapping? Why will we get every possible permutation of $n-1$ '(' and $n+1$ ')' by doing this?

  • 1
    $\begingroup$ Check this for a good explanation :www-math.mit.edu/~djk/18.310/18.310F04/parentheses.pdf $\endgroup$ Jul 25, 2013 at 19:53
  • $\begingroup$ Proved what? ${}$ $\endgroup$ Jul 25, 2013 at 19:55
  • $\begingroup$ @QiaochuYuan, should have said "derived it". sorry... $\endgroup$
    – udiboy1209
    Jul 25, 2013 at 19:56
  • $\begingroup$ Derived what? ${}$ $\endgroup$ Jul 25, 2013 at 19:56
  • 1
    $\begingroup$ I suspect that Qiaochu was actually asking what you meant by ‘it’. I assume that you mean the formula $C_n=\frac1{n+1}\binom{2n}n$. $\endgroup$ Jul 25, 2013 at 19:57

1 Answer 1


Just show that the operation is invertible: if you start with a string of $n-1$ left and $n+1$ right parentheses, you can reconstruct the string of $n$ left and $n$ right parentheses from which it came. In fact, you can do it by applying the same operation.

Start with any string of $n-1$ left and $n+1$ right parentheses. Since you have more right than left parentheses, there must be a first index $k$ at which the number of right parentheses is greater than the number of left parentheses. If there are $\ell$ left parentheses up to that point, there must be $\ell+1$ right parentheses. Thus, after that point there are $n-1-\ell$ left and $n+1-(\ell+1)=n-\ell$ right parentheses.

Starting at index $k+1$ change every left parenthesis to a right parenthesis and vice versa. Now there are $n-\ell$ left and $n-1-\ell$ right parentheses after position $k$. There are $\ell$ left parentheses up through position $k$, so there are altogether $\ell+(n-\ell)=n$ left parentheses in the new string. Similarly, there are $(\ell+1)+(n-1-\ell)=n$ right parentheses in the new string. And you can easily check that if you apply the operation to this string, you’ll get back the string of $n-1$ left and $n+1$ right parentheses with which you started.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.