I am trying to prove Cayley's formula for number of labelled trees on n vertices using multinomial coefficients.
The multinomial coefficient satisfies the recurrence: $\tbinom{n}{r_1,\cdots r_k}=\sum_{i=1}^{k}\binom{n-1}{r_1\cdots r_{i}-1\cdots r_k}$. The $r_i$'s are nonnegative numbers whose sum is $n$.
Suppose $t(n;d_1\cdots d_n)$ is the number of labeled trees on $n$ vertices with degrees $d_i$ for the $i$th vertex. Since the value of $t(n;d_1\cdots d_n)$ depends only on the multiset of numbers $d_i$ and not on their order so we may assume that $d_1\ge \cdots \ge d_n$ and hence $d_n=1$. It can now be proved that
$t(n;d_1\cdots d_n)=\sum_{i=1}^{n-1}t(n-1;d_1\cdots d_i-1\cdots d_{n-1})$
Now given that $t(n;d_1\cdots d_n)=\binom{n-2}{d_1,\cdots,d_n-1}$ for $n=3$ my book says that as the two satisfy the same recurrence relation this holds for all $n$.
My question is that I dont exactly see the two recurrences to be the same. It may be a silly point but shouldn't the second recurrence be $t(n;d_1\cdots d_n)=\sum_{i=1}^n t(n-1;d_1\cdots d_i-1\cdots d_n)$ to match with the first recurrence. But that doesnt even make sense according to the definition of $t$. Can someone explain?
Thanks a lot.