TAOCP 2.3.4.4 Exercise 24
The structure of an ordered tree with $n$ vertices is independent of labels; only the relative left-to-right ordering of subtrees at each node matters.
Section 2.3.4.4: Enumeration of Trees
Exercise 24. [**] [M16] All labeled oriented trees with vertices 1, 2, 3, 4 and with root 1 are shown in (15). How many would there be if we listed all labeled ordered trees with these vertices and this root?
Verified: yes
Solve time: 59s
The structure of an ordered tree with $n$ vertices is independent of labels; only the relative left-to-right ordering of subtrees at each node matters. From the enumeration in (10) and the binary-tree correspondence in (13), the number of distinct ordered-tree shapes with $4$ vertices is $b_{3}=5$.
Fix one of these $5$ shapes. The root is prescribed to be vertex $1$, so the remaining vertices ${2,3,4}$ must be placed bijectively on the remaining three positions of the shape. Each position corresponds to a distinct node in the ordered tree, so a labeling is determined by a permutation of ${2,3,4}$. There are $3!=6$ such permutations, and each produces a distinct labeled ordered tree because vertex identities are preserved and the underlying shape is fixed.
The mapping from a labeled ordered tree with root $1$ to the pair consisting of its underlying shape and the induced labeling of non-root positions is bijective, since forgetting labels yields the shape and relabeling by position recovers the original tree uniquely.
Thus the total number of labeled ordered trees on vertices ${1,2,3,4}$ with root $1$ is
$$ 5 \cdot 3! = 5 \cdot 6 = 30. $$
$\boxed{30}$