Catalan Number

When solving this combinatorial problem, I learned a new thing called Catalan number. The problem is to find all isomorphic forms of binary trees using N nodes.

With simple divide and conquer, we can have the form:

F(0) = 1,

F(N) = sigma(0, N-1, F(i)*F(N-1-i))

Actually, F(N)  is indeed the famous Catalan number. Catalan number has closed form representation:

C(N) = (2N, N)

However, it is non-trivial to get the closed form. The proof requires the knowledge of using generating function and non-integer binomial expansion to solve sequence sum. I found great resources of the proof.

http://math.stackexchange.com/…/simplifying-catalan-number-…http://www.cs.nthu.edu.tw/…/algo08-tut…/tutorial-catalan.pdf#catalan_number

 

Catalan number has other interesting applications

TODO

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s