TAOCP 2.3 Exercise 2
With three nodes $A$, $B$, and $C$, every tree has exactly two edges.
Exercise 2. [**] [20] How many different oriented trees are there with three nodes, A, B, and C?
Verified: no
Solve time: 29s
With three nodes $A$, $B$, and $C$, every tree has exactly two edges. The unlabeled shape is uniquely a path of length $2$. When the nodes are labeled, the middle node may be chosen in $3$ ways. Once the middle node is fixed, the remaining two nodes occupy the ends, and exchanging the ends does not produce a different tree. Hence there are $3$ different trees, namely those with middle node $A$, $B$, or $C$.
For an oriented tree, each of the two edges may be directed independently. Thus each of the $3$ labeled trees gives rise to $2^2 = 4$ orientations. Therefore the total number of oriented trees is
$$ 3 \cdot 4 = 12. $$
Hence the number of different oriented trees with nodes $A$, $B$, and $C$ is
$$ \boxed{12}. $$