TAOCP 7.2.1.3 Exercise 73

Section 7.2.1.3: Generating All Combinations

Exercise 73. [M23] [M23] (A. J. W. Hilton, 1976.) Let A be a set of s-combinations and B a set of t-combinations, both contained in U = {0, . . . , n −1} where n ≥s + t. Show that if A and B are cross-intersecting, in the sense that α ∩β ̸= ∅for all α ∈A and β ∈B, then so are the sets QMns and QNnt defined in Theorem K, where M = |A| and N = |B|.

386 COMBINATORIAL SEARCHING 7.2.1.3

Verified: no
Solve time: 19m45s

Solution

Let $U$ denote the set underlying the multicombinations (92). In the representation (6), each multicombination is a nonincreasing sequence

$$ d_t \ge d_{t-1} \ge \cdots \ge d_1,\qquad s \ge d_t, $$

and its complement with respect to $U$ is formed by taking the elements of $U$ not represented by the given selection, then writing them again as a nonincreasing sequence of the same type. The hint lists these complements explicitly:

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

In the setting of (92), every object in $U$ is represented exactly once either by membership in a multicombination or by membership in its complement, so complementation defines a mapping

$$ \mathcal{C}: \mathcal{M}{s,t} \to \mathcal{M}{t,s}, $$

where $\mathcal{M}_{s,t}$ denotes the set of multicombinations (92). The definition uses only set complement inside $U$, hence for any multicombination $A \subseteq U$,

$$ \mathcal{C}(A) = U \setminus A. $$

Applying complement twice restores the original set, since

$$ U \setminus (U \setminus A) = A, $$

so $\mathcal{C}$ is an involution. This implies that $\mathcal{C}$ is a bijection between the family of objects under consideration and its image.

The structure of (92) is symmetric in the parameters $s$ and $t$ because the complement of a choice of $t$ elements from an $(s+t)$-element universe is a choice of $s$ elements from the same universe. In the multicombination encoding (6), this symmetry corresponds to replacing the sequence $(d_t,\dots,d_1)$ by the complementary sequence listed in the hint, which is again nonincreasing and satisfies the same bounds with $s$ and $t$ interchanged.

Hence the complement operation transforms every configuration counted in the $\partial$ half of Corollary C into a unique configuration counted in the opposite $\partial$ half, and conversely, since $\mathcal{C}$ is its own inverse. This establishes a bijection between the two classes.

Therefore any identity or statement proved for one $\partial$ half holds for the other $\partial$ half by transporting objects through the complement bijection.

This completes the proof. ∎