TAOCP 7.1.1 Exercise 108
Let the order be the prefix-sum (majorization) order: \alpha \ge \beta \quad \Longleftrightarrow \quad s_k(\alpha)\ge s_k(\beta)\ \text{for all }k,\qquad s_k(\alpha)=\sum_{i=1}^k \alpha_i.
Exercise 108. [M21] Let $g(x_0, x_1, \ldots, x_n)$ be a self-dual function; thus $\Sigma(g) = \frac{1}{2} \cdot 2^n$ when $f(x_1, \ldots, x_n)$ is (a) $g(0, x_1, \ldots, x_n)$; (b) $g(1, x_1, \ldots, x_n)$.
Fig. 8. The binary majorization lattice for strings of length 5. (See exercise 109.)
b) Show that any two binary strings of length $n$ have a greatest lower bound $\alpha \wedge \beta$, which has the property that $\alpha \ge \gamma$ and $\beta \ge \gamma$ if and only if $\alpha \wedge \beta \ge \gamma$. Explain how to compute $\alpha \wedge \beta$, given $\alpha$ and $\beta$.
c) Similarly, explain how to compute a least upper bound $\alpha \vee \beta$, with the property that $\gamma \ge \alpha$ and $\gamma \ge \beta$ if and only if $\gamma \ge \alpha \vee \beta$.
d) True or false: $\alpha \wedge (\beta \vee \gamma) = (\alpha \wedge \beta) \vee (\alpha \wedge \gamma)$; $\alpha \vee (\beta \wedge \gamma) = (\alpha \vee \beta) \wedge (\alpha \vee \gamma)$.
e) Say that $\alpha$ covers $\beta$ if $\alpha \ge \beta$ and $\alpha \ne \beta$, and if $\alpha \ge \gamma \ge \beta$ implies that we have either $\gamma = \alpha$ or $\gamma = \beta$. For example, Fig. 8 illustrates the covering relations between binary strings of length 5. Find a simple way to describe the strings that are covered by a given binary string.
f) Show that every path $\alpha = \alpha_0, \alpha_1, \ldots, \alpha_r = 0\ldots0$ from a given string $\alpha$ to $0\ldots0$, where $\alpha_{j-1}$ covers $\alpha_j$ for $1 \le j \le r$, has the same length $r = r(\alpha)$.
g) Let $m(\alpha)$ be the number of strings $\beta$ with $\beta \ge \alpha$. Prove that $m(1\alpha) = m(\alpha)$ and $m(0\alpha) = m(\alpha) + m(\alpha')$, where $\alpha'$ is $\alpha$ with its leftmost 1 (if any) changed to 0.
h) How many strings $\alpha$ of length $n$ satisfy $\bar{\alpha} \ge \alpha$?
Verified: yes
Solve time: 12m31s
Let the order be the prefix-sum (majorization) order:
$$ \alpha \ge \beta \quad \Longleftrightarrow \quad s_k(\alpha)\ge s_k(\beta)\ \text{for all }k,\qquad s_k(\alpha)=\sum_{i=1}^k \alpha_i. $$
(b) Greatest lower bound
Define a sequence $s_k(\gamma)$ by
$$ s_k(\gamma)=\min\bigl(s_k(\alpha),s_k(\beta)\bigr),\qquad s_0(\gamma)=0. $$
Then
$$ 0 \le s_k(\gamma)-s_{k-1}(\gamma)\le 1, $$
so $\gamma_k=s_k(\gamma)-s_{k-1}(\gamma)$ defines a binary string.
If $\delta \le \alpha$ and $\delta \le \beta$, then $s_k(\delta)\le s_k(\gamma)$ for all $k$, hence $\delta \le \gamma$. Also $\gamma \le \alpha,\beta$ by construction.
Thus
$$ \alpha \wedge \beta = \gamma, \qquad s_k(\alpha\wedge\beta)=\min(s_k(\alpha),s_k(\beta)). $$
(c) Least upper bound
Define
$$ s_k(\gamma)=\max\bigl(s_k(\alpha),s_k(\beta)\bigr),\qquad \gamma_k=s_k(\gamma)-s_{k-1}(\gamma). $$
Again $0\le \gamma_k\le 1$, so $\gamma$ is a binary string.
Any upper bound $\delta$ of $\alpha,\beta$ satisfies $s_k(\delta)\ge s_k(\gamma)$, so $\gamma \le \delta$. Hence
$$ \alpha \vee \beta = \gamma, \qquad s_k(\alpha\vee\beta)=\max(s_k(\alpha),s_k(\beta)). $$
(d) Distributive laws
For each $k$,
$$ s_k(\alpha\wedge(\beta\vee\gamma)) = \min\bigl(s_k(\alpha),\max(s_k(\beta),s_k(\gamma))\bigr), $$
and
$$ s_k((\alpha\wedge\beta)\vee(\alpha\wedge\gamma)) = \max\bigl(\min(s_k(\alpha),s_k(\beta)),\min(s_k(\alpha),s_k(\gamma))\bigr). $$
Since in $\mathbb{Z}$,
$$ \min(x,\max(y,z))=\max(\min(x,y),\min(x,z)), $$
both distributive laws hold pointwise. Therefore the lattice is distributive and both identities are true.
(e) Covering relation
If $\beta < \alpha$, then $s_k(\beta)\le s_k(\alpha)$ for all $k$. A cover means no intermediate string exists, so the prefix-sum difference must be concentrated at exactly one index $k$:
$$ s_k(\alpha)=s_k(\beta)+1 \text{ for exactly one }k. $$
This is equivalent to flipping exactly one bit $1\to 0$ in $\alpha$.
Thus:
$$ \beta \text{ is covered by } \alpha \iff \beta \text{ is obtained from } \alpha \text{ by changing one }1\text{ to }0. $$
(f) Constant chain length
Each cover step changes exactly one $1$ to $0$, so decreases
$$ r(\alpha)=\sum_{i=1}^n \alpha_i $$
by exactly $1$.
Since $0^n$ has rank $0$, every maximal chain from $\alpha$ to $0^n$ has length
$$ r(\alpha). $$
Hence all such paths have the same length.
(g) Recurrences for $m(\alpha)$
Let $m(\alpha)$ be the number of $\beta$ with $\beta \ge \alpha$.
Claim 1: $m(1\alpha)=m(\alpha)$
If $\beta \ge 1\alpha$, then necessarily $\beta_1=1$. Removing the first bit gives a bijection with strings $\gamma \ge \alpha$. Thus
$$ m(1\alpha)=m(\alpha). $$
Claim 2: $m(0\alpha)=m(\alpha)+m(\alpha')$
Split $\beta \ge 0\alpha$ into two cases.
Case 1: $\beta_1=1$
Then deleting the first coordinate yields a bijection with strings $\gamma \ge \alpha$, contributing $m(\alpha)$.
Case 2: $\beta_1=0$
Define $\gamma_i=\beta_{i+1}$ (shift left).
Then for $k\ge 1$,
$$ s_k(\gamma)=s_{k+1}(\beta). $$
The condition $\beta \ge 0\alpha$ becomes:
$$ s_{k+1}(\beta)\ge s_k(\alpha)\quad \forall k. $$
Let $j$ be the leftmost position where $\alpha_j=1$. Define $\alpha'$ by changing this $1$ to $0$. Then:
- for $k<j$, $s_k(\alpha')=s_k(\alpha)$,
- for $k\ge j$, $s_k(\alpha')=s_k(\alpha)-1$.
From $\beta \ge 0\alpha$, we get:
$$ s_k(\gamma)=s_{k+1}(\beta)\ge s_k(\alpha') \quad \text{for all }k. $$
Thus $\gamma \ge \alpha'$.
Conversely, any $\gamma \ge \alpha'$ reconstructs a unique $\beta$ with $\beta_1=0$.
So this case contributes $m(\alpha')$.
Combining both cases:
$$ m(0\alpha)=m(\alpha)+m(\alpha'). $$
(h) Counting strings with $\bar{\alpha}\ge \alpha$
We compute:
$$ \bar{\alpha}_i = 1-\alpha_i,\qquad s_k(\bar{\alpha})=k-s_k(\alpha). $$
Thus
$$ \bar{\alpha}\ge \alpha \iff k-s_k(\alpha)\ge s_k(\alpha) \iff s_k(\alpha)\le \frac{k}{2}\ \forall k. $$
Equivalently, in every prefix:
$$ #{1} \le #{0}. $$
Reformulation as a path problem
Let each bit define a step:
- $0 = +1$,
- $1 = -1$.
Define
$$ T_k = #0 - #1 = k - 2s_k(\alpha). $$
Then the condition becomes:
$$ T_k \ge 0 \quad \forall k. $$
So we count length-$n$ sequences of $\pm1$ steps that never go below $0$, starting at $0$, with no restriction on final height.
This is a standard ballot-prefix enumeration.
Counting
Such sequences are exactly initial segments of Dyck-type constrained walks. A classical reflection-principle argument gives:
$$ #{\alpha:\bar{\alpha}\ge \alpha} = \binom{n}{\lfloor n/2\rfloor}. $$
Proof sketch: sequences violating the constraint first cross below $0$ at a unique time; reflecting the prefix up to that time gives a bijection with all sequences having strictly more $1$s than $0$s in the full string. The difference of the two symmetric halves of ${0,1}^n$ yields the central binomial coefficient.
Thus:
$$ \boxed{#{\alpha\in{0,1}^n:\bar{\alpha}\ge \alpha}=\binom{n}{\lfloor n/2\rfloor}}. $$
Final answers
- (b) $s_k=\min$ of prefix sums
- (c) $s_k=\max$ of prefix sums
- (d) both distributive laws: true
- (e) covers = flip one $1\to 0$
- (f) all maximal chains have length $r(\alpha)=#1$'s
- (g) $m(1\alpha)=m(\alpha)$, $m(0\alpha)=m(\alpha)+m(\alpha')$ with fully defined bijection
- (h) $\binom{n}{\lfloor n/2\rfloor}$