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.



counting trees with two kind of vertices and fixed number of edges beetween one kind
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?


