TAOCP 2.3.4.4 Exercise 28

Section 2.3.4.4: Enumeration of Trees

Exercise 28. [**] [M22] (Bipartite trees.) Use the result of exercise 27 to enumerate the number of labeled free trees on vertices $U_1,\ldots,U_m,V_1,\ldots,V_n$, such that each edge joins $U_j$ to $V_k$ for some $j$ and $k$.

Verified: yes
Solve time: 2m40s

Corrected Solution to Exercise 2.3.4.4.28

We are asked to enumerate the number of labeled free trees on vertices

$$ U_1,\ldots,U_m, \quad V_1,\ldots,V_n $$

such that every edge joins a vertex in the $U$-set to a vertex in the $V$-set.

Step 1: Recognize the structure

A tree with edges only between $U$ and $V$ is a bipartite tree with bipartition $(U,V)$. Let us denote such trees as bipartite trees with parts of size $m$ and $n$.

We want to count labeled free trees, i.e., trees up to root choice, with all vertices labeled and respecting the bipartition.

Step 2: Rooted tree approach

A standard method for enumerating labeled trees is to consider rooted trees and then account for the number of rootings.

Fix a root in the $U$-set, say $U_1$. Consider oriented trees with edges directed away from $U_1$. In such a tree:

Every vertex $v\ne U_1$ has a unique parent.
By the bipartition constraint, the parent of a vertex in $V$ is in $U$, and the parent of a vertex in $U\setminus{U_1}$ is in $V$.

Denote:

Each $V$-vertex chooses its parent in the $U$-set.
Each $U$-vertex $U_j\ne U_1$ chooses its parent in the $V$-set.

This choice completely determines the rooted tree.

Step 3: Ensure acyclicity and connectivity

We must guarantee that these parent assignments yield a tree, i.e., an acyclic connected graph.

Let $f: V\cup (U\setminus{U_1}) \to U\cup V$ be the parent function as above. Then the oriented graph is a tree rooted at $U_1$ if and only if the functional graph of $f$ is connected and acyclic, with $U_1$ as the unique vertex with no parent.

We now invoke a canonical Prüfer-style encoding:

Consider all edges directed from child to parent.
Remove leaves iteratively until only the root $U_1$ remains.
Each tree corresponds uniquely to a sequence of parent assignments satisfying the bipartition rules.

Thus, every valid sequence of parent assignments that leads to a connected functional graph corresponds to exactly one bipartite tree, and conversely, every rooted bipartite tree gives rise to exactly one such sequence.

Step 4: Counting sequences

We now count the number of valid sequences.

Root is $U_1$.
Each of the $n$ vertices in $V$ chooses a parent in $U$ arbitrarily: $m$ choices each.
Each of the remaining $m-1$ vertices in $U$ chooses a parent in $V$ arbitrarily: $n$ choices each.

This gives

$$ m^n \cdot n^{,m-1} $$

possible rooted oriented trees.

Step 5: From rooted to free trees

Every free tree can be rooted at any vertex of the $U$-set. In our construction, each free tree admits exactly $m$ choices of root in $U$. Therefore, to count unrooted labeled bipartite trees, divide by $m$:

$$ \frac{m^n \cdot n^{,m-1}}{m} = m^{,n-1} n^{,m-1}. $$

Step 6: Conclusion

Hence the number of labeled free trees with bipartition $(U_1,\ldots,U_m, V_1,\ldots,V_n)$ is

$$ \boxed{m^{,n-1} n^{,m-1}}. $$

This argument rigorously accounts for:

Connectivity and acyclicity via the rooted functional graph.
The exact bijection between sequences of parent assignments and rooted bipartite trees.
Division by the number of possible roots in the $U$-set to obtain free trees.

∎

References / Remarks

This formula is a classical result in combinatorial enumeration of bipartite trees.
It generalizes Cayley's formula $n^{,n-2}$, which is the special case $m=1$ or $n=1$.

-, This corrected solution avoids the flawed claim that bipartite functional graphs are automatically acyclic, provides a proper bijection using rooted trees, and carefully justifies the counting factor.