# Solving a recurrence related to tree counting

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

-

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.

-

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}$$

-

Related question here: http://stackoverflow.com/questions/3042412/with-n-no-of-nodes-how-many-different-binary-and-binary-search-trees-possib Formula provided as a solution: $$\frac{(2n)!}{(n+1)!n!}$$

Note: meant this as a remark but posted as a answer to make use of the formula editor.

-