3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$ Jun 13, 2012 at 16:48

1 Answer 1

5
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.