# Number of rooted trees

Compute the number $$t_n$$ of rooted trees with n nodes described by the following equation:

We know that we cannot construct such tree for all $$n$$ (where $$n$$ is natural number).

For example, we can construct trees for $$n's$$ based on formula above:

$$n=7$$

$$n=7+2*7$$

$$n=7+2*7+4*7$$

$$n=7+2*7+4*7+8*7$$

How can I compute $$t_n$$ for arbitrary n?

You can solve this by defining your $$T$$ as a functional equation for a generating function $$T(z)$$ and then compute $$t_n$$, which is the $$n^{th}$$ coefficient of $$T(z)$$. This will give you all possible combinations of the trees with $$n$$ nodes.

Solving the functional equation

$$T(z) = z^4 + z^2 * T(z)^2$$

gives you

$$T(z) = \frac{1 - \sqrt{1-4z^6}}{2z^2}$$

The only thing left now is to compute:

$$t_n = [z^n]T(z)$$

From here on I think it is clear what to do. The only thing tricky left is the $$z^6$$ under the square root, which can be dealt with by substitution.