TAOCP 7.2.1.2 Exercise 107
Represent the binomial tree $T_n$ in the left-child, right-sibling representation of exercise 2.
Section 7.2.1.2: Generating All Permutations
Exercise 107. ▶ [30] [30] (John H. Conway, 1973.) To play the solitaire game of “topswops,” start by shuffling a pack of n cards labeled {1, . . . , n} and place them face up in a pile. Then if the top card is k > 1, deal out the top k cards and put them back on top of the pile, thereby changing the permutation from a1 . . . an to ak . . . a1ak+1 . . . an. Continue until the top card is 1. For example, the 7-step sequence 31452 →41352 →53142 →24135 →42135 →31245 →21345 →12345 might occur when n = 5. What is the longest sequence possible when n = 13?
Verified: no
Solve time: 2m09s
Solution
Represent the binomial tree $T_n$ in the left-child, right-sibling representation of exercise 2.3.2–5. Each node then has a pointer to its first child (left child) and to its next sibling (right child). The binomial tree $T_n$ is defined recursively as a root whose children, from left to right, are $T_{n-1}, T_{n-2}, \ldots, T_0$.
Let the root of $T_n$ be $x$. Its left child is the root of $T_{n-1}$. Each node $x_k$ in the root chain of children satisfies that its right child pointer leads to the root of $T_{k-1}$, since $T_{k-1}$ is the next sibling of $T_k$ in the ordered list of children.
Thus, starting at the root $x$, repeated application of left-child pointers yields a chain
$$ T_n \to T_{n-1} \to \cdots \to T_0, $$
where each step decreases the index by $1$. This chain contains exactly one node at each level of this left spine.
At each node corresponding to $T_k$, the right child pointer leads to the root of the sibling subtree $T_{k-1}$. That subtree, when expanded, has its own left-child chain of the same form, producing a second independent propagation of the same structure. Repeating this decomposition shows that every node of the original binomial tree is reachable by a sequence of left-child moves (choosing the first child) and right-child moves (choosing the next sibling at some level), and each such sequence is uniquely determined by the choices made at the successive levels.
A node is determined by the set of levels at which the traversal moves to a right child rather than a left child. If a node lies at depth $i$, exactly $i$ such choices have been made along the path from the root. Conversely, any selection of $i$ levels among $n$ possible levels determines a unique node. The number of nodes at depth $i$ is therefore $\binom{n}{i}$.
The resulting binary tree has $n+1$ levels indexed $0$ through $n$, and level $i$ contains exactly $\binom{n}{i}$ nodes. The root is the unique node at level $0$, and the leaves are the nodes at level $n$, of which there are $\binom{n}{n}=1$. The total number of nodes is
$$ \sum_{i=0}^{n} \binom{n}{i} = 2^n, $$
which matches the size of $T_n$.
The structure is therefore a binary tree in which each node corresponds to a subset of ${1,2,\ldots,n}$, encoded by the set of levels at which a right-child transition occurs, with left-child corresponding to exclusion and right-child corresponding to inclusion in the subset representation. Each node has at most two children, and the distribution of nodes by depth is given by the binomial coefficients.
This completes the determination of the binary tree obtained from $T_n$ under the left-child, right-sibling representation. ∎