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 just want to make sure i had this question right:

Count the number of trees on the set of vertices $V=\{1,...,12\}$ where $d(1)=d(2)=5,d(3)=3,d(4)=d(5)=...=d(12)=1$

*$d(1)=$ degree of $v_1$

What I did was to draw a graph according to these requirements and then write down the matching Prüfer sequence, which was (in my case alone of course) 3312222111. And so I was looking for the number of sequences of length 10 that has 4 2's, 4 1's and 2 3's and I got $$\binom{10}{4} \cdot \binom{6}{4} \cdot \binom{2}{2}=3150$$

Two questions:

  1. Did I get it right?
  2. Is there an easier way?

Thanks!

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

The answer appears to be correct. I got it by a completely different analysis. Vertices $3$ through $12$ are leaves, so the interval vertices are $1,2$, and $3$, and they must form a tree after all the leaves have been removed. This can happen in just three ways: $1-2-3$, $1-3-2$, or $2-1-3$. (The other six permutations are simply the reversals of these.) If vertex $3$ is in the middle, it gets one leaf, and the remaining eight leaves are split equally between vertices $1$ and $2$. If vertex $1$ or $2$ is in the middle, vertex $3$ gets two leaves, the middle vertex gets three, and the remaining internal vertex gets the other four. Thus, there are

$$9\binom84+2\binom92\binom73=9\cdot70+2\cdot36\cdot35=630+2520=3150$$

possible labelled trees satisfying the condition on the degrees.

Your approach may be more efficient in general; mine works well here because there are so few internal vertices.

share|improve this answer
    
That's nice, thanks –  yotamoo Mar 12 '12 at 9:53
add comment

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.