# Showing two recurrences to be identical

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.

-
Do you have a typo in the recurrence for $t(\cdot)$? It seems that $$t(4;1,1,2,2) = 2 \neq t(3;0,1,2) + t(3;1,0,2) + t(3;1,1,1).$$ – Scaramouche Jan 3 '12 at 19:49
Thanks for pointing that out. I had missed stating that we can take $d_n=1$ without disrupting the definition of $t$. The recurrence actually follows only if we take $d_n=1$. I have edited the question now. – Shahab Jan 4 '12 at 2:05

If we assume that $d_n = 1$ so that $d_n - 1 = 0$, and using the fact that for multinomial coefficients, a $0$ in the bottom will drop out, we can write $$t(n ; d_1, \cdots, d_n)= \binom{ n-2 }{ d_1 - 1, \cdots, d_{n-1} - 1, d_n -1 } = \binom{n-2}{ d_1 -1, \cdots, d_{n-1} - 1 }.$$ From here it is clear that the two recurrences are equal.