Counting binary trees

combinatoricsdiscrete mathematicsrecurrence-relationstrees

How to get a closed form for the number of different trees possible for a labeled binary tree with $n$ leaves labeled from $1$ to $n$?

I have derived a recurrence formula, but unable to find a way to solve it.

My formula is :

if there are $n$ terminal nodes in the tree, then

T(n)=$\frac{1}{2} \sum_{i=1}^{n-1} \binom{n}{i} *T(i)*T(n-i)$

The result should be a closed form equation, like $T(n)=\frac{(2n – 3)!}{2^{n-2}(n – 2)!}$

It is different from Catalan number.

Explanation:

For $3$ terminal nodes, number of possible trees is $3$. These are :

enter image description here
enter image description here
enter image description here

However following trees are equivalent, and counted only once:

enter image description here enter image description hereenter image description here

Best Answer

You are correct, the closed form solution is $T(n)=(2n-3)!/(2^{n-2}\cdot (n-2)!)$. Another way of writing this is $$ (2n-3)\times (2n-1)\times \dots \times 3\times 1, $$ also written as $(2n-3)!!$.

Here is the proof. Imagine you have a binary tree with $n$ leaves, and you delete the leaf labeled "$n$." The result is now almost a binary tree; the only problem is that one of the internal nodes will have only one children (namely, the node which originally had "$n$" as a child). This can be fixed by "contracting" that internal node. Here is an example when $n=4$:

    __.__            __.__            __.__    
   /     \          /     \          /     \   
  .       .        .       .        .       3  
 / \     / \      / \     /        / \       
1   2   3   4    1   2   3        1   2

Now, imagine the process in reverse. How many ways are there to take a tree $T$ with $n-1$ children, and add in a leaf node labeled $n$? Now you need to choose a node $v$ in $T$, and add an new internal node $w$ just above $T$. The parent of $w$ is the original parent of $v$, and the children of $w$ are $v$ and the new leaf node labeled $n$. Since $T$ has $2n-3$ nodes total ($n-1$ leaves, $n-2$ internal), you can add a new leaf to $T$ in $2n-3$ ways.

We have shown that for every tree with $n-1$ leaves, there are exactly $2n-3$ corresponding trees with $n$ leaves. That is, $$T(n)=(2n-3)\times T(n-1).$$ By induction, this proves that $T(n)=(2n-3)\times (2n-1)\cdots 3\times 1$. Explicitly, every tree with $n$ leaves can be built by adding the leaves number $2$ to $n$ one a time starting from the tree with a single leaf, and there are $2i-3$ ways to add leaf number $i$.

Related Question