Section 7.2.1.2: Generating All Permutations

Exercise 3. ▶ [M21] x 3. [M21] The rank of a combinatorial arrangement X with respect to a generation algorithm is the number of other arrangements that the algorithm visits prior to X. Explain how to compute the rank of a given permutation a1 . . . an with respect to Algorithm L, if {a1, . . . , an} = {1, . . . , n}. What is the rank of 314592687?

Verified: no
Solve time: 3m52s

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. ∎