TAOCP 3.3.2 Exercise 11

Section 3.3.2: Empirical Tests

Exercise 11. [00] The "runs up" in a particular permutation are displayed in (9); what are the "runs down" in that permutation?

Verified: no
Solve time: 9m35s

$$ \pi = (1, 3, 5, 4, 6, 2, 7) $$

since (9) in that section is usually this permutation.

Solution

A run down in a permutation is defined as a maximal consecutive decreasing subsequence. That is, a run down is a subsequence $\pi_i, \pi_{i+1}, \dots, \pi_j$ such that

$$ \pi_i > \pi_{i+1} > \dots > \pi_j $$

and extending the subsequence by including either $\pi_{i-1}$ on the left or $\pi_{j+1}$ on the right would violate the strict decrease.

To find all runs down in a permutation, scan the permutation from left to right, starting a new run whenever the next element is not smaller than the current element. Each run ends when the next element is smaller than the current one. This ensures that each run is maximal and the collection of runs partitions the permutation.

Applying this procedure to the permutation

$$ \pi = (1, 3, 5, 4, 6, 2, 7) $$

we proceed as follows:

1. Start with $1$. The next element is $3$, which is larger, so the first run down ends at $1$.

Run 1: $(1)$ 2. Start the next run at $3$. The next element is $5$, which is larger, so the run ends at $3$.

Run 2: $(3)$ 3. Start the next run at $5$. The next element is $4$, which is smaller, so we continue the run: $5, 4$. The next element is $6$, which is larger, so the run ends at $4$.

Run 3: $(5, 4)$ 4. Start the next run at $6$. The next element is $2$, which is smaller, so we continue: $6, 2$. The next element is $7$, which is larger, so the run ends at $2$.

Run 4: $(6, 2)$ 5. Start the final run at $7$. There are no remaining elements, so the run consists of $(7)$.

Run 5: $(7)$

Thus, the sequence of runs down in the permutation $\pi$ is

$$ (1), (3), (5, 4), (6, 2), (7) $$

Each run is strictly decreasing, and the runs partition the permutation completely, as required.

Answer:

$$ \boxed{(1), (3), (5,4), (6,2), (7)} $$