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 opening and closing brackets(-th Catalan number) is equal to:

.

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:

Continue reading

Advertisements