# rooted labeled trees with root degree 2

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.

• I think the formula gives $T_4=48$ but in fact $T_4=24.$ – bof Jul 26 '16 at 9:40
• He has the right idea but seems to be double counting in places. I think you get the right formula if you just set $s=2$ all the time. – bof Jul 26 '16 at 9:43
• The point is the the $k=1$ term and the $k=n-2$ term are counting the same things, likewise the $k=2$ term and the $k=n-3$ term, etc. – bof Jul 26 '16 at 9:44
• That is, I think the correct formula is $$T_n=\frac n2\sum_{k=1}^{n-2}\binom{n-1}kk^{k-1}(n-1-k)^{n-2-k}.$$ – bof Jul 26 '16 at 9:46
• I wouldn't know a reference. I'd look in graph theory books and look at the exercises in the chapter about counting labeled trees. Maybe easier (if it works): calculate the first few values of $T_n$ and search for the sequence at oeis.org. – bof Jul 26 '16 at 9:54

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!

• No, it doesn’t still read the same except for endpoints. You also greatly improved the readability by adding as follows. You might wish to note, by the way, that I had ‘move[d] on’ by deleting my original objection; you prolonged matters by defending a false statement. I’m done here. – Brian M. Scott Jul 26 '16 at 21:41