0
$\begingroup$

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!

1 Answers 1

1

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.