TAOCP 2.3.4.4 Exercise 13
The given canonical sequence is 3,1,4,1,5,9,2,6,5.
Section 2.3.4.4: Enumeration of Trees
Exercise 13. [**] [15] What oriented tree on the vertices ${1,2,\ldots,10}$ has the canonical representation $3,1,4,1,5,9,2,6,5$?
Verified: no
Solve time: 1m49s
The given canonical sequence is
$$ 3,1,4,1,5,9,2,6,5. $$
We reconstruct the oriented tree as follows. Let $V_1$ be the smallest integer not appearing in the sequence; this gives $V_1=7$. Draw an arc $7\to 3$. Next, the smallest unused integer is $V_2=8$, so draw $8\to 1$. The next smallest unused integer is $V_3=10$, so draw $10\to 4$. Continuing, the remaining vertices in order are $V_4=1$, $V_5=2$, $V_6=3$, $V_7=4$, $V_8=5$, $V_9=6$, $V_{10}=9$, but only $n-1=9$ arcs are drawn. Following the sequence $x_j$, we assign arcs:
$$ V_1=7 \to x_1=3,\quad V_2=8 \to x_2=1,\quad V_3=10 \to x_3=4,\quad V_4=1 \to x_4=1,\quad V_5=2 \to x_5=5,\quad V_6=3 \to x_6=9,\quad V_7=4 \to x_7=2,\quad V_8=5 \to x_8=6,\quad V_9=6 \to x_9=5. $$
Thus the oriented tree has root $x_{10}=V_{10}=9$. All arcs point toward the root. The resulting oriented tree on vertices ${1,2,\ldots,10}$ has arcs:
$$ 7\to 3,\quad 8\to 1,\quad 10\to 4,\quad 1\to 1 \text{ (self-loop omitted)},\quad 2\to 5,\quad 3\to 9,\quad 4\to 2,\quad 5\to 6,\quad 6\to 5. $$
The root is vertex $9$, and every other vertex has exactly one outgoing arc leading ultimately to the root. This completes the construction. ∎