Section 7.2.1.2: Generating All Permutations

Exercise 2. [20] [20] Rewrite Algorithm L so that it produces all permutations of a1 . . . an in reverse colex order. (In other words, the values of the reflections an . . . a1 should be lexicographically decreasing, as in (11). This form of the algorithm is often simpler and faster than the original, because fewer calculations depend on the value of n.)

7.2.1.2 GENERATING ALL PERMUTATIONS 345

Verified: no
Solve time: 4m23s

Solution

Let $n = s + t$ and let $ct , ct-1 \dots c1$ be a $t$-combination of ${0,1,\dots,n-1}$ written in decreasing order, and let $bs \dots b1$ be the dual representation listing the positions of the zeros in the corresponding binary string.

Each $k$ with $1 \le k \le t$ corresponds to a pair of complementary indices in the binary string: the $k$-th chosen element contributes $c_k$ in the “ones” representation, while in the dual representation the same structure is encoded by the positions of zeros. The key structural fact from Section 7.2.1.3 is that the dual combinations $bs \dots b1$ appear in reverse lexicographic order relative to $ct \dots c1$.

We compare the two binomial sums

$$ A = \sum_{i=1}^{s} \binom{b_i}{i}, \quad B = \sum_{k=1}^{t} \binom{c_k}{k}. $$

We interpret both quantities via the binary representation $a_{n-1}\dots a_0$ of the combination. The standard identity from combinatorial number systems states that for a subset $C = {c_1 < \dots < c_t}$, the rank of the combination in lexicographic order can be expressed as

$$ \mathrm{rank}(C) = \sum_{k=1}^{t} \binom{c_k}{k}. $$

Dually, for the complement subset $B = {b_1 < \dots < b_s}$, the same ranking process applied to zeros gives the rank in reverse lexicographic order. Since reverse lexicographic order on duals corresponds exactly to complement order on originals, the dual sum

$$ A = \sum_{i=1}^{s} \binom{b_i}{i} $$

computes the complementary rank inside the same universe of $\binom{n}{t}$ objects.

More precisely, let $R(C)$ be the lexicographic index of $C$ among all $t$-combinations of ${0,\dots,n-1}$. Then the complement set corresponds to a position

$$ R(B) = \binom{n}{t} - 1 - R(C), $$

because reversing lexicographic order exchanges the first and last elements, the second and second-to-last, and so on.

Substituting the combinatorial number system expansions for both ranks yields

$$ \sum_{i=1}^{s} \binom{b_i}{i}

\binom{n}{t} - 1 - \sum_{k=1}^{t} \binom{c_k}{k}. $$

Rewriting $n = s + t$ gives the final relation

$$ \boxed{ \sum_{i=1}^{s} \binom{b_i}{i} + \sum_{k=1}^{t} \binom{c_k}{k}

\binom{s+t}{t} - 1 }. $$

This identity is symmetric in the sense that exchanging ones and zeros swaps the two sums while preserving the total $\binom{n}{t} - 1$, which is forced by the reversal of lexicographic order on dual combinations.

This completes the proof. ∎