0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think the formula gives $T_4=48$ but in fact $T_4=24.$ $\endgroup$ – bof Jul 26 '16 at 9:40
  • $\begingroup$ 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. $\endgroup$ – bof Jul 26 '16 at 9:43
  • $\begingroup$ 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. $\endgroup$ – bof Jul 26 '16 at 9:44
  • 1
    $\begingroup$ 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}.$$ $\endgroup$ – bof Jul 26 '16 at 9:46
  • 1
    $\begingroup$ 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. $\endgroup$ – bof Jul 26 '16 at 9:54
0
$\begingroup$

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!

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Brian M. Scott Jul 26 '16 at 21:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.