[Math] finding the formula for nth catalan number as total number of combinations of balanced n pair parenthesis.

catalan-numberscombinatoricspermutations

Catalan numbers can be defined in lots of ways. One of those ways is:
(nth Catalan number) Cn counts the number of expressions containing n 
pairs of parentheses which are correctly matched:

for example for n = 3, C_n = 5 
((()))   ()(())     ()()()     (())()     (()())

This wiki article gives a nice formula for $C_n$:

C_n = ((2n)!/(n!n!)) / (n+1)  where n = number of pairs of parentheses.

I wanted to figure out the value of C_n by finding all balanced expressions by n 
pairs of parentheses.
So, we have 2n parentheses which creates (2n)! arrangements out of which we have n 
identical open parentheses and n closed parentheses so we divide by n!*n!.
Total unique arrangements would be (2n)!/(n!n!) but not all of them are balanced.

So how does dividing by n+1 solves the problem?

Best Answer

I would write out a solution but Wikipedia already has a really nice write-up of the same proof: https://en.m.wikipedia.org/wiki/Catalan_number#Third_proof

Here, they use paths instead of parentheses, but it's very easy to transition between the two. Whenever you move right one step, that's like an open parenthesis, whenever you move up, that's a close parenthesis.

In this way, avoiding violations means at any point in the parenthesis sequence you never have more close parentheses than open, and so you never have more up moves than right moves. It is now easy to see how that is analogous to the path never crossing the middle diagonal.

As for why the exceedance goes down by one, the transform described is analogous to basically taking an open parenthesis that came too late and moving it to the front, thus resolving one of the pairs of parentheses that posed a problem.

Related Question