TAOCP 6.5 Exercise 1

Let $0 \le k \le n/2$.

taocpmathematicsalgorithmsvolume-3math-hard

Section 6.5: Retrieval on Secondary Keys

Exercise 1. ▶ [M27] Let $0 \le k \le n/2$. Prove that the following construction produces $\binom{n}{k}$ permutations of ${1,2,\ldots,n}$ such that every $t$-element subset of ${1,2,\ldots,n}$ appears as the first $t$ elements of at least one of the permutations, for $t \le k$ or $t \ge n-k$: Consider a path in the plane from $(0,0)$ to $(n,r)$ where $r \ge n-2k$, in which the $i$th step is from $(i-1,j)$ to $(i,j+1)$ or to $(i,j-1)$; the latter possibility is allowed only if $j \ge 1$, so that the path never goes below the $x$ axis. There are exactly $\binom{n}{k}$ such paths. For each path of this kind, a permutation is constructed as follows, using three lists that are initially empty: For $i = 1,2,\ldots,n$, if the $i$th step of the path goes up, put the number $i$ into list $B$; if the step goes down, put $i$ into list $A$ and move the currently largest element of list $B$ into list $C$. The resulting permutation is equal to the final contents of list $A$, then list $B$, then list $C$, each list in increasing order. For example, when $n = 4$ and $k = 2$, the six paths and permutations defined by this procedure are

  |1 2 3 4|          2|3 4|1       2 4|1 3       3|1 4|2    3 4|1 2       4|1 2|3

(Vertical lines show the division between lists $A$, $B$, and $C$. These six permutations correspond to the compound attributes in (8).) Hint: Represent each $t$-element subset $S$ by a path that goes from $(0,0)$ to $(n,n-2t)$, whose $i$th step runs from $(i-1,j)$ to $(i,j+1)$ if $i \notin S$ and to $(i,j-1)$ if $i \in S$. Convert every such path into an appropriate path having the special form stated above.

Verified: no
Solve time: 15m57s

Setup

Let $0 \le k \le n/2$. We are given a construction that produces $\binom{n}{k}$ permutations of ${1,2,\ldots,n}$:

  • A path is a sequence of $n$ steps from $(0,0)$ to $(n,r)$ with $r \ge n-2k$. The $i$-th step goes from $(i-1,j)$ to $(i,j+1)$ (up) or to $(i,j-1)$ (down); a down step is allowed only when $j\ge 1$, so the path never goes below the $x$-axis. There are exactly $\binom{n}{k}$ such paths.
  • From a path we build three lists $A,B,C$ (initially empty). For $i=1,\ldots,n$:
    • if the $i$-th step is up, put $i$ into $B$;
    • if the $i$-th step is down, put $i$ into $A$ and move the largest element of $B$ into $C$.
  • The resulting permutation is the concatenation of $A$, $B$, $C$, each written in increasing order.

We must prove that for every $t$-element subset $S\subseteq{1,\ldots,n}$ with $t\le k$ or $t\ge n-k$, at least one of these permutations has $S$ as the set of its first $t$ elements.

Solution

1. Representing $S$ by a path

For any $t$-element set $S$, define a path $P_S$ of length $n$ by taking a down step at positions in $S$ and an up step at positions in $\overline{S} = {1,\ldots,n}\setminus S$. $P_S$ starts at $(0,0)$ and ends at $(n,,n-2t)$. It may go below the $x$-axis.

2. Matching on $P_S$

Process the steps of $P_S$ from left to right, maintaining a stack of indices of up steps that have not yet been matched with a down step.

  • On an up step at $i$, push $i$ onto the stack.
  • On a down step at $i$:
    • if the stack is nonempty, pop its top element (matching this down step with that up step);
    • if the stack is empty, this down step is unmatched; add $i$ to a set $R$.

Let $M_P$ be the set of up steps that get matched, and $U_P^{\text{unmatched}} = \overline{S}\setminus M_P$ be the unmatched up steps (the stack contents at the end). The unmatched down steps are exactly $R$.

Key observation: Every element of $U_P^{\text{unmatched}}$ is larger than every element of $R$.
Proof. An unmatched up step is pushed and never popped. If it occurred before some $r\in R$, then at step $r$ the stack would contain that up step, so $r$ would not be unmatched. Hence all $r\in R$ occur before all unmatched up steps. ∎

3. Converting $P_S$ to a valid path $Q$

Construct a new path $Q$ by changing every step in $R$ from down to up. All other steps stay the same. Thus $Q$ has down steps $A = S\setminus R$ and up steps $U_Q = \overline{S} \cup R$.

Lemma 1. $Q$ never goes below the $x$-axis.
Proof. In $P_S$ the height is the stack size. The unmatched down steps $R$ are exactly those that occur when the height is $0$ and would make it $-1$. Changing them to up steps increases the height from that point onward by $2$. The minimum height of $P_S$ is $-|R|$; after the changes the minimum becomes $-|R|+2|R| = |R| \ge 0$. ∎

4. Behaviour of the matching on $Q$

Run the same stack algorithm on $Q$. Because the steps in $R$ are now up steps, they are pushed onto the stack at their positions. The segment of $P_S$ between two consecutive elements of $R$ (or before the first / after the last) starts and ends with an empty stack and contains no unmatched down steps. In $Q$ such a segment starts with the stack containing the elements of $R$ seen so far. Its internal pushes and pops cancel perfectly, so it leaves the elements of $R$ still on the stack. After the last element of $R$, the remaining segment of $P_S$ starts empty and finishes with stack $U_P^{\text{unmatched}}$. In $Q$ this segment starts with the stack containing all of $R$, and after its internal cancellation the final stack becomes $R$ followed by $U_P^{\text{unmatched}}$ (in the order of indices).

Therefore the unmatched up steps of $Q$ are [ B = R \cup U_P^{\text{unmatched}}, ] and because $\max(R) < \min(U_P^{\text{unmatched}})$ (when both are nonempty), the list $B$ written in increasing order begins with all elements of $R$, then all elements of $U_P^{\text{unmatched}}$. The matched up steps of $Q$ are $C = M_P$.

5. The permutation of $Q$ has prefix $S$

The permutation produced from $Q$ is $A$ (increasing), then $B$ (increasing), then $C$ (increasing). We have [ |A| = |S| - |R| = t - |R|,\qquad |R| \le t. ] The first $t$ elements of this permutation are therefore all of $A$ (size $t-|R|$) followed by the first $|R|$ elements of $B$. By the previous section, the first $|R|$ elements of $B$ are exactly $R$. Hence the set of the first $t$ elements is [ A \cup R = (S\setminus R) \cup R = S. ]

6. $Q$ belongs to the prescribed family

It remains to check that $Q$ satisfies the conditions of the construction:

  • $Q$ never goes below the $x$-axis (Lemma 1).
  • $Q$ ends at height $r = n - 2|A| = n - 2(t-|R|) = n-2t+2|R|$. We need $r \ge n-2k$.
    • If $t \le k$, then $r \ge n-2t \ge n-2k$ because $|R|\ge 0$.
    • If $t \ge n-k$, the minimum height of $P_S$ is at most its final height $n-2t$, so $-|R| \le n-2t$, i.e. $|R| \ge 2t-n$. Then [ r = n-2t+2|R| \ge n-2t+2(2t-n) = 2t-n. ] Since $t \ge n-k$, we have $2t-n \ge n-2k$, so $r \ge n-2k$. In both cases $r \ge n-2k$, which is equivalent to $|A| = t-|R| \le k$.

Thus $Q$ is one of the $\binom{n}{k}$ paths described in the problem, and the corresponding permutation has $S$ as its first $t$ elements.

Verification

  • Example $n=4,k=2$. The six valid paths and their permutations are listed in the problem statement. For every $t\le 2$ and $t\ge 2$ all $\binom{4}{t}$ subsets appear as prefixes of these permutations.
  • Boundary cases. $t=0$: $S=\emptyset$, any permutation works (empty prefix). $t=n$: $S={1,\ldots,n}$, the permutation from the all-up path $U^n$ is $1,2,\ldots,n$ and its first $n$ elements are $S$.
  • Independent check of the height bound. The condition $t\ge n-k$ gives $2t-n \ge t-k$. Because $|R|\ge 2t-n$, we have $|R|\ge t-k$, so $t-|R|\le k$, matching the requirement that the number of down steps of $Q$ is at most $k$.

This completes the proof. ∎