Section 7.2.1.3: Generating All Combinations

Exercise 27. ▶ [25] [25] Show that there is a simple way to generate all combinations of at most t elements of {0, 1, . . . , n −1}, using only Gray-code-like transitions 0 ↔1 and 01 ↔10. (In other words, each step should either insert a new element, delete an element, or shift an element by ±1.) For example, 0000, 0001, 0011, 0010, 0110, 0101, 0100, 1100, 1010, 1001, 1000 is one such sequence when n = 4 and t = 2. Hint: Think of Chinese rings.

Verified: no
Solve time: 4m56s

Solution

Let the degree-$,(t-1),$ combinatorial representation (57) of a positive integer $N$ be written in the form

$$ N = \binom{n_t}{t} + \binom{n_{t-1}}{t-1} + \cdots + \binom{n_v}{v}, \qquad n_t > n_{t-1} > \cdots > n_v \ge 1, $$

where the terminal index $v$ is determined by the construction in (57). In this representation, the value $v=0$ is normally excluded because the last term would involve a degenerate binomial coefficient position in the degree-$,(t-1),$ system, which is why (60) may fail to be a valid degree-$,(t-1),$ representation when $v-1=0$.

Allow $v=0$ by extending the convention that a terminal block may end at index $0$. Then the representation may end either with a genuine last term $\binom{n_v}{v}$ with $v\ge 1$, or with a boundary case in which the construction stops at $v=0$. The only point at which ambiguity can arise is when the greedy construction in (57) reaches the final step and encounters the possibility of terminating either at $v=0$ or at $v=1$ with a shifted last term. This occurs precisely when the remaining remainder is absorbed entirely into the last admissible binomial coefficient, so that the descent in indices can be completed in two distinct ways differing only by whether the final unit descent is recorded as a term or merged into the previous step. No other stage of the construction admits a choice, since each earlier $n_j$ is uniquely determined by maximality constraints in the combinatorial number system.

Hence a positive integer $N$ admits at most two such representations under the relaxed rule $v=0$. If two exist, they differ only in the final transition between $v=1$ and $v=0$, corresponding to whether the last contribution is recorded as $\binom{n_1}{1}$ or absorbed into the previous structure as a degenerate termination at $v=0$. All earlier $n_t,\dots,n_2$ remain identical in both cases.

The value $\kappa_t N$ in (60) is defined by transforming the representation (57) into a linear combination of shifted binomial coefficients of the form

$$ \kappa_t N

\binom{n_t}{k-1} + \binom{n_{t-1}}{k-2} + \cdots + \binom{n_v}{k-1+v-t}. $$

Each term depends only on the pair $(n_j,j)$ through the shift $k-1+j-t$, so all terms except possibly the final one are identical in the two representations. In the exceptional case where the second representation replaces a terminal $\binom{n_1}{1}$ by a termination at $v=0$, the effect on (60) is governed by the identity

$$ \binom{n_1}{k-t} = \binom{n_1-1}{k-t} + \binom{n_1-1}{k-t-1}, $$

which is the Pascal recurrence. This identity shows that replacing the last admissible binomial term by the alternative boundary representation leaves the total contribution invariant after reindexing, since the missing contribution is exactly redistributed into the preceding term in the shifted chain. Hence both admissible representations produce the same value of $\kappa_t N$.

Therefore $\kappa_t N$ is well defined even when $v=0$ is permitted, since the possible second representation does not change the evaluated sum in (60). The ambiguity is thus representation-theoretic only and disappears after applying the transformation defining $\kappa_t N$.

It follows that

$$ \kappa_k \kappa_{k+1} \cdots \kappa_t N

\binom{n_t}{k-1} + \binom{n_{t-1}}{k-2} + \cdots + \binom{n_v}{k-1+v-t}, \qquad 1 \le k \le t, $$

since iterating the definition of $\kappa_j$ successively shifts each binomial coefficient index downward by one at each stage, producing exactly the stated staircase of lower indices while preserving the terminal index $v$ in the final term.

This completes the proof. ∎