Finding the coefficients of the OGF of unary-binary trees

Question

A unary-binary tree is a plane (unlabeled) tree where each vertex has $0$, $1$, or $2$ descendants. Find the OGF $M(z)$ for a unary-binary tree and show that its coefficients are $[z^n]M(z) = \frac{1}{n}\sum_{k=0}^n \binom{n}{k}\binom{n-k}{k-1}$.

Using the symbolic method I get from

$$\mathcal{M} = \mathcal{E} + \mathcal{Z} \times CYC_{\le 2}(\mathcal{M} - \mathcal{E})$$

directly the functional equation

$$ M(z) = 1 + z (1 + (M(z) - 1) + (M(z) - 1)^2) = z(1+M(z)+M(z)^2).$$

Rewriting this as $M(z) - z(1+M(z)+M(z)^2) = 0$ the quadratic solution formula leads to the ogf

$$ M(z) = \frac{1 - z - \sqrt{1 - 2 z - 3 z^2}}{2 z}. $$

Since by the functional equation we have

$$z = \frac{M(z)}{1+M(z)+M(z)^2}$$

we can use the Lagrange Inversion Formula to obtain

\begin{align} [z^n] M(z) = \frac{1}{n} [z^{n-1}] (1+z+z^2)^n \end{align}

However, I do not get who to proceed from here. Could you please give me a hint?

Answer 1

We obtain \begin{align*} \color{blue}{[z^{n-1}]}&\color{blue}{\left(1+z+z^2\right)^n}\\ &=[z^{n-1}]\sum_{k=0}^n\binom{n}{k}\left(z+z^2\right)^k\tag{1}\\ &=\sum_{k=0}^{n-1}\binom{n}{k}[z^{n-1-k}](1+z)^k\tag{2}\\ &\,\,\color{blue}{=\sum_{k=\lceil \frac{n-1}{2}\rceil}^{n-1}\binom{n}{k}\binom{k}{n-1-k}}\tag{3} \end{align*}

Comment:

• In (1) we use the binomial theorem.

• In (2) we factor out $z^k$ and apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$. We also set the upper limit of the sum to $n-1$, since other summands do not contribute to $[z^{n-1}]$.

• In (3) we select the coefficient of $z^{n-1-k}$. Since $\binom{p}{q}=0$ if $q>p$ we set the lower limit of the sum accordingly.