How many labeled trees exist on n vertices with exactly 3 vertices of degree 1? My combinatorics class is covering spanning trees right now and one of the questions being asked is "What is the number of labeled trees on n vertices with exactly $3$ vertices of degree $1$?"

I've tried a couple different ways of doing this and none of them seem to work. I tried examining the degree sequence, looking at the Prüfer code as words from an $[n-3]$ length alphabet, but it seems fruitless. 

Any help would be greatly appreciated. Thanks!

Edit: I mis-read the problem, this was first posted with at least 3 vertices of degree 1, but the actual problem states exactly 3 vertices of degree 1.
Here's a way to find the number.  It looks like it might not be the best (Sloane's A055315 has other formulas), but it works.

Let $n$ be the number of vertices and $e=n-1$ be the number of edges.

Claim: There is exactly one vertex of degree $3$, all others have degree $2$ or $1$.  (Assume otherwise, and we violate the Handshaking Lemma, which stipulates the sum of degrees is $2e=2(n-1)$.)

So, the trees look like this:



If we delete the degree-$3$ vertex, we obtain three components.  These three components only have vertices of degree $1$ and $2$, and so must be paths.  Suppose the paths have $a$, $b$ and $c$ vertices.  Then $a+b+c=n-1$ and $a,b,c$ are all positive integers.  Conversely, given three paths of lengths $a \geq 1$, $b \geq 1$ and $c \geq 1$ and $a+b+c=n-1$, we can join their endpoints to a new vertex to create an $n$-vertex tree with exactly three $3$ leaves.

Let $a(n)$ be the number of partitions of $n-1$ into $3$ non-zero parts; this is equivalent to Sloane's A001399 which includes the formula $$a(n)=1+\left\lfloor\frac{(n-1)^2+6(n-1)}{12}\right\rfloor$$ among others.

Given an unlabeled tree, we can label the vertices in $n!$ (not necessarily distinct) ways.  In this way, we generate $a(n)\ n!$ labeled trees.

In some cases (not many), there are symmetries which need to be accounted for.  Because of symmetry, in this case



we count every labeling twice.  This happens whenever $\{a,b,c\}$ have two parts of the same size.

And in this case



we count every labeling six times.  This happens when $\{a,b,c\}$ has all three parts of the same size.

In these cases, we'll need to add a correction.


In the first case: we subtract $$\sum_{a \geq 1:n-1-a \text{ is even and } \geq 2} \tfrac{1}{2}n!=\frac{\lfloor (n-2)/2 \rfloor\ n!}{2}$$ since we have double-counted the $\frac{1}{2} n!$ graphs with $b=c=\tfrac{n-1-a}{2}$.
In the second case: if $n-1 \equiv 0 \pmod 3$, we first "uncorrect" the first correction, so we add back in $\tfrac{1}{2}n!$ and then subtract $\frac{5}{6}n!$ since we originally counted six times the $\frac{1}{6} n!$ graphs with $a=b=c$.


This gives $$\begin{cases} a(n)\ n!-\tfrac{\lfloor (n-2)/2 \rfloor\ n!}{2} &amp; \text{if } n-1 \not\equiv 0 \pmod 3 \\ a(n)\ n!-\tfrac{\lfloor (n-2)/2 \rfloor\ n!}{2}+\tfrac{1}{2}n!-\tfrac{1}{6} n! &amp; \text{if } n-1 \equiv 0 \pmod 3. \end{cases}$$ in agreement with Sloane's A055315.
In fact, the problem can be solved by Prufer code only. Consider first we choose $3$ nodes, they are not in Prufer code and there are $C(n,3)$ ways to choose. Then for last $n-3$ nodes, they must be in the code. It's easily to find that only one of them show 2 times and the other shows exactly one times. Then we can choose the position for the 2 times' number , there are $(n-3)C(n-2,2)$ ways, for the last $n-4$ numbers, we have $(n-4)!$ ways to arrange them.
As all above, we have $C(n,3)(n-3)C(n-2,2)(n-4)!$ such trees.
You can simplify the result, it is same to the other answers.