I'm a bit stuck on this practice problem. Any help on how to solve it would be great. Thanks.

We will see that the generating function for ordered binary rooted trees is $T(x) = 1 + xT(x)^2$

i. Use the quadratic formula to find the two possible generating functions for T(x).
ii. Use coefficient extraction to determine which generating function is correct

  • $\begingroup$ Solve for $y$ in $y=1+xy^2$ and then try to compute taylor expansion of a square root you will get. $\endgroup$ – Phicar Oct 19 '16 at 17:17
  • $\begingroup$ I can get the two formulas by solving for y, but I'm still not sure where to go from there $\endgroup$ – PCR Oct 19 '16 at 17:56
  • $\begingroup$ Use differentiation, you should look a little bit about Taylor expansion. $\endgroup$ – Phicar Oct 19 '16 at 18:34

From your quadratic formula you can deduce $T(x) = \frac{1 \pm \sqrt{1 - 4 x}}{2x}$, solving (i). Which leaves the question, what sign to use (ii).

Luckily, we know the first terms of the genreating function $T(x)$: There is one tree without nodes and one tree with one node. This yields

$$T(x)= 1 + 1x + \ldots.$$

So the constant term should be $1$. But the constant term is $T(0)$. However, because of the fraction we cannot simply evaluate at $0$ but we may multiply the equation by the denominator. So we get

$$2x T(x) = 1 \pm \sqrt{1 - 4x} \; \Rightarrow \; 0 = 1 \pm \sqrt{1 - 0}.$$

Where the left equation is only true for $-$. Finally, we get

$$T(x) = \frac{1 - \sqrt{ 1 - 4x}}{2x}.$$

If you want to find the Taylor expansion of this expression, please refer to the first proof on the Wikipedia-Page of the Catalan numbers.


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.