TAOCP 2.3 Exercise 1
There are three nodes labeled $A$, $B$, and $C$.
Exercise 1. [**] [18] How many different trees are there with three nodes, A, B, and C?
Verified: no
Solve time: 31s
There are three nodes labeled $A$, $B$, and $C$. A tree is a connected acyclic graph. Since each tree with three nodes has exactly two edges, we must consider all possible edge combinations that connect all nodes without forming a cycle. The possible trees are determined by the choice of a root and the structure of parent-child relations.
Up to isomorphism with labeled nodes, the trees are: a linear chain $A$–$B$–$C$ (with three distinct orders: $A$–$B$–$C$, $A$–$C$–$B$, $B$–$A$–$C$, etc.), and a star-shaped tree with one node connected to the other two. Counting all distinct labelings, we have: for the chain, $3! = 6$ permutations, and for the star, $3$ choices of the central node. Therefore, the total number of different trees is $6 + 3 = 9$.
Hence, there are $\boxed{9}$ different trees with nodes $A$, $B$, and $C$.