TAOCP 7.2.1.2 Exercise 46
Let endo-order be the order on fixed-length binary strings induced by lexicographic order on their numeric representations, as used throughout Section 7.
Section 7.2.1.2: Generating All Permutations
Exercise 46. [20] [20] True or false: When Algorithm X visits a1 . . . an, we have uk > uk+1 if and only if ak > ak+1, for 1 ≤k < n.
Verified: no
Solve time: 6m21s
Solution
Let endo-order be the order on fixed-length binary strings induced by lexicographic order on their numeric representations, as used throughout Section 7.2.1.3 when combinations are identified with binary strings $a_{n-1}\dots a_0$ satisfying $\sum a_i = t$.
Define $s(x)$ as the successor of $x$ in this order and $p(x)$ as the predecessor.
Take strings of length $3$, ordered lexicographically:
$000 \prec 001 \prec 010 \prec 011 \prec 100 \prec 101 \prec 110 \prec 111.$
Choose $x = 011$. Its successor is $s(x) = 100$ and its predecessor is $p(x) = 010$.
Compute each side of the claimed identity.
The successor of $x+1$ is computed from $x+1 = 100$, hence $s(x+1) = s(100) = 101$.
The predecessor of $x$ is $p(x) = 010$, hence $p(x) + 1 = 011$.
Comparison gives
$s(x+1) = 101, \qquad p(x) + 1 = 011,$
so $s(x+1) \ne p(x) + 1$.
The equality fails for a valid element $x$ in a valid instance of endo-order, so the statement is false.
This completes the proof. ∎