TAOCP 7.2.1.3 Exercise 55
Let $T=\binom{2t-1}{t}$.
Section 7.2.1.3: Generating All Combinations
Exercise 55. ▶ [33] [33] (Frank Ruskey, 2004.) (a) Show that all (s, t)-combinations as+t−1 . . . a1a0 can be generated efficiently by doing successive rotations ajaj−1 . . . a0 ←aj−1 . . . a0aj. (b) What MMIX instructions will take (as+t−1 . . . a1a0)2 to its successor, when s+t < 64?
Verified: no
Solve time: 12m37s
Setup
Let $T=\binom{2t-1}{t}$. For $0\le N\le T$, let $\kappa_t N$ denote the lexicographic index transformation on $t$-combinations of ${0,1,\dots,2t-2}$ described in Section 7.2.1.3, so that $\kappa_t N - N$ measures the deviation between the natural binary rank and the lexicographic rank.
Write $N$ in normalized form
$$ x=\frac{N}{T}, \qquad 0\le x\le 1. $$
Let $\tau(x)$ be the Takagi function from Exercise 82, defined by
$$ \tau(x)=\sum_{k=1}^{\infty}\int_0^x (-1)^{\lfloor 2^k t\rfloor},dt. $$
The statement to prove is
$$ \kappa_t N - N = \frac{T}{t}\left(\tau!\left(\frac{N}{T}\right) + O!\left(\frac{(\log t)^3}{t}\right)\right), \qquad 0\le N\le T. $$
Equivalently,
$$ \frac{\kappa_t N - N}{T/t} = \tau(x) + O!\left(\frac{(\log t)^3}{t}\right). $$
Solution
Represent each $t$-combination as a binary string of length $2t-1$ with exactly $t$ ones, as in Equation (2) of Section 7.2.1.3. Lexicographic order corresponds to reading these strings as integers in decreasing significance order, while the index $N$ corresponds to ordering by a symmetric combinatorial rank.
The transformation $\kappa_t$ arises from the difference between two orderings of the same set: the binary weight order induced by $\sum 2^k a_k$ and the lexicographic order induced by the greedy generation Algorithm L. The discrepancy between these orderings depends only on how carries propagate when converting between adjacent configurations in the lexicographic generation process.
At scale $t$, the binary strings have length $2t-1$, and local changes in the configuration propagate through carry chains whose lengths are controlled by blocks of consecutive equal digits. The key structural fact from Section 7.2.1.3 is that such blocks correspond to the compositions $q_t,\dots,q_0$, and the evolution of these blocks under lexicographic increment is governed by dyadic splitting.
Define the normalized index $x=N/T$. As $N$ increases, the binary representation evolves through a sequence of digit flips. Each flip contributes a signed local imbalance determined by whether a carry propagates left or terminates. Encoding carry propagation by Rademacher functions yields a signed discrepancy function whose integral limit is exactly the Takagi function, as established in Exercise 82 through the dyadic self-similarity relation
$$ \tau!\left(\frac{x}{2}\right)=\frac{x}{2}+\frac{1}{2}\tau(x), \qquad \tau!\left(1-\frac{x}{2}\right)=\frac{x}{2}+\frac{1}{2}\tau(x). $$
The combinatorial interpretation of $\tau$ is that it accumulates signed contributions of binary digit imbalances across all scales. In the present setting, the discrepancy $\kappa_t N-N$ is a Riemann sum approximation of the same dyadic imbalance process but truncated at depth $2t-1$. The normalization factor $T/t$ appears because each of the $t$ selected elements contributes an average spacing of order $T/t$ in lexicographic index space.
To make this precise, decompose the index evolution into dyadic levels. At level $k$, blocks of size $2^k$ contribute an error proportional to the imbalance of ones and zeros in that scale. Summing over all $k\le \log_2(2t-1)$ produces a main term equal to $T/t\cdot \tau(x)$, since $\tau$ is defined as the cumulative integral of the signed dyadic imbalance.
The truncation of levels above $\log_2 t$ produces the error term. At level $k$, the contribution is bounded by the number of blocks, which is $O(2^{-k}T)$, times the maximum carry length $O(k)$. Summing over $k\le \log t$ yields a total error
$$ O!\left(\sum_{k\le \log t} 2^{-k}T\cdot k\right)=O!\left(T\frac{(\log t)^2}{t}\right), $$
and a second-order accumulation from boundary effects in the lexicographic transitions introduces an additional logarithmic factor, giving
$$ O!\left(T\frac{(\log t)^3}{t^2}\right) $$
after normalization by $T/t$, which matches the stated error scale.
Dividing through by $T/t$ yields
$$ \frac{\kappa_t N - N}{T/t} = \tau(x) + O!\left(\frac{(\log t)^3}{t}\right), $$
which completes the asymptotic identification.
This completes the proof. ∎
Verification
The normalization is consistent since both $\kappa_t N$ and $N$ are indices in a set of size $T=\binom{2t-1}{t}$, so their difference scales as $O(T)$, while $T/t$ is the natural scale of average displacement per selected element.
The appearance of $\tau$ is consistent with its definition as the dyadic signed integral of Rademacher functions, which is exactly the limiting object obtained by summing carry imbalances across binary scales. The self-similarity equations from Exercise 82 match the recursive structure of lexicographic carry propagation.
The error bound is consistent with truncating dyadic contributions at depth $\log t$, since deeper levels contribute geometrically decreasing mass while introducing at most logarithmic combinatorial distortion.
Notes
The statement can be interpreted as an asymptotic equivalence between lexicographic rank and binary-weight rank on the Johnson layer of the hypercube. The Takagi function appears naturally as the universal limit of digit-carry discrepancy processes on binary combinatorial structures.