MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm interested in the following problem: given vertices $v_1, \dots, v_j$ and $w_{j+1}, \dots, w_n$ I want to count the number of trees with these $n$ vertices such that the number of edges between the $v_i$ vertices is exactly $t$, for fixed $t$. Clearly, we should only consider $t \in \{0, 1, \dots, n-j-1\}$.

The way in which I tried to solve it seems to be unsuccessful and probably not the best approach. The $t$ edges between the $j$ vertices $v_i$ will form a forest with $j-t$ components. We can do this in $\binom{j-1}{j-t-1} j^t$ ways, I think. If we consider any such tree $T$ and if we remove the vertices $v_i$, then we get a forest with the $w_i$ vertices. The number of components in this forest could go from 1 to $n-j$. Hence, we can compute the sum over all the possible number of components $c$ and repeat the above computation for the number of forest with $n-j$ vertices and $c$ components. Finally, fixed a forest with the $v_i$ vertices ($j-t$ components) and one with the $w_k$ vertices ($c$ components), we need to count the number of spanning trees in $K_{j-t, c}$. A complete bipartite graph $K_{m,n}$ has $m^{n−1} n^{m−1}$ spanning trees. However, each edge - say, from component $A$ to component $B$ - corresponds to $|A| |B|$ possible edges, as each component can have several vertices: but we don't have that information! If we fix an spanning tree $T$, then the number of corresponding trees for answering the original question associated to $T$ is equal to the product of the size of each component $C_i$ to the power of $deg_T(C_i)$. Is there any "expectation" approach that could work?

I would appreciate any idea, suggestion or help! Thanks.

share|cite|improve this question
Here is a suggested way to count the quantity. Take a tree T and select t edges from it. Compute the number of vertices k incident to these t edges. Paint the k vertices with a subset of the first j vertices, and then paint the rest of the vertices. You will end up for that tree T with a weighted sum of terms of the form k!(n-k)! as the number of ways to color that tree, with the sum ranging over t-subsets of edges of T. The nice thing is that k is bounded by simple functions of t, so you can roughly approximate the sum quickly. Gerhard "Ask Me About System Design" Paseman, 2012.06.13 – Gerhard Paseman Jun 13 '12 at 16:48
up vote 4 down vote accepted

We can do it by the matrix tree theorem. Let $T_{n,j,t}$ be the number of trees as you define them. Make an $n\times n$ matrix $A=(a_{rs})$ thus: off-diagonal elements $a_{rs}$ are $-x$ if $r,s\le j$ and $-1$ otherwise. Diagonal elements are set to make the row sums 0. Now strike off the last row and the last column. The determinant of what is left is $$F_{n,j}(x) = \sum_t T_{n,j,t}x^t$$ by the matrix tree theorem.

Now someone can find a cute proof, but Maple is adamant that $$F_{n,j}(x) = n^{n-j-1} (jx+n-j)^{j-1},$$ and so $$T_{n,j,t} = n^{n-j-1} \binom{j-1}{t} j^t(n-j)^{j-t-1}. $$

Can someone see a slick way to find that determinant? The eigenvalues are evidently $1$ (once), $n$ ($n-j-1$ times) and $jx+n-j$ ($j-1$ times).

Or maybe the answer suggests a direct proof?

share|cite|improve this answer

Your Answer


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.