2
$\begingroup$

A tree $G$ on $n$ vertices $V=\{v_1,...,v_n\}$ is a connected undirected graph which is acyclic. For each tree $G$ one can split the set of vertices $V$ into two disjoint subsets $U,W \subset V$ such that $V = U \cup W$ and each edge in $G$ is between a vertex from $U$ and a vertex from $W$. In order to get uniqueness of $U$ and $W$ let's require $v_1$ to be in $U$.

My question is if there is a known formula for the number of trees on $n$ vertices which satisfy $\#U = n_1$ and $\#W = n_2$ for given $n_1,n_2$ with $n_1+n_2=n$.

Any help is much appreciated.

Improve this question
$\endgroup$
2
  • $\begingroup$ Are these labelled trees or just pointed/rooted? $\endgroup$
    – Peter Taylor
    Commented Apr 12, 2022 at 11:30
  • $\begingroup$ labelled. sorry, for being imprecise. $\endgroup$
    – Ben Deitmar
    Commented Apr 12, 2022 at 11:33

1 Answer 1

Reset to default
5
$\begingroup$

If the trees are labelled, then each tree satisfying the condition corresponds to exactly one spanning tree of the bipartite graph $K_{n_1,n_2}$. Therefore the answer is the number of spanning trees of the bipartite graph $K_{n_1,n_2}$, which is $n_1^{n_2-1}n_2^{n_1-1}$ according to this.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Nice, an interesting approach. Thanks! $\endgroup$
    – Ben Deitmar
    Commented Apr 12, 2022 at 13:02
  • $\begingroup$ small correction: we still need to multiply with $\frac{1}{2}{n \choose n_1}$, since for each spanning tree of $K_{n_1,n_2}$ the sets $U,W$ are always $\{1,...,n_1\}$ and $\{n_1+1,...,n\}$ respectively. We want to allow for $U$ to be any subset of $\{1,...,n\}$ with $n_1$ elements (thus the ${n \choose n_1}$ factor) but it still must contain $1$, thus the factor $\frac{1}{2}$. $\endgroup$
    – Ben Deitmar
    Commented Apr 12, 2022 at 13:24
  • 1
    $\begingroup$ @Tardis, shouldn't it be $\binom{n-1}{n_1-1}$? $\endgroup$
    – Peter Taylor
    Commented Apr 12, 2022 at 13:35
  • $\begingroup$ ah, yes you're right. I got mixed up. $\endgroup$
    – Ben Deitmar
    Commented Apr 12, 2022 at 13:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .