= Labelled tree count with prescribed degrees
{title2=$\frac{(n-2)!}{\prod_{v=1}^n(d_v-1)!}$}
For $n\geq2$ and positive integers $d_1,\ldots,d_n$ with $\sum_v d_v=2(n-1)$, the number of <labelled trees> having <vertex degree> $d_v$ at label $v$ is
$$
\frac{(n-2)!}{\prod_{v=1}^n(d_v-1)!}.
$$
By the <Prüfer degree formula>, this is the <multinomial coefficient> counting <sequences> with $d_v-1$ occurrences of each label. If a degree is zero or the sum is wrong, there are no such <trees>. For the example <degree sequence> $(2,1,3,1,2,1)$, there are $4!/(1!0!2!0!1!0!)=12$ <labelled trees>, one for each ordering of the labels $1,3,3,5$. Knowing the <vertex degrees> thus constrains, but usually does not determine, the <tree>.
Back to article page
