# Tag Archives: Ballow walks

## 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: