How many distinct unlabeled binary trees with i leaves?

Question

I've been reading a paper that claims: The number of distinct unlabeled binary trees with i leaves is: $$ \frac{1}{2i-1}{2i-1 \choose i} $$ I cannot figure out the reason why . Can someone help me explain that ? Thanks!

Answer 1

I’m assuming that what you’ve written is a typo for

$$\frac1{2i-1}\binom{2i-1}i\;,$$

and that your definition of binary tree requires that each non-leaf have exactly two children, i.e., that you’re talking about what I would call a full binary tree. In that case a binary tree with $i$ leaves has $2i-1$ nodes altogether, and the root is identifiable as the only node of degree $2$. The $i-1$ internal nodes, with the root identified as such, may be any rooted binary tree with $i-1$ nodes, where I use the term rooted binary tree to mean a rooted tree in which each node has at most $2$ children. Conversely, every rooted binary tree with $i-1$ nodes can be extended uniquely to a full binary tree with $2i-1$ nodes by adding the minimum set of leaves required to make each of the original $i-1$ nodes an internal node of the larger tree. Thus, the number of full binary trees with $i$ leaves is the same as the number of rooted binary trees with $i-1$ nodes.

Let the number of rooted binary trees with $i$ nodes be $b_i$. Each such tree has a left subtree with some number $\ell$ of nodes, $0\le\ell\le i-1$, and a right subtree with $i-1-\ell$ nodes. The left subtree can be any of the $b_\ell$ rooted binary trees with $\ell$ nodes, and the right subtree can be any of the $i-1-\ell$ rooted binary trees with $i-1-\ell$ nodes. Thus,

$$b_i=\sum_{\ell=0}^{i-1}b_\ell b_{i-1-\ell}\;.\tag{1}$$

Moreover, it’s clear that $b_0=1$: the unique rooted binary tree with no nodes is the empty tree. The recurrence $(1)$ with initial condition $b_0=0$ is well-known to characterize the Catalan numbers, so $b_i=C_i$, the $i$-th Catalan number. The Catalan numbers have the closed form

$$C_i=\frac1{i+1}\binom{2i}i\;,$$

so the number of full binary trees with $i$ leaves is

$$b_{i-1}=C_{i-1}=\frac1i\binom{2i-2}{i-1}=\frac1{2i-1}\binom{2i-1}i\;.$$