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:
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":
But how? I just have no idea. Not even sure where to start. Any suggestions?