Take the 2-minute tour ×

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

share|improve this question

3 Answers 3

up vote 5 down vote accepted

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


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.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

Your Answer


