Number of trees with vertex set $[n]$ and vertex $i$ with $deg(v_i)=d_i$ s.t. $\sum d_i = 2n-2$

Question

If we are given n positive integers $d_1,d_2,...,d_n$ such that $\sum d_i = 2n-2$, then we want to show that the number of trees with vertex set $[n]$ where vertex $v_i$ has degree $d_i$ is exactly $$\frac{(n-2)!}{(d_1-1)!\cdots(d_n-1)!}. $$

Apparently this can be done with Prüfer codes, but I don't know how to approach it with that method - or any other method actually. I tried to make a choice argument, starting off by saying that the first vertex can connect to all others, giving $n-1$ choices, and so on; but I don't actually think that is a valid line of reasoning, and it didn't give me my desired result anyhow. Would anybody be able to show me how we could proceed?

Answer 1

Hint: Use induction on $n$; show that $d_j=1$ for some $j$ and then choose which vertex is the (unique) neighbour of vertex $j$.

---

Full Proof:
For simplicity, denote the number of trees with vertex set $\{v_i:i=1,2,...,n\}$ and $d(v_i)=d_i$ as $T(d_1,d_2,...,d_n)$.
We prove by induction on $n$ that $$T(d_1,d_2,...,d_n)=\frac{(n-2)!}{(d_1-1)!...(d_n-1)!}$$

Base Step: If $n=2$ then $d_1=d_2=1$. There is exactly one tree satisfying the hypothesis, namely $C_2$; so $T(1,1)=1$. Note that $$\frac{0!}{0!0!}=1$$ Hence the claim holds.

Inductive Step: Suppose instead that $n>1$. If $d_i\geq2\;\forall i$ then $d_1+d_2+...d_n\geq2n$ which is a contradiction; thus there exists some $m\in\{1,2,...,n\}$ such that $d_m=1$. Note that rearranging the indices of $d_1,...,d_n$ doesn't change the value of $T(d_1,...,d_n)$, so for semplicity we can just set $d_n=1$.

Now we have $n-1$ choices: we choose some $j\not=n$ and join $v_j$ and $v_n$ by an edge. Now we have $T(d_1,d_2,...,d_j-1,...,d_{n-1})$ ways to pick a tree with vertex set $\{v_i:i=1,2,...,n-1\}$ such that $d(v_j)=d_j-1$ and $d(v_i)=d_i$ for $i\not=j$. Note that by adding the vertex $v_n$ and the edge $v_jv_n$ we get a tree with vertex set $\{v_i:i=1,2,...,n\}$ and $d(v_i)=d_i\;\forall i$.
Thus
$$T(d_1,...,d_{n-1},1)=T(d_1-1,d_2,d_3,...,d_{n-1})+T(d_1,d_2-1,d_3,...,d_{n-1})+...+T(d_1,d_2,d_3,...,d_{n-1}-1)$$ Now we apply the inductive hypothesis to each term in the RHS: $$T(d_1,...,d_{n-1},1)=\frac{(n-3)!}{(d_1-2)!(d_2-1)!(d_3-1)!...}+\frac{(n-3)!}{(d_1-1)!(d_2-2)!(d_3-1)!...}+...$$ $$=\frac{(n-3)!}{(d_1-1)!(d_2-1)!(d_3-1)!...(d_{n-1}-1)!}\cdot((d_1-1)+...+(d_{n-1}-1))$$ $$=\frac{(n-3)!}{(d_1-1)!(d_2-1)!(d_3-1)!...(d_{n-1}-1)!}\cdot((d_1+...d_{n-1})-(n-1))$$ $$=\frac{(n-3)!}{(d_1-1)!(d_2-1)!(d_3-1)!...(d_{n-1}-1)!}\cdot((2n-3)-(n-1))$$ $$=\frac{(n-2)!}{(d_1-1)!(d_2-1)!(d_3-1)!...(d_{n-1}-1)!}$$ Hence $T(d_1,...,d_{n-1},1)=\frac{(n-2)!}{(d_1-1)!(d_2-1)!(d_3-1)!...(d_{n-1}-1)!(1-1)!}$, which concludes the proof.

I hope this was helpful.

Answer 2

The degree of a node is the number of times its label appears in the Prüfer sequence plus one (see the algorithm for converting a Prüfer sequence to a tree at Wikipedia). Thus we need to choose $d_i-1$ terms in the Prüfer sequence of length $n-2$ for label $i$. The number of ways to do this is the multinomial coefficient

$$ \binom{n-2}{d_1-1,\ldots,d_n-1}=\frac{(n-2)!}{(d_1-1)!\cdots(d_n-1)!}\;. $$