<s>[INST] number of ternary trees: finding a recurrent relationship If $t_n$ is the number of ternary trees with n nodes, with $t_0=0$, what would be the convenient manner for finding a recurrent relationship for $t_n$? It is given that $t_1=1, t_2=3, t_3=12$.
A sketch for $t_1, t_2, t_3$ 
https://drive.google.com/file/d/0Bzsj_3-U1ZOhS2dFaFNyWFlGOHFnLXdtdEFxQkYxbl9JRzNR/view?usp=sharing
I had found this link on the stackexchange: https://oeis.org/A001764
my guesswork is that $t_n$ of the form $C_1t_{n-1}+C_2t_{n-2}+C_3t_{n-3}$
 [/INST] Suppose we are interested in  computing a recurrence for the number of
ternary trees  where there  is one  leaf and one  ternary tree  on one
node. This gives the species
$$\mathcal{T} = 
\epsilon + \mathcal{Z}\mathfrak{S}_{=3}(\mathcal{T})$$
This yields the functional equation
$$T(z) = 1 + z T(z)^3$$
which immediately produces the recurrence $T_0 = 1$ and
$$T_n = \sum_{a=0}^{n-1}\sum_{b=0}^{n-1-a} T_a T_b T_{n-1-a-b}.$$
For the closed form we get the integral
$$T_n =
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} T(z) \; dz.$$
Use the functional equation and put $T(z) = w$ to get
$$z = \frac{w-1}{w^3} = \frac{1}{w^2}-\frac{1}{w^3}$$
and $$dz = -\frac{2}{w^3}+\frac{3}{w^4} \; dw$$
to get for the integral (by Lagrange inversion)
$$\frac{1}{2\pi i}
\int_{|w-1|=\epsilon} \frac{w^{3n+3}}{(w-1)^{n+1}} 
w \left(-\frac{2}{w^3}+\frac{3}{w^4}\right) \; dw
\\ = \frac{1}{2\pi i}
\int_{|w-1|=\epsilon} \frac{1}{(w-1)^{n+1}} 
 \left(-2w^{3n+1}+3 w^{3n}\right) \; dw .$$
This evaluates by inspection to
$$-2{3n+1\choose n} + 3{3n\choose n}
=\left( -2\frac{3n+1}{2n+1} + 3\frac{2n+1}{2n+1} \right) 
{3n\choose n}
\\ = \frac{1}{2n+1}{3n\choose n}.$$
Here we have used the fact that
$$w^{3n+1} = \sum_{q=0}^{3n+1} {3n+1\choose q} (w-1)^q
\quad\text{and}\quad
w^{3n} = \sum_{q=0}^{3n} {3n\choose q} (w-1)^q.$$
Addendum. For an alternate recurrence observe that
$$(2n+3) T_{n+1} =
{3n+3\choose n+1}
= \frac{(3n+3)(3n+2)(3n+1)}{(2n+2)(2n+1)(n+1)}
{3n\choose n}
\\ = \frac{(3n+3)(3n+2)(3n+1)}{(2n+2)(n+1)} T_n.$$
This yields
$$T_{n+1} =
\frac{(3n+3)(3n+2)(3n+1)}{(2n+3)(2n+2)(n+1)} T_n
\\ = 3\frac{(3n+2)(3n+1)}{(2n+3)(2n+2)} T_n.$$
</s>