Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
Check this for a good explanation :www-math.mit.edu/~djk/18.310/18.310F04/parentheses.pdf –  Torsten Hĕrculĕ Cärlemän Jul 25 '13 at 19:53
    
@TorstenHĕrculĕCärlemän The link doesn't work –  udiboy Jul 25 '13 at 19:54
    
Proved what? ${}$ –  Qiaochu Yuan Jul 25 '13 at 19:55
    
@QiaochuYuan, should have said "derived it". sorry... –  udiboy Jul 25 '13 at 19:56
1  
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$. –  Brian M. Scott Jul 25 '13 at 19:57
show 2 more comments

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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