1
$\begingroup$

What I want is to count the number of binary trees on $n$ nodes, except when a node has only one child, I don't distinguish between left and right. So let $T_n$ be the number of such trees on $n$ nodes, we have

\begin{align*} T_n=\left(\sum_{k=0}^{n-1}T_k\cdot T_{n-k-1}\right)-T_{n-1}. \end{align*}

I am not sure how to solve this recurrence. If we proceed the same way as in counting normal binary trees (where left and right matters when there's a single child) using generating function $g(s)=\sum_{n=0}^\infty T_ns^n$ and squaring it, I get that

\begin{align*} g(s)=\frac{1+s-\sqrt{1-2s-3s^2}}{2s}. \end{align*}

Calculating the series expansion around zero seems to give me what I want, but I cannot get this expression in the form of $\sum_nT_ns^n$ so the quantity $T_n$ comes out...

3 Answers 3

5

This is A086246 in OEIS, but with the index shifted by $1$, and A001006, the Motzkin numbers, with the index shifted by $1$ in the other direction. (That is, $T_{n+1}=M_n$, where $M_n$ is the $n$-th Motzkin number.) The latter reference yields the possibly simpler recurrence

$T_{n+1}=\frac{2n+1}{n+2}T_n+\frac{3n-3}{n+2}T_{n-1}\;,$

the asymptotic formula

$T_n\sim 3^n\sqrt3\frac{1+\frac1{16n}}{(2n+3)\sqrt{(n+1)\pi}}\;,$

and a wealth of references, formulas involving summations, and variant forms of the generating function, but there doesn’t seem to be a nice closed form.

Not so nice closed forms for the Motzkin numbers involving trinomial coefficients, hypergeometric functions, regularized hypergeometric functions and the gamma function, or Legendre polynomials can be found here.

1

Your trees are described by an empty tree or a root linked to a sequence of at most 2 non-empty trees, in symbols: $ \mathcal{T} = \mathcal{E} + \mathcal{Z} \times \mathfrak{S}_{\le 2}(\mathcal{T} - \mathcal{E}) $ This directly gives the functional equation: $ T(z) = 1 + z (1 + (T(z) - 1) + (T(z) - 1)^2) $ This also gives: $ T(z) = \frac{1 - z - \sqrt{1 - 2 z - 3 z^2}}{2 z} $

0

You forgot to mention that there is an implicit assumption in your problem that $T_0=T_1=1$. In this case your Z-transform is correct. Now the question is to invert the Z transform. This is pretty straightforward: \begin{eqnarray} g(s) &=& \frac{1}{2} - \left(\frac{\sqrt{1-2 s-3 s^2}-1}{2 s}\right) \\ &=& \frac{1}{2} - \left(\frac{\sqrt{(1+s)(1-3 s)}-1}{2 s} \right) \\ &=& \frac{1}{2} - \frac{1}{2} \sum\limits_{n=0}^\infty \binom{\frac{1}{2}}{n+1} F_{2,1}\left[\begin{array}{r} -\frac{1}{2} & -n-1 \\ \frac{1}{2} - n \end{array};-3\right] \cdot s^n \end{eqnarray} In the last line we multiplied the respective binomial expansions and then we computed the resulting convolution bu using the definition of the hypergeometric function. Therefore the result reads: \begin{equation} T_n = \frac{1}{2} \delta_{n,0} -\frac{1}{2} \binom{\frac{1}{2}}{n+1} F_{2,1}\left[\begin{array}{r} -\frac{1}{2} & -n-1 \\ \frac{1}{2} - n \end{array};-3\right] \end{equation} Now the result can be further simplified using the theory of hypergeometric functions.