Combinatorics Problem 1

We consider the species $\mathcal T$ of such trees. An object in $\mathcal T$ is either a single node $\bullet$ or a single node followed by two or three trees. Hence the combinatorial construction is $$\mathcal T = \{\bullet \}\text{ } \dot{\cup}\text{ } (\{\bullet \} \times \mathcal T \times \mathcal T)\text{ } \dot{\cup}\text{ } (\{\bullet \} \times \mathcal T \times \mathcal T \times \mathcal T),$$

which translates into the equation $T(z) = z+zT^2(z)+zT^3(z)$ for the generating function $T(z)\in \mathbb C[\![z]\!]$, which is equivalent to $z = \frac{T(z)}{1+T^2(z)+T^3(z)}$. Thus, the compositional inverse of $T(z)$ is $\frac{z}{1+z^2+z^3}$. By Lagrange's inversion formula one gets for the $n$-th coefficient of $T(z)$: $$\frac 1n [\![z^{-1}]\!]\left ( \frac{z}{1+z^2+z^3} \right )^{-n} = \frac 1n [\![z^{-1}]\!] \frac 1{z^n} ( 1+ z^2 + z^3 )^n = \frac 1n [\![z^{-1}]\!] \frac 1{z^n} \sum_{k=0}^n \binom{n}{k} (z^2+z^3)^k = \frac 1n [\![z^{-1}]\!] \sum_{k=0}^n \binom{n}{k} z^{2k-n} (1+z)^k$$ $$= \frac 1n [\![z^{-1}]\!] \sum_{k=0} ^n \sum_{l=0}^k \binom{n}{k} \binom{k}{l} z^{2k-n+l} = \frac 1n \sum_{k=0}^n \binom{n}{k}\binom{k}{n-2k-1} = \frac 1n \sum_{k=0}^n \binom{n}{k}\binom{k}{3k-n+1}$$

The result is the formula we wanted to find.