Find a recurrence relation and associated generating function for the number of different binary trees with n leaves.
I'm learning about recurrence relations, and I'm struggling more with defining my recurrence relation than solving it.
My gut tells me that the recurrence relation has something to do with the Catalan numbers. Is that the case? If so (or not so), can you explain how you come up with the recurrence relation?
I can answer your second question about the generating function.
The recurrence equation is
$$B_n = \sum_{i=0}^{n-1}B_iB_{n-i-1}$$
If you count the number of different binary trees with a few leaves, or use the above recurrence relation for the first terms you would get $1, 1, 2, 5, 14, 42$ etc. and the generating function for the binary tree with $n$ leaves or the catalan numbers would be
$$C(x) = 1 + x + 2x^2 + 5x^3 + 14x^4 + 42x^4...$$
And we want to find a closed form for this.
Now we multiply $C(x)$ with it self:
$$C(x)^2 = 1 + 2x + 5x^2 + 14x^3...$$
Now
$$C(x) - 1 = x(1 + 2x + 5x^2+ 14x^3...)$$
And you recognize $C(x)^2$ inside the parenthesis.
$$C(x) - 1 = x \cdot C(x)^2$$
or
$$x \cdot C(x)^2 - C(x) + 1 = 0$$
and
$$C(x) = \frac{1 \pm \sqrt{1 - 4x}}{2x}$$
And it turns out that
$$C(x) = \frac{1 - \sqrt{1 - 4x}}{2x}$$
is the generating function.
You can use taylor series on this expression and arrive at
that the coefficients are
$$B_n = \frac{1}{n+1}\binom{2n}{n}$$
So the number of binary trees with, say, $50$ leaves would be
$$B_{50} = \frac{1}{50+1}\binom{2 \cdot 50}{50}$$