Suppose i have 1 nodes hence total number of binary trees is 1.Suppose i have 2 nodes then total number of binary trees is 2.Then suppose i have 3 nodes then total number of binary trees is 5.
How to prove that for n nodes it is equal to Catalan number i.e total number of unlabelled binary tree with node n is $(2n)! / (n+1)!n!$.Please provide some easy explanation of derivation since derivations on web seems either little vague or incomplete .
For more information of what i am talking about see the article https://www.geeksforgeeks.org/enumeration-of-binary-trees/
Best Answer
So let $F(n)$ be the number of unlabeled binary trees with $n$ nodes. I will show that $F(0)=1$ and $F(n)=\sum_{i=0}^{n-1}F(i)F(n-i-1)$ for all $n\geq1$. You can then consult the excellent explanation of why the closed form of that recurrence relation is $\frac{1}{n+1}\binom{2n}{n}$.
So our tree has a root and a left child and a right child. (If a child doesn't exist, I will consider it a child with zero nodes.)
Suppose that the left child is the root of a tree with $i$ nodes. Then the right child would have to be the root of a tree with $n-i-1$ nodes, since the total of the nodes in those two trees plus the root of our tree must equal $n$. We've decided that there are $F(i)$ possible trees that can be made from $i$ nodes to be rooted at the left child and $F(n-i-1)$ possible trees that can be made rooted at the right child. So the total number of rooted trees that have $i$ nodes on the left and $n-i-1$ nodes on the right is $F(i)F(n-i-1)$.
Of course, the number of nodes on the left side can vary anywhere from $0$ to $n-i-1$ nodes, so the grand total number of rooted trees with $n$ vertices is $$F(n)=\sum_{i=0}^{n-1}F(i)F(n-i-1).$$To give us an initial point for this recursion, we note that there is only one binary tree with zero nodes (the empty tree), so $F(0)=1$.
I think the easiest way to believe the proof is to just try drawing all of the binary trees with up to four nodes. The numbers aren't too big, $F(1)=1$, $F(2)=2$, $F(3)=5$, and $F(4)=14$. At each step, make sure you have all of them before going on to the next one, and at each step notice how each of the trees is built from left and right trees of different sizes and how that is built off of the formula.