1

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?

glion14
  • 63

1 Answers1

1

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.

LogiC
  • 46