1
$\begingroup$

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

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?

$\endgroup$
1
$\begingroup$

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.

$\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.