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.
Best Answer
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} & \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! & \text{if } n-1 \equiv 0 \pmod 3. \end{cases}$$ in agreement with Sloane's A055315.