Find number of trees where $$ \forall{v}, \text{ }\deg(v) \in \left\{1,3 \right\} $$ Generally I have idea for recurrence there:
$$t_n = n\left( t_{n-1} + \sum_{a,b,c \in \mathbb{Z_+} \wedge a+b+c = n-3} t_a t_b t_c \right) $$
but it is too hard to solve so there is probably tricky observation which could help to write a explicit pattern for that.
Suppose the tree has $n$ vertices, $k$ of which are of degree $3$. By the Handshaking Lemma, $$3k+(n-k)=2(n-1)\implies k={n-2\over2}$$ so $t_n=0$ if $n$ is odd.
I had originally thought that there would only be one isomorphism class when $n$ is even, but this isn't so. I had just tried very small examples.
I still don't have a full solution, but here's another idea. Suppose T is an admissible tree. Call the subgraph of T induced by all the vertices of T the "$3$-subgraph" of T. If G is the $3$-subgraph of T, then G is a tree of maximal degree $2$. Furthermore there is only one way to get from G to an admissible tree whose $3$-subgraph is G; attach a leaf to each vertex of degree $2$ and two leaves to each vertex of degree $1$.
If I'm not mistaken, when $n$ is even, this shows that $t_n$ is the number of trees on ${n-2\over2}$ vertices with maximum degree $3$. Not sure if this helps, though.
EDIT I used nauty to calculate the number of $3$-valent trees on $n$ vertices for $n=1,\dots,20$ and plugged the result into OEIS to find A000672. The "formulas" given on the page seem way too complicated to come up with during an exam. Perhaps we're supposed to be counting labeled trees rather than isomorphism classes?