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$ Commented Apr 12, 2022 at 11:30
  • $\begingroup$ labelled. sorry, for being imprecise. $\endgroup$ 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$ 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$ Commented Apr 12, 2022 at 13:24
  • 1
    $\begingroup$ @Tardis, shouldn't it be $\binom{n-1}{n_1-1}$? $\endgroup$ Commented Apr 12, 2022 at 13:35
  • $\begingroup$ ah, yes you're right. I got mixed up. $\endgroup$ Commented Apr 12, 2022 at 13:42

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.