Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.