6
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

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.