for Binary tree, suppose there is n node, how many different structure can I construct?

Question

Consider a binary tree with n nodes. How many different possible binary trees structures are there?

I tried something like:

n   number of different structure:

1        1
2        4
3        16

so is that 4(n-1) for n >1 ; 1 for n == 1?

Answer 1

The number of different binary trees that can be formed using n nodes is given by the nth Catalan number.

number of nodes (n)   binary trees C(n)  
1                     1  
2                     2  
3                     5  
4                     14   

See:

http://en.wikipedia.org/wiki/Binary_tree
http://en.wikipedia.org/wiki/Catalan_number