I found a proof about the number in this site.
In that site the author says that the number of all possible binary trees with n labeled nodes is equal to the number of ways one can make n-1 edges from n nodes. Since each node can have 2 or less edges, number of all possible edges is 2n. So, the number of ways one can choose n-1 edges from 2n possible edges is 2n×(2n−1)×(2n−2)×....×(2n−(n−2))=(2n)!/(n+1)!. And finally merging all permutation trees into one tree gives the number of binary trees with n unlabeled nodes, (2n)!/((n+1)!n!)=2nCn/(n+1).
But, in the middle of the proof I don't get how one can find 1-1 corrospondence between the number of ways of choosing edges and the number of binary trees with n labeled nodes. For example, if n=3, and each node has name 1, 2 and 3, respectively, and I choose left edge and right edge from node 1 in that order, then there are two possible cases:
1
/\
2 3
1
/\
3 2
So, it seems that choosing 2 edges from 6 edges (3 nodes) does not correspond to a specific binary tree.
Can anyone provide me with the mapping rule between the sequence of chosen edges and the corresponding binary tree?