0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ It seems that your intuition that it had to do with Catalan numbers was correct. According to one of the answers on the linked question above, for $n+1$ leaves, the number of different trees possible is the $n^{\text{th}}$ Catalan number. I don't know how to derive that, though, although it might be explained in the link above. $\endgroup$ – Noble Mushtak Apr 21 '16 at 18:20
  • $\begingroup$ Hint: Every tree is either a single leaf or a root with two subtrees. If $f(x)$ is the generating function this means $f(x) = x + f(x)^2$... $\endgroup$ – Jair Taylor Apr 21 '16 at 20:10
1
$\begingroup$

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

$\endgroup$

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.