A colleague of mine (who is not a mathematician at all) asks me to have a look at his formula for the number $T_n$ of rooted labeled trees on $n$ vertices where the root has degree 2.
He starts out by saying that there are $n^{n-1}$ rooted labeled trees (Cayley's formula https://en.wikipedia.org/wiki/Cayley%27s_formula says that there are $n^{n-2}$ labeled trees, so I assume each vertex can be a root, so the formula above sounds plausible, to start with).
Finally, he arrives at a formula of the form:
$$T_n = n\cdot \sum_{k=1}^{n-2} \binom{n-1}{k}/s\cdot (k^{k-1})\cdot (n-1-k)^{n-2-k},$$
where $s=2,1$ (depending on whether $k=n-k-1$ or not).
Does anyone know more about this? I'm sure that the number $T_n$ is either well-known or easily derivable.
Okay, I'll post an answer myself.
The formula appears to be equivalent to
$$T_n = n\cdot(n-2)\cdot (n-1)^{n-3}.$$
This can be explained as follows. Choose a root (there are $n$ possible choices). Then there are $n-1$ vertices left. Choose a labeled tree on $(n-1)$ vertices: there are $(n-1)^{n-3}$ such trees on $n-1$ vertices. Finally, connect your root to exactly $2$ vertices in the labeled tree as follows:
A tree with $(n-1)$ vertices has $(n-2)$ edges. Choose one of them ($n-2$ choices) and connect its endpoints to the root. That generates the two children of our rooted tree.
The alternative formula can be proven as follows. A rooted labeled tree with root degree $2$ has two subtrees. Each is an unrooted labeled tree. One of the subtrees can have size $k=1,\ldots,n-2$, the other has size $n-1-k$. If it has size $k$, we can choose its elements in $\binom{n-1}{k}$ ways. This also accounts for the elements in the other subtree. Moreover, when it has size $k$ we can connect each of its $k$ nodes to the root, and the same for the other subtree of size $n-1-k$. Finally, we can choose $n$ root nodes.
Hence,
$$T_n = n\cdot \sum_{k=1}^{n-2}\binom{n-1}{k}k\cdot k^{k-2}(n-1-k )(n-1-k)^{n-1-k-2}$$
We note that we have overcounted since the subtrees are indistinguishable. Hence, we have to divide by $2$.
This formula generalizes. If the root vertex has degree $3$, the three subtrees have sizes $x,y,z$ such that $x+y+z=n-1$. The formula becomes
$$T_{n,3} = n\sum_{x+y+z=n-1}\binom{n-1}{x,y,z}x^{x-1}y^{y-1}z^{z-1}$$
Again, we have overcounted, since the subtrees are indistinguishable. We counted all permutations of $(x,y,z)$, so we have to divide by $3!$
After some trying around, we find:
$$T_{n,3} = n\cdot\binom{n-2}{2}\cdot (n-1)^{n-4}$$
and this has a very nice interpretation too!