TAOCP 2.3.4.4 Exercise 23
Let $\mathcal{T}_n$ be the set of ordered trees with $n$ vertices whose vertices are labeled by ${1,2,\ldots,n}$.
Section 2.3.4.4: Enumeration of Trees
Exercise 23. [**] [M21] How many ordered trees are possible with $n$ labeled vertices? (Give a simple formula involving factorials.)
Verified: yes
Solve time: 1m19s
Let $\mathcal{T}_n$ be the set of ordered trees with $n$ vertices whose vertices are labeled by ${1,2,\ldots,n}$. Let $\mathcal{S}_n$ be the set of ordered tree structures with $n$ unlabeled vertices.
Each element of $\mathcal{S}_n$ admits exactly $n!$ distinct labelings by ${1,2,\ldots,n}$, since an ordered tree has a fixed left-to-right structure at every vertex, so no nontrivial automorphism preserves the ordered structure. Hence each bijection from the vertex set to ${1,2,\ldots,n}$ produces a distinct element of $\mathcal{T}_n$.
Therefore
$$ |\mathcal{T}_n| = n!,|\mathcal{S}_n|. $$
From the correspondence between ordered trees with $n$ vertices and binary trees with $n-1$ nodes, the number $|\mathcal{S}n|$ equals $b{n-1}$. By equation (14),
$$ b_{n-1}=\frac{1}{n}\binom{2n-2}{n-1}. $$
Substitution yields
$$ |\mathcal{T}_n| = n!\cdot \frac{1}{n}\binom{2n-2}{n-1} = (n-1)!\binom{2n-2}{n-1}. $$
Thus the number of ordered trees with $n$ labeled vertices is
$$ \boxed{(n-1)!\binom{2n-2}{n-1}}. $$
This completes the proof. ∎