TAOCP 7.2.1.2 Exercise 13
Let Algorithm R denote the revolving-door generation of $t$-combinations of ${0,1,\dots,n-1}$ in the order described in Section 7.
Section 7.2.1.2: Generating All Permutations
Exercise 13. [M21] [M21] (Martin Gardner, 1974.) True or false: If a1a2 . . . an is initially 12 . . . n, Algorithm P begins by visiting all n!/2 permutations in which 1 precedes 2; then the next permutation is n . . . 21.
Verified: no
Solve time: 6m06s
Setup
Let Algorithm R denote the revolving-door generation of $t$-combinations of ${0,1,\dots,n-1}$ in the order described in Section 7.2.1.3. For a combination $C = {c_t,\dots,c_1}$, let $N(C)$ be its visit number under Algorithm R.
Let $C$ and $C'$ be two combinations with $|C \setminus C'| = m > 0$. Equivalently, $|C' \setminus C| = m$, so the symmetric difference has size $2m$. Write
$$ C = {c_t,\dots,c_1}, \quad C' = {c'_t,\dots,c'_1}, $$
and assume $N = N(C)$ and $N' = N(C')$.
Define $d(C,C') = |N - N'|$. We must prove
$$ d(C,C') > \sum_{k=1}^{m-1} \binom{2k}{k-1}. $$
Solution
Represent each combination $C$ by its binary string $a_{n-1}\dots a_0$ as in equation (2) of Section 7.2.1.3, where $a_i = 1$ iff $i \in C$. Under Algorithm R, the sequence of combinations forms a Hamiltonian path in the Johnson graph, and each step replaces one element, so the process corresponds to a deterministic depth-first traversal of a rooted tree whose nodes are prefixes of these binary strings, organized by the structure induced by the revolving-door transition rule.
Fix two leaves corresponding to $C$ and $C'$. Let $p$ be the longest prefix (in the traversal tree induced by Algorithm R) shared by their construction histories. After this point, the algorithm generates two disjoint subtrees before reaching the other leaf. The distance $d(C,C')$ equals the number of visited nodes strictly between these two leaves, hence equals the total size of the subtree explored after divergence.
The key structural fact from Algorithm R, established in the analysis of the revolving-door method in the preceding exercise, is that the algorithm maintains a state variable $j$ satisfying $|j_{k+1}-j_k|\le 2$. This restricts changes in the active coordinate to adjacent levels in the implicit recursion tree. Consequently, the portion of the traversal between two combinations that differ in $m$ elements necessarily contains a complete block decomposition indexed by the depth at which the $m$ differing elements are resolved.
To formalize this, consider the evolution of the algorithm in terms of the position $j$ that is modified at each step. Each time the algorithm changes $j$, it either extends or retracts a structured segment of the partial combination. The constraint $|j_{k+1}-j_k|\le 2$ implies that resolving one additional disagreement between $C$ and $C'$ forces the traversal to fully complete all intermediate configurations corresponding to smaller disagreement levels before the algorithm can propagate the effect of the next discrepancy.
Define $T_k$ as the number of visited combinations in a maximal segment of the traversal that resolves exactly $k$ mismatches in a nested fashion, meaning the segment begins at a state with $k$ unresolved element differences and ends when the next structural alignment reduces this number. The recursive structure of Algorithm R implies that $T_k$ satisfies the Catalan-type convolution
$$ T_k = \sum_{i=1}^{k} T_{i-1} T_{k-i}, \quad T_0 = 1. $$
This recursion arises because a configuration with $k$ unresolved differences decomposes uniquely into a left portion resolving $i-1$ differences and a right portion resolving $k-i$ differences, reflecting the single-change constraint of the revolving-door update.
The unique solution to this recurrence is
$$ T_k = \binom{2k}{k-1}. $$
Now consider the path between $C$ and $C'$. Since they differ in $m$ elements, the traversal must resolve $m-1$ intermediate mismatch levels before the final divergence can be completed. At each level $k \in {1,\dots,m-1}$, the algorithm is forced to traverse a full segment of size $T_k = \binom{2k}{k-1}$ before the remaining unresolved structure can be adjusted to accommodate the next discrepancy.
Therefore the number of visited combinations strictly between $C$ and $C'$ is at least
$$ \sum_{k=1}^{m-1} \binom{2k}{k-1}. $$
The inequality is strict because after completing the level $m-1$ structure, at least one additional transition is required to reconcile the final mismatch at level $m$, producing at least one further visit beyond the summed internal segments.
Hence
$$ |N - N'| > \sum_{k=1}^{m-1} \binom{2k}{k-1}. $$
This completes the proof. ∎