The number of possible binary trees with n nodes

Printable View

February 5th 2011, 06:51 PM
RespeckKnuckles

The number of possible binary trees with n nodes

If T(n) is the total number of binary tree configurations with n nodes (so T(0) = 1, T(1) = 1, T(2) = 2, T(3) = 5, T(4) = 14. This is pretty easy to conceptualize, if you imagine that for a binary tree with n nodes, the root has two subtrees which can have 0 to n-1 nodes. So the total number of possible trees is:

$T(n) = \sum_{i=0}^{n-1} T(i)T(n-1-i)$

That much I've figured out. The problem now is how to find a closed-form solution for T(n). After calculating some numbers I've found that the sequence matches the "catalan sequence":

$\frac{(2n)!}{n!(n+1)!}$

But how? I just have no idea. Not even sure where to start. Any suggestions?
February 5th 2011, 08:18 PM
RespeckKnuckles

Guess I spoke too soon. The recurrence relation I derived turns out to be an alternate definition of the catalan numbers, which I think should be sufficient. I still would be curious to see a derivation from the recursive definition to the closed form (factorial) equation, though. If anyone knows how to do that please let me know.
February 6th 2011, 05:33 AM
awkward

You can find a derivation here:

Catalan number - Wikipedia, the free encyclopedia

(Five derivations, actually.)