TAOCP 2.3.4.3 Exercise 1
The root of the oriented tree is the empty sequence $(,)$, which corresponds to the case $n=0$.
Exercise 1. [**] [M10] The text refers to a set $S$ containing finite sequences of positive integers, and states that this set is "essentially an oriented tree." What is the root of this oriented tree, and what are the arcs?
Verified: yes
Solve time: 3m11s
The root of the oriented tree is the empty sequence $(,)$, which corresponds to the case $n=0$. By condition i), every initial subsequence of an element of $S$ is also in $S$, so the empty sequence exists and serves as the origin from which all other sequences grow.
The arcs of the tree connect each sequence $(x_1,\ldots,x_n)$ to the sequences $(x_1,\ldots,x_n,x_{n+1})$ that extend it by one additional positive integer. By condition ii), only finitely many such extensions exist for each node, ensuring that each node has finitely many children. Each arc thus corresponds to adding a single $x_{n+1}$ to an existing sequence in $S$, forming a parent-child relation in the oriented tree. ∎