Problem with proving Catalan number

Question

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?

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.