# counting trees with two kind of vertices and fixed number of edges beetween one kind

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.

• 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 Jun 13, 2012 at 16:48

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