Tag Archives: Catalan number

Catalan numbers, mirror image and walks enumeration

I always enjoyed seeing short and elegant proofs of theorems that I knew before.
I really enjoy this short proof that number of proper placing of n opening and n closing brackets(n-th Catalan number) is equal to:
C_n = \frac{1}{n+1} {2n\choose n}.

for example, there are 2 ways to properly place 2 opening and 2 closing brackets, out of 6 total ways:

(()), ()(),
())(, )((), )()(, ))((

First, we may transform the problem into one about walks on plane.
If we take (0,0) as a starting position, and assign to ‘(‘ a walk into UP-RIGHT direction, and ‘)’ a walk into DOWN-RIGHT direction, we might encode sequences of brackets. So, encoding of ((())))(() is:
path1
Continue reading

Advertisements