TAOCP 7.2.1.1 Exercise 60
The bit string $(13)$ refers to the binary representation displayed in equation $(13)$ of the section, a_{23}\dots a_1 a_0 = 011001001000011111101101, which represents an $(s,t)$-combination with $s=1...
Section 7.2.1.1: Generating All n-Tuples
Exercise 60. [20] [20] Show that the run-length-bound function satisfies r(n + 1) ≥r(n).
Verified: no
Solve time: 4m59s
Solution
The bit string $(13)$ refers to the binary representation displayed in equation $(13)$ of the section,
$$ a_{23}\dots a_1 a_0 = 011001001000011111101101, $$
which represents an $(s,t)$-combination with $s=11$ zeros and $t=13$ ones. In the grid interpretation of (7.2.1.3), an $(s,t)$-combination corresponds to a path from the southwest corner to the northeast corner of an $s\times t$ grid, consisting of $s$ vertical steps and $t$ horizontal steps.
Under this correspondence, each bit $a_k$ determines a step: $a_k=0$ yields a vertical step, and $a_k=1$ yields a horizontal step. The condition $s+t=24$ ensures that the path has exactly $24$ unit steps.
Decomposing the string into maximal blocks,
$$ 01100;10010;0001;11111;01101, $$
gives a direct description of the path as consecutive runs of vertical and horizontal moves:
the first block contributes $0,1,1,0,0$, the second $1,0,0,1,0$, the third $0,0,0,1$, the fourth $1,1,1,1,1$, and the fifth $0,1,1,0,1$.
Interpreting $0$ as a vertical step $V$ and $1$ as a horizontal step $H$, the path is
$$ VVHHV;HVVHV;VVVH;HHHHH;VHHVH. $$
Equivalently, the path is uniquely determined by starting at $(0,0)$, taking $11$ vertical steps and $13$ horizontal steps in the order prescribed by the above sequence, and ending at $(11,13)$ in the grid. This completes the translation from the bit string $(13)$ to its corresponding lattice path. ∎