2
$\begingroup$

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.

  • 0
    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.2012-01-04

1 Answers 1

1

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.