# Counting trees of labled graphs

Here's a question we got as a homework assignment:

Calculate the number of trees for a graph of n labeled vertices in which the degree of $v_1$ is $k$. Hint: Use the formulas for the multinomial coefficients.

I have no idea where to start here, so any (more) hints would be great. Thanks!

This time

-

A tree with two leaves is a path, no? So the 1st question asks for the number of paths on $n$ labeled vertices. A path that uses all $n$ vertices is the same as a permutation of the $n$ vertices, and I think you know how many of those there are, and it's a lot more than $n$-choose-2. It's not clear to me from the wording whether you're also supposed to count shorter paths.

-
No, just the number of trees. Where is my mistake? Could it be that a relation between degree sequences and trees is not one to one? – yotamoo Jan 24 '12 at 11:22
"No, just the number of trees." But a path is a tree, right? Anyway, suppose you have 3 vertices; a, b, and c. Then the paths/trees a-b-c, b-c-a, and c-a-b all have the same degree sequence 1, 1, 2, according to my understanding of the terminology. – Gerry Myerson Jan 24 '12 at 11:57
So, yes that was my mistake. $n!$ it is then. Do you have any idea regarding the second question? Thanks anyway! – yotamoo Jan 24 '12 at 12:21

Maybe I am misunderstanding your question, you mean you want to count the number of labeled trees on $n$ vertices for which node 1 has degree $k$, right?

Remember that if $f(d_1,d_2,..,d_n)$ is the number of trees in which node $1$ has degree $d_1$ , ..., node $n$ has degree $d_n$ (*) then we have $f(d_1,..,d_n) = \frac{(n-2)!}{(d_1-1)!\cdot .. \cdot (d_n-1)!}$ . This fact can be proved by induction (in the inductive step remember that every tree must have a leaf).

Apply the multinomial theorem to derive a formula for $F(x_1,..,x_n) = \displaystyle\sum_{d_1+d_2+..+d_n = 2\cdot n - 2 ; d_i \geq 1} f(d_1,..,d_n)\cdot x^{d_1}\cdot ..\cdot x^{d_n}$

Here read off the coefficient of $x_1^{k}$ (to force the degree of that vertex) and evaluate it at $x_2=x_3=...=x_n=1$ to get your answer.

(*) We must have $d_i \geq 1$ and $\sum_{i=1}^n d_i = 2\cdot (n - 1)$.

-

There is an easy solution with Prüfer sequences. The trees we need to count are the ones which have $v_1$ exactly $k-1$ times in the Prüfer sequences. That means we have to count sequences of length $n-2$ consisting of numbers from $1$ to $n$ with $1$ appearing exactly $k-1$ times. This should be $$\binom{n}{k-1} \big( n-1 \big )^{(n-k+1)}$$

(the binomial selects the slots to be filled with $1$s, the exponential selects a vertex different from $v_1$ for the remaining slots)

-