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.

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

share|improve this question
add comment

3 Answers

up vote 1 down vote accepted

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.

share|improve this answer
    
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
add comment

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)$.

share|improve this answer
add comment

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)

share|improve this answer
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.