K Vertices on a labeled trees

Question

I need to figure out how many labeled trees are there on {1,2,⋯,n} such that vertex 1 has degree k. I have an instinct that some form of n-1 choose k is going to find its way in there but it always get me slightly off. Thanks for any help.

Answer 1

Have you heard of Prufer sequences? I'm guessing this is a "simple" approach. It says we have bijective correspondence between labelled trees on $n$ vertices and length $n-2$ sequences of integers in $\{1,2,\cdots ,n\}$. Look at a few examples very closely and see if you can tell anything about degrees from the Prufer sequences and go from there.