Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am studying for an exam an I came across a question I couldn't answer:

Count the number of labeled trees ($v_i=1...17$ for all $1 \le i \le 17$) with diameter 15

So, I know its just a track of 16 vertices with one leaf connected to one of thm. There are $16!$ different tracks, and $\binom{16}{1}$ options of different ways to connect the left to the track. $\binom{16}{1} \cdot 16!$ is not the right answer, however. The right answer was $$\frac{17!}{2} \cdot 6 \cdot 17!$$ Any ideas where my mistake was? Thanks!

share|improve this question
add comment

1 Answer 1

up vote 1 down vote accepted

First, you want to make a path of $16$ vertices. Since you have $17$ vertices to choose those $16$ vertices from, that gives you ${17 \choose 16} = 17$ ways to choose those $16$ vertices, and then $16!$ permutations of those vertices, giving a total of $17 \cdot 16! = 17!$ paths of length $16$. However, since e.g. the path $1,2,3,\ldots,16$ is the same as the path $16,15,14,\ldots,1$, you have to divide by $2$ for double counting. So that's

$$\frac{17!}{2}$$

different paths of $16$ vertices. Then, you just have to add the last vertex to one of the $14$ middle vertices (not to one of the leaves, as that would give you a path of length $17$ with diameter $16$). For the $12$ vertices furthest from the edges, this simply gives you $12 \cdot 17!/2 = 6 \cdot 17!$ trees. However, if you attach the last vertex to the ones that are next to the leaves, then you will again count solutions twice (since you could have also obtained that tree by using this last vertex as part of the path, and adding the leaf as your last vertex), so you get another $(2 \cdot 17!/2) / 2 = 17!/2$ solutions there, giving a grand total of

$$\frac{17!}{2} + 6 \cdot 17!$$

To answer your question, note that to make a path of $16$ vertices you have $17!$ options instead of the $16!$ you claim, and you cannot add the last vertex to one of the leaves (since then the diameter would be $16$). Also beware of double counting, as I did above.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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