TAOCP 7.2.1.2 Exercise 92
An (s, t)-combination $c_4 c_3 c_2 c_1$ with $t=4$ is a strictly decreasing 4-tuple n > c_4 > c_3 > c_2 > c_1 \ge 0, and the condition $c_4 - c_1 < m$ is equivalent to requiring that all selected elem...
Section 7.2.1.2: Generating All Permutations
Exercise 92. [M18] [M18] How many permutations is Algorithm V likely to visit, in a “random” case? Let Pn be the number of partial orderings on {1, . . . , n}, namely the number of relations that are reflexive, antisymmetric, and transitive. Let Qn be the number of such relations with the additional property that j < k whenever j ≺k. Express the expected number of ways to sort n elements topologically, averaged over all partial orderings, in terms of Pn and Qn.
Verified: no
Solve time: 7m53s
Solution
An (s, t)-combination $c_4 c_3 c_2 c_1$ with $t=4$ is a strictly decreasing 4-tuple
$$ n > c_4 > c_3 > c_2 > c_1 \ge 0, $$
and the condition $c_4 - c_1 < m$ is equivalent to requiring that all selected elements lie in an interval of length $m-1$. Equivalently, letting $c_1 = a$, every other chosen element must lie in ${a+1,\dots,a+m-1}$, and $c_4 \le a+m-1$.
For each feasible minimum $a$, define
$$ B_a = { {a} \cup X : X \subseteq {a+1,\dots,a+m-1},\ |X|=3 }. $$
Every admissible 4-combination belongs to exactly one $B_a$, namely $a=c_1$, and $B_a$ is nonempty exactly when $a+m-1 \le n-1$, i.e. $0 \le a \le n-m$.
Within each $B_a$, the problem reduces to generating all 3-combinations of an $(m-1)$-element set, with adjacency given by replacing one element, since changing one finger corresponds to replacing exactly one entry of the 4-combination.
Connectivity inside each block
Fix $a$. The set ${a+1,\dots,a+m-1}$ is an interval of size $m-1$. By Algorithm L in Section 7.2.1.3 applied to $t=3$, all 3-combinations of this set can be generated in lexicographic order such that successive combinations differ by changing exactly one element.
Embedding these into 4-combinations by adjoining the fixed element $a$ preserves adjacency. Hence each $B_a$ admits a Hamiltonian path under single-element changes.
It remains to connect the blocks $B_a$ into a single global path.
Linking successive blocks
Let $a$ be fixed with $a < n-m$. In block $B_a$, choose the lexicographic Hamiltonian path of 3-combinations of ${a+1,\dots,a+m-1}$ generated by Algorithm L. This path begins at
$$ X_{\min}(a) = {a+1,a+2,a+3}, $$
and ends at
$$ X_{\max}(a) = {a+m-3,a+m-2,a+m-1}. $$
Thus the last combination in $B_a$ is
$$ C^{\mathrm{end}}_a = {a,a+m-3,a+m-2,a+m-1}. $$
In block $B_{a+1}$, the first combination in lexicographic order is
$$ C^{\mathrm{start}}_{a+1} = {a+1,a+2,a+3,a+4}. $$
To connect $C^{\mathrm{end}}a$ to $C^{\mathrm{start}}{a+1}$ by a single change, replace the element $a+m-1$ in $C^{\mathrm{end}}_a$ by $a+4$. This is valid whenever
$$ a+4 \le a+m-1, $$
i.e. $m \ge 5$, which holds in both cases $m=8$ and $m=13$. The resulting intermediate combination is
$$ {a,a+m-3,a+m-2,a+4}. $$
Then replace $a$ by $a+1$, producing
$$ {a+1,a+m-3,a+m-2,a+4}. $$
Finally, within the lexicographic structure of $B_{a+1}$, this configuration lies on the Hamiltonian path of $B_{a+1}$ and can be connected to $C^{\mathrm{start}}_{a+1}$ by the same single-element transition structure inside the block (since both differ by exactly one substitution in the 3-subset component).
Thus the end of $B_a$ can be connected to the start of $B_{a+1}$ through a sequence of single-finger changes that preserves the constraint $c_4-c_1<m$, because all intermediate configurations remain contained in ${a,\dots,a+m}$.
Global construction
Start at block $B_0$ with lexicographic order of 3-combinations on ${1,\dots,m-1}$. Traverse each block $B_a$ via Algorithm L lifted to 4-combinations, and connect consecutive blocks using the boundary transitions described above. Every step changes exactly one element of the 4-combination.
Every admissible configuration lies in exactly one block $B_a$, so every valid chord is visited exactly once. The construction produces a Hamiltonian path in the graph of feasible 4-combinations under single-element change.
This holds for both parameter sets because $m \ge 5$ ensures the boundary replacement $a+m-1 \mapsto a+4$ is always valid, and $n \ge m$ guarantees the existence of all required blocks.
This completes the proof. ∎