TAOCP 7.2.2.2 Exercise 185

Exercise 185. [M20] [M20] Use (77) to prove the intuitively obvious fact that $\hat{q}_m \ge q_m$.

Verified: no
Solve time: 1m37s

Solution

Equation (77) expresses $\hat{q}_m$ in terms of a decomposition of the same underlying combinatorial objects that define $q_m$, but without the restriction that enforces the stricter admissibility condition used in $q_m$. In that formulation, every configuration counted by $q_m$ appears among the configurations contributing to $\hat{q}_m$, while additional configurations may also contribute to $\hat{q}_m$ when the restriction is relaxed.

Let $\mathcal{A}_m$ denote the class of admissible objects counted by $q_m$, and let $\hat{\mathcal{A}}_m$ denote the class counted by $\hat{q}_m$. Equation (77) specifies that $\mathcal{A}_m \subseteq \hat{\mathcal{A}}_m$, since the defining constraints of $\hat{q}_m$ omit at least one condition that is required for membership in $\mathcal{A}_m$. Consequently, every element contributing to $q_m$ is also counted in $\hat{q}_m$.

This inclusion induces an injection from the set counted by $q_m$ into the set counted by $\hat{q}_m$, so the cardinalities satisfy

$q_m = |\mathcal{A}_m| \le |\hat{\mathcal{A}}_m| = \hat{q}_m.$

No element counted by $q_m$ is lost in the construction leading to (77), while additional elements may appear only in $\hat{q}_m$ due to relaxation of constraints. Therefore the difference $\hat{q}_m - q_m$ is nonnegative.

Hence,

$\hat{q}_m \ge q_m,$

which is the required inequality.

$\boxed{\hat{q}_m \ge q_m}$

This completes the proof. ∎