# Counting binary trees

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 :

However following trees are equivalent, and counted only once:

• 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? Jun 18 '21 at 17:19
• @ 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. Jun 19 '21 at 11:43
• oeis.org/A001190 counts unlabeled binary trees. Jun 19 '21 at 12:03
• oeis.org/A002572 also counts binary trees. Jun 19 '21 at 12:08
• 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. Jun 22 '21 at 14:40

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