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

Question

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.

Answer 1

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?