Problem: Find the number of trees on $2m$ given vertices in which all vertices have degree $1$ or $3$.
My attempt: We know that for a tree $T$, we have $2(n-1) = \sum _ { v \in T } d ( v )$, with $n$ the number of vertices and $d(v)$ the degree of a vertex $v$. We can call $n_k$ the number of vertices of degree $k$. Hence we have that $$2(n_1+n_3-1)=n_1+3n_3$$
and $$2m=n_1+n_3$$.
From this we can conclude that either $n_1$ and $n_3$ are both even, or both odd. Now we also now that $n_3=n_1-2$. One can easily check an example, with $n_1=3, n_3=3-2=1, n_1+n_3=2\cdot 2$, we do have a star graph with 3 leaves and a center of degree 3.
My question: now I have a formula to draw such trees, but I don't have the number of trees for a given $2m$ vertices. Maybe I could calculate the number of pairs $(n_1, n_3)$ such that the sum is even. Can someone help me conclude?
Best Answer
Using Pruefer codes we have that the leaves of degree one do not appear in the code at all. Therefore the code consists of two appearances of all nodes of degree three. As the length of the code is $2m-2$ there are $m-1$ such nodes. Hence we choose these, and select two slots for each in turn, proceeding in order. This yields
$${2m\choose m-1} \frac{(2m-2)!}{2^{m-1}}.$$
This gives the sequence
$$1, 4, 90, 5040, 529200, 89812800, 22475653200, \\ 7791559776000, 3576325937184000, 2100278686746240000, \ldots$$
which points us to OEIS A274056 where these values are confirmed.