I want to calculate $m_n$ - the number of different Motzkin trees (Trees where every node has zero, one or two nodes as children) that contain exactly $n$ nodes. The position of the children should matter, so e.g. a single node with a single right child should not be considered the same Motzkin tree as a single node with a single left child.
Denote the family of all Motzkin trees by $\mathcal{M}$. This structure can be defined by $$\mathcal{M} := \{O\} \cup \{O\} \times \mathcal{M} \cup \{O\} \times \mathcal{M} \times \mathcal{M}.$$ By considering every node should have weight 1, this yields the generating function ($M(z) := \sum_{i = 0}^{\infty} m_n \cdot z^n$) $$ M(z) = \frac{1 - z - \sqrt{1 - 2z - 3z^3}}{2z}.$$ In similar problems I've solved before there was always a rather obvious way to write the function (here $\frac{1 - z - \sqrt{1 - 2z - 3z^3}}{2z}$) as a series and I was able to come to the solution by "reading off" the coefficient $m_n$.
I'm pretty confident my generating function is correct, but can somebody please help me out with the step from $M(z)$ to $m_n$? $m_n$ doesn't have to be in a closed form it could be a sum (or a series?) aswell.
Thank you in advance for any help!
We start with the functional equation
$$M(z) = z + z M(z) + z M(z)^2$$
so that
$$z = \frac{M(z)}{1+M(z)+M(z)^2}$$
We then have
$$n \times m_n = [z^{n-1}] M'(z)$$
and from the Cauchy Coefficient Formula
$$[z^{n-1}] M'(z) = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^n} M'(z) \; dz.$$
Now put $M(z) = w$ so that $M'(z) \; dz = dw$
and we obtain
$$\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w+w^2)^n}{w^n} \; dw.$$
This is
$$m_n = \frac{1}{n} [w^{n-1}] (1+w+w^2)^n = \frac{1}{n} [w^{n-1}] \sum_{q=0}^n {n\choose q} w^q (1+w)^q \\ = \frac{1}{n} \sum_{q=0}^{n-1} {n\choose q} [w^{n-1-q}] (1+w)^q.$$
We thus have for the desired answer
$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{n} \sum_{q=0}^{n-1} {n\choose q} {q\choose n-1-q}.}$$
This will produce the sequence
$$1, 1, 2, 4, 9, 21, 51, 127, 323, 835, \\ 2188, 5798, 15511, 41835, \ldots$$
which points us to OEIS A001006, Motzkin numbers, where we have $A001006(n-1)$.