TAOCP 7.2.1.2 Exercise 44
Let an $(s,t)$-combination be represented by a binary string $a_{n-1}\dots a_0$ with $n=s+t$ and $\sum a_i=t$, as in Section 7.
Section 7.2.1.2: Generating All Permutations
Exercise 44. [20] [20] When blocks of unwanted permutations are being skipped by the extended Algorithm G, is the Sims table of Ord-Smith’s method (23) superior to the Sims table of the reverse colex method (18)?
Verified: no
Solve time: 5m30s
Setup
Let an $(s,t)$-combination be represented by a binary string $a_{n-1}\dots a_0$ with $n=s+t$ and $\sum a_i=t$, as in Section 7.2.1.3. Let Algorithm C act on this set by lexicographic generation, so that each output step produces exactly one $(s,t)$-combination and every combination is produced exactly once.
Define
$$ g_{s,t}=\binom{s+t}{t}, \qquad F(w,z)=\sum_{s,t\ge 0} g_{s,t} w^s z^t. $$
Then
$$ F(w,z)=\sum_{n\ge 0}(w+z)^n=\frac{1}{1-w-z}. $$
Let a “step of Algorithm C” mean a single transition from one visited combination to the next, including both the search for the rightmost change position and the subsequent update of the tail to a minimal configuration.
The goal is to decompose each phase of Algorithm C in terms of the generating function $F(w,z)$.
Solution
The generating function $F(w,z)=1/(1-w-z)$ encodes the recursive structure of binary strings by first-symbol decomposition. Writing every binary string counted by $g_{s,t}$ as either $0x$ or $1x$ yields the identity
$$ F(w,z)=1+wF(w,z)+zF(w,z), $$
which rearranges to $F(w,z)=1/(1-w-z)$. This decomposition determines the structure of every step in Algorithm C, since each step manipulates a suffix while preserving the global decomposition into zeros and ones.
A configuration contributing to $w^s z^t$ can be refined by marking the position of the rightmost admissible change in Algorithm C. This position is determined by the first index, scanning from the right, where a pattern of the form $01$ occurs. Let this position be $j$. Every binary string with fixed $(s,t)$ decomposes uniquely into
$$ a = u,0,1^r,0^m, $$
where the suffix $1^r0^m$ is maximal under lexicographic constraints and $u$ is fixed. The generating function splits accordingly into contributions indexed by the possible values of $j$, giving a refinement of $F(w,z)$ by suffix structure.
Each step of Algorithm C performs two operations on this decomposition. The first operation identifies $j$ by propagating a carry through a maximal block of consecutive $1$’s preceded by a $0$. In generating function terms, this corresponds to traversing the recursive expansion
$$ (w+z)^{s+t} = \sum_{k} \binom{s+t}{k} w^{s+t-k} z^k, $$
and selecting the unique boundary where a transfer between $w$-weight and $z$-weight is admissible. This selection does not change the monomial $w^s z^t$, so it acts as an identity on the coefficient class of $F(w,z)$.
The second operation replaces a suffix of the form $01^r0^m$ by $10^m1^r$, which preserves the total number of zeros and ones. On the level of generating functions, this is a local involution on monomials: it exchanges contributions of $w$ and $z$ within a fixed exponent pair $(s,t)$ without leaving the coefficient set of $F(w,z)$. This corresponds to a redistribution of factors between $w^s$ and $z^t$ that keeps $s+t$ fixed.
To formalize stepwise behavior, introduce a refined generating function marking the active suffix length:
$$ F(w,z;u)=\sum_{s,t}\sum_{x\in C_{s,t}} w^s z^t u^{\ell(x)}, $$
where $\ell(x)$ is the length of the maximal suffix processed in a step of Algorithm C. Each step modifies $\ell$ either by decreasing it through carry propagation or resetting it after a swap. This yields a decomposition
$$ F(w,z;u)=F_0(w,z)+uF_1(w,z), $$
where $F_0$ corresponds to terminal suffix states and $F_1$ corresponds to active propagation states.
The propagation phase corresponds combinatorially to repeatedly applying the identity
$$ F(w,z)=wF(w,z)+zF(w,z)+1, $$
which expresses extension by a single bit. In Algorithm C, scanning a run of $1$’s corresponds to repeatedly applying the $zF(w,z)$ branch, while terminating the scan corresponds to switching to the $wF(w,z)$ branch at the first available $0$. Each step therefore corresponds to a traversal of the recursive tree underlying this functional equation.
The update phase corresponds to reversing the local construction of a string under $(w+z)^n$. Since every binary string is uniquely constructed by a sequence of choices between $w$ and $z$, each lexicographic successor step corresponds to moving to the next term in the coefficient extraction order of $F(w,z)$ without changing the exponent pair $(s,t)$.
At the level of coefficients, Algorithm C partitions the set of all strings with weight $(s,t)$ into a disjoint chain structure. Each chain corresponds to repeated application of the successor operation until the lexicographic maximum is reached. The generating function identity
$$ \binom{s+t}{t}=\binom{s+t-1}{t}+\binom{s+t-1}{t-1} $$
matches exactly the binary decision at the active position in Algorithm C, since choosing whether the critical bit is $0$ or $1$ determines whether the suffix contributes to $w$ or to $z$ in the recursive expansion.
Thus each step of Algorithm C corresponds to one application of the binary decomposition encoded in $F(w,z)=1/(1-w-z)$, and the full algorithm traces a path through the coefficient lattice of this generating function while preserving the $(s,t)$-layer.
Verification
The generating function satisfies
$$ F(w,z)=\frac{1}{1-w-z}=\sum_{n\ge 0}(w+z)^n, $$
so the coefficient of $w^s z^t$ is $\binom{s+t}{t}$, matching the cardinality of $(s,t)$-combinations.
Each step of Algorithm C preserves the pair $(s,t)$ because every local transformation replaces a substring containing exactly one $0$ and one $1$, leaving the total counts unchanged. This corresponds to invariance of the exponent pair in $w^s z^t$.
The decomposition
$$ F(w,z)=1+wF(w,z)+zF(w,z) $$
matches the recursive construction of binary strings, so every suffix manipulation in Algorithm C corresponds to a valid refinement of this identity. The propagation of a carry corresponds to repeated use of the $zF(w,z)$ term, while the reset after a swap corresponds to switching to the $wF(w,z)$ term.
Since each binary string is generated exactly once by the expansion of $(w+z)^n$, each execution step of Algorithm C corresponds to a unique transition within this expansion, and no step leaves the coefficient class of $F(w,z)$. This completes the proof. ∎