Cayley's tree formula proof

Question

I want to prove Cayley's tree formula that The number of distinct trees of order $n$ with a specified vertex set is $n^{n-2}$ using the fact that the number of trees on the set of $n$ vertices $\{1,2,...,n\}$ that the degree of ith vertex is $d_i$ is $\frac{(n-2)!}{(d_1-1)!...(d_n-1)!}$. But I don't know how to reach $n^{n-2}$ from this formula. Would you please help?

Answer 1

In any $n$-vertex tree, we have $d_1 + \dots + d_n = 2(n-1)$ and therefore $(d_1 - 1) + \dots + (d_n - 1) = n-2$. Therefore $\frac{(n-2)!}{(d_1-1)! \cdots (d_n-1)!}$ is a multinomial coefficient that counts the number of $(n-2)$-tuples with $(d_1 - 1)$ $1$'s, $(d_2 - 1)$ $2$'s, and so on through $(d_n - 1)$ $n$'s.

If we sum over all choices of $(d_1, \dots, d_n)$ with $(d_1 - 1) + \dots + (d_n - 1) = n-2$, then we are just counting the number of $(n-2)$-tuples made up of $1$'s, $2$'s, and so on through $n$'s. There are $n^{n-2}$ such tuples: each of $n-2$ positions can have one of $n$ values. Therefore there are $n^{n-2}$ labeled $n$-vertex trees in total.

If you are curious about whether these $(n-2)$-tuples have a further combinatorial meaning, look into Prüfer codes. These are also, incidentally, the easiest way to prove the $\frac{(n-2)!}{(d_1-1)! \cdots (d_n-1)!}$ formula.