Number of labelled trees with exactly 3 leaves

Question

I have seen some relevant questions here about that matter [1], [2] but I am getting a different result and I cannot understand if I am wrong. So the question is:

Find the number of labelled trees on $n\geq 4$ vertices that have exactly $3$ leaves.

This problem can be translated as follows: From the Prüfer code we want to count the number of codewords in which exactly $n-3$ different numbers appear. We know that a Prüfer code for $n$ vertices will have a length of $n-2$. So we have to place $n$ items in $n-3$ positions without repetitions and this can be done in $\frac{n!}{(n-3)!}$ times their permutations ($(n-3)!$) and then we have 1 position to choose from $n-3$ numbers (because we have $3$ leaves) and therefore $\binom{n-3}{1}$ ways to fill that position. So in total we have $\frac{n!(n-3)!(n-3)!}{(n-3)!(n-4)!}=n!(n-3)$ trees with exactly three leaves.

Am I missing something in my enumeration?

Answer 1

You have the right Prufer codes, but you have made some mistakes in counting. It's easy to check your formula doesn't work: for $n=4$ there are $4$ labelled trees with this property, because the tree must be a star and the only choice you have is which label goes in the middle.

First, to choose $n-3$ from $n$ elements in order is $\binom n3\times (n-3)!=\frac{n!}{6}$.

Secondly, when you choose an element to duplicate, you not only need to choose which element is duplicated ($n-3$ options) but also where to put the duplicate ($n-2$ possible places). However, this actually counts each code twice, because it distinguishes the "original" and "duplicate" version of the label that appears twice, meaning you need to divide by $2$.

So overall there are $\frac{n!}{6}\times\frac{(n-3)(n-2)}{2}=\frac{n!(n-2)(n-3)}{12}$ such trees.