# Thread: The number of possible binary trees with n nodes

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

$\displaystyle 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":

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

But how? I just have no idea. Not even sure where to start. Any suggestions?

2. 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.

3. You can find a derivation here:

Catalan number - Wikipedia, the free encyclopedia

(Five derivations, actually.)

,
,
,

,

,

,

,

,

,

,

,

,

,

,

# number of all posible binary tree with 4 node is

Click on a term to search for related topics.