1
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ It appears you are talking about unordered trees, in which case the linked question would not be a duplicate. Can you confirm, how many trees should there be when there are $n=3$ terminal nodes? Is it one or two? $\endgroup$ Jun 18 at 17:19
  • $\begingroup$ @ Mike Earnest : Yes, the grouping is not ordered, but the terminal nodes are labelled. For $n$ terminal nodes (say $n1,n2,n3$), total number of binary trees possible, is 3. As I am unable to draw trees in the comment, I am editing my question, to give the 3 trees possible. Also, while giving this explanation, I realize, my recurrence formula is wrong. $\endgroup$
    – Sukti Sen
    Jun 19 at 11:43
  • $\begingroup$ oeis.org/A001190 counts unlabeled binary trees. $\endgroup$ Jun 19 at 12:03
  • $\begingroup$ oeis.org/A002572 also counts binary trees. $\endgroup$ Jun 19 at 12:08
  • 1
    $\begingroup$ I am voting to reopen this question because it should not have been closed; the linked question is not a duplicate, as this question is asking for a proof of a closed form formula. $\endgroup$ Jun 22 at 14:40
2
$\begingroup$

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$.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.