2

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?

David Johns
  • 139
  • 1
    Your question is unclear - the title refers to unlabelled nodes, but the question text talks about labelled nodes? which one do you want? – Siddharth Bhat May 01 '16 at 12:57
  • @SiddharthBhat I want unlabelled one, but in the steps of proof it uses labelled binary tree. And I don't understance that part of the proof clearly. – David Johns May 01 '16 at 13:02

1 Answers1

-1

As per my understanding, an edge is defined by combination of nodes. Like in the example you mentioned (1,2) and (1,3) are two edges So if you are choosing (1,2) to be the left edge, you cannot switch the nodes. So it is corresponding to one binary tree only.

Harsh Rohila
  • 101