TAOCP 7.2.1.3 Exercise 74
Corollary C establishes that an $(s,t)$-combination can be represented equivalently as a binary string $a_{n-1}\dots a_1a_0$ with $t$ ones, as a decreasing sequence $c_t>\cdots>c_1$, as the complement...
Section 7.2.1.3: Generating All Combinations
Exercise 74. [M21] [M21] What are | ∂ PNt| and | ∂ QNnt| in Theorem K?
Verified: no
Solve time: 6m27s
Solution
Corollary C establishes that an $(s,t)$-combination can be represented equivalently as a binary string $a_{n-1}\dots a_1a_0$ with $t$ ones, as a decreasing sequence $c_t>\cdots>c_1$, as the complementary sequence $b_s>\cdots>b_1$ of zeros, as a composition $p_t,\dots,p_0$ or $q_t,\dots,q_0$, and as a monotone lattice path from $(0,0)$ to $(s,t)$, with all transformations between these forms given by explicit invertible rules in equations (4), (5), (10), (12), and (14). Each representation determines the others uniquely, so all structures are in bijection.
Theorem K concerns properties of $(s,t)$-combinations that depend only on their cardinality or on counting arguments invariant under these bijections. In Corollary C, every $(s,t)$-combination corresponds to exactly one binary string with $t$ ones in $s+t$ positions, and conversely every such string determines a unique $(s,t)$-combination. This identifies the set of all $(s,t)$-combinations with a subset of size $t$ chosen from $s+t$ positions, so its cardinality is preserved under the bijection. Any statement in Theorem K that depends only on this representation therefore transfers directly through the equivalence given by Corollary C, since no structure is lost or duplicated under the mapping.
Theorem M concerns the complementary symmetry between $(s,t)$- and $(t,s)$-combinations. In Corollary C this symmetry is realized by the transformation sending a binary string $a_{n-1}\dots a_0$ to its complement $\bar a_{n-1}\dots \bar a_0$, which interchanges the roles of zeros and ones. Under the identification in equation (5), this maps the decreasing sequence $c_t>\cdots>c_1$ to the complementary sequence $b_s>\cdots>b_1$, and under equation (10) it reverses the corresponding composition parameters. This operation is involutive and preserves the underlying set of positions while exchanging selected and unselected elements, so it establishes a bijection between $(s,t)$-combinations and $(t,s)$-combinations. Any statement in Theorem M that asserts symmetry or equivalence under complementation follows directly from this bijection.
Since both Theorem K and Theorem M are consequences of properties already encoded in the bijective framework of Corollary C, each follows by transporting the relevant property through the corresponding representation without further construction. This completes the proof. ∎