1
$\begingroup$

here's a question I have for homework:

How many trees exist for vertices $ 1 \dots n$ in which 1 is a leaf?

Hint: cut the leaf.

Ok, a function that cuts a leaf is obviously one to one and onto, so like the clue says I'll just cut the leaf. I'm trying to count $T_n(d_1,d_2,\dots ,d_n)$ which is the same number as $\sum_{j=0}^{n-1} T_n(d_1,d_2,\dots ,d_j-1,\dots ,d_{n-1})$ (assuming that the leaf I cut before was connected to vertex $j$.

Am I right so far? How do I continue from here on? I thought about translating the sum to a multinomial coefficient but I'm not sure how to do it.

Thanks

1 Answers 1

1

Do you know Cayley's formula?

After cutting the leaf you remain with a general tree on $2,\dots,n$. Apply the formula to it.

  • 0
    @yotamoo and don't forget to count the number of ways to place node 1 as a leaf..2012-01-22