an intuition for $\sum {\frac{(n-2)!}{k_1!k_2!...k_n!}}=n^{n-2}$

Question

in studying about Graphs I've faced to the problem which says that the number of trees on n points is $n^{n-2}$. In the solution manual of the book the problem is reduced to the summation $\sum {\dfrac{(n-2)!}{k_1!k_2!...k_n!}}$ where $k_1,...,k_n \geq 0$ and $k_1+k_2+...+k_n=n-2$. Without any explanation the book says that this summation is equal to $n^{n-2}$ but I can't figure it out. I would be grateful if somebody told me why this equation is true and also gave me a combinatorial intuition of it.

Answer 1

This is simply the multinomial theorem, which says that

$$\sum_{k_1+\ldots+k_n=m}\binom{m}{k_1,\ldots,k_n}x_1^{k_1}\ldots x_n^{k_n}=(x_1+\ldots+x_n)^m\;.$$

Set $x_1=\ldots=x_n=1$ and $m=n-2$, and you have the desired result. There is a proof of the theorem at the link.

Answer 2

The multinomial coefficient $ \dfrac{m!}{k_1! k_2! \ldots k_n!}$, where $k_1 + \ldots + k_n = m$, is the number of ways to label a collection of $m$ objects with $n$ labels where $k_1$ get label $1$, $k_2$ get label $2$, ..., $k_n$ get label $n$. The sum of these is the total number of ways to label $m$ objects with $n$ labels, which is $n^m$.