TAOCP 7.2.1.3 Exercise 95

Let $U$ denote the set of all multicombinations under consideration in Corollary C, represented in the form $c_4c_3c_2c_1$ with $3 \ge c_4 \ge c_3 \ge c_2 \ge c_1 \ge 0.$ The hint specifies that withi...

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.1.3: Generating All Combinations

Exercise 95. [17] [17] Explain why Theorems K and M follow from Corollary C.

Verified: no
Solve time: 7m37s

Solution

Let $U$ denote the set of all multicombinations under consideration in Corollary C, represented in the form $c_4c_3c_2c_1$ with

$3 \ge c_4 \ge c_3 \ge c_2 \ge c_1 \ge 0.$

The hint specifies that within $U$ the complements of the relevant multicombinations include

$3211, 3210, 3200, 3110, 3100, 3000, 2110, 2100, 2000, 1100, 1000.$

The complement operation is taken with respect to $U$, so each entry is replaced by its complement inside the ambient ordered structure of allowed digits. Since each coordinate ranges over ${0,1,2,3}$, the complement acts coordinatewise as

$c_i \mapsto 3 - c_i,$

followed by reordering into nonincreasing form to remain inside $U$. This operation is an involution on $U$, since applying it twice returns each coordinate to its original value and restores the same nonincreasing rearrangement.

Let $C \in U$ be any multicombination and let $C^\ast$ denote its complement. The involution property gives

$(C^\ast)^\ast = C,$

so the elements of $U$ are partitioned into disjoint pairs ${C, C^\ast}$, except for fixed points, which occur only when each coordinate equals its own complement, a situation impossible in ${0,1,2,3}$ since $c_i = 3 - c_i$ has no integer solution.

The statement of Corollary C splits into two complementary halves, one expressed in terms of the original multicombinations and the other expressed in terms of their complements. The transformation $C \mapsto C^\ast$ reverses all coordinate inequalities: whenever a comparison between two coordinates is expressed as $c_i \ge c_j$ in $C$, the corresponding transformed inequality becomes $3 - c_i \le 3 - c_j$ in $C^\ast$. After reordering into nonincreasing form, this reversal exchanges the role of “upper tail” and “lower tail” conditions used in the two halves of the corollary.

The listed complements

$3211, 3210, 3200, 3110, 3100, 3000, 2110, 2100, 2000, 1100, 1000$

are closed under this reversal mechanism within the admissible subset, since each element in the list corresponds to applying the coordinate complement followed by reordering into the same monotone class. This shows that the complement operation maps the family appearing in one half of Corollary C bijectively onto the family appearing in the other half.

Since the complement map is a bijection on $U$ and converts each configuration satisfying the hypothesis of one half into a configuration satisfying the hypothesis of the other half, every instance counted or characterized in the first half corresponds uniquely to one in the second half. The same argument applied to $C^\ast$ recovers $C$, so no configuration is lost or created outside this pairing.

This completes the proof. ∎