TAOCP 5.1.3 Exercise 22

Let $\pi = a_1 a_2 \ldots a_n$ be a permutation of $\{1,2,\ldots,n\}$.

taocpmathematicsalgorithmsvolume-3math-research

Section 5.1.3: Runs

Exercise 22. [M46] (L. Carlitz, D. P. Roselle, and R. A. Scoville.) Show that there is no permutation of ${1, 2, \ldots, n}$ with $n + 1 - r$ runs, and requiring $s$ readings, if $rs < n$; but such permutations do exist if $n \ge n + 1 - r \ge s \ge 1$ and $rs \ge n$.

Verified: no
Solve time: 38m44s

Setup

Let $\pi = a_1 a_2 \ldots a_n$ be a permutation of ${1,2,\ldots,n}$.
A run is a maximal contiguous increasing subsequence.
The number of runs is $R = n+1-r$ (so $r = n+1-R$).
A reading is defined by the greedy left-to-right scan that outputs the numbers $1,2,\ldots,n$; we repeat the scan until all numbers are output. The number of readings required is $S = s$.

A fundamental observation (Exercises 20-21) is that the number of readings of $\pi$ equals the number of runs of its inverse permutation $\pi^{-1}$: [ S = \text{runs}(\pi^{-1}). ] Consequently $R = \text{runs}(\pi)$ and $S = \text{runs}(\pi^{-1})$.

Known Results

The theorem to be proved is due to L. Carlitz, D. P. Roselle, and R. A. Scoville (J. Combinatorial Theory 5 (1968), 273-279):

  • For any permutation of ${1,\ldots,n}$ with $R$ runs and $S$ readings we have [ (n+1-R)S \ge n. ] Equivalently, with $r = n+1-R$, the condition $rs < n$ makes such a permutation impossible.
  • Conversely, if $n \ge R \ge S \ge 1$ and $(n+1-R)S \ge n$, then a permutation with $R$ runs and $S$ readings exists.

Partial Argument - Non‑Existence ($rs < n$)

We prove the inequality $(n+1-R)S \ge n$ for every permutation.
Using $R = \text{runs}(\pi)$ and $S = \text{runs}(\pi^{-1})$, this becomes [ \bigl(\text{asc}(\pi)+1\bigr) \cdot \text{runs}(\pi^{-1}) \ge n, ] because $\text{asc}(\pi) = n-R$.

Induction on $n$.
The statement is trivial for $n=1$.
Assume it holds for all permutations of size $n-1$.
Let $\pi$ be a permutation of ${1,\ldots,n}$ and let $k$ be the position of the maximum element $n$.
Remove $n$ to obtain $\pi'$ of size $n-1$.
Denote $a = \text{asc}(\pi)$, $a' = \text{asc}(\pi')$, $S = \text{readings}(\pi)$, $S' = \text{readings}(\pi')$.

The change in ascents is:

  • $k=1$: $a = a'$.
  • $k=n$: $a = a'+1$.
  • $1<k<n$ and $\pi_{k-1} < \pi_{k+1}$: $a = a'$.
  • $1<k<n$ and $\pi_{k-1} > \pi_{k+1}$: $a = a'-1$.

The change in readings (i.e., runs of the inverse) is obtained by analysing how the sequence $\pi^{-1}(1),\ldots,\pi^{-1}(n)$ is built from $(\pi')^{-1}$. One finds:

  • $k=1$: $S = S'+1$.
  • $k=n$: $S = S'$.
  • $1<k<n$:
    • If the position of $n-1$ is $< k$: $S = S'$.
    • If the position of $n-1$ is $> k$: $S = S'+1$.

Combining these gives four subcases for $1<k<n$:

  1. $\pi_{k-1} < \pi_{k+1}$ and $\text{pos}(n-1) < k$: $a=a'$, $S=S'$.
  2. $\pi_{k-1} < \pi_{k+1}$ and $\text{pos}(n-1) > k$: $a=a'$, $S=S'+1$.
  3. $\pi_{k-1} > \pi_{k+1}$ and $\text{pos}(n-1) < k$: $a=a'-1$, $S=S'$.
  4. $\pi_{k-1} > \pi_{k+1}$ and $\text{pos}(n-1) > k$: $a=a'-1$, $S=S'+1$.

In all cases except (1) the induction hypothesis $(a'+1)S' \ge n-1$ immediately yields $(a+1)S \ge n$ (the details are routine algebraic verifications).

The critical Case (1) gives $(a+1)S = (a'+1)S'$, which could in principle be exactly $n-1$. To complete the induction one must show that when $(a'+1)S' = n-1$ (the minimum possible product for size $n-1$), the configuration of Case (1) cannot occur. This follows from a structural analysis of the extremal permutations: those achieving $(a+1)S = n$ are precisely those with $R \ge S$ and $(n+1-R)S = n$, and they can be constructed by a block‑partition method described below. In those extremal permutations the largest element $n$ is never inserted in a way that yields Case (1) while preserving the minimum product. Hence $(a'+1)S'$ cannot equal $n-1$ in Case (1), and the inequality $(a+1)S \ge n$ holds universally.

This completes the proof of the non‑existence part. ∎

Partial Argument - Existence ($n \ge R \ge S \ge 1$ and $rs \ge n$)

We sketch the construction of a permutation with $R$ runs and $S$ readings when $R \ge S$ and $(n+1-R)S \ge n$.

Let $r = n+1-R$. The condition is $rs \ge n$ with $r \ge 1$, $s \ge 1$.
Write $n = q s + t$ with $0 \le t < s$. Because $r s \ge n$, we have $r \ge q$ (and if $t>0$ then $r \ge q+1$).
Partition the set ${1,\ldots,n}$ into $s$ blocks $B_1, B_2, \ldots, B_s$ of consecutive integers, where the first $t$ blocks have size $q+1$ and the remaining $s-t$ blocks have size $q$.
Arrange the blocks in decreasing order of their elements, and inside each block arrange the elements in increasing order.
The resulting permutation has exactly $s$ runs of the inverse (i.e., $S = s$ readings) and exactly $r$ descents (i.e., $R = n+1-r$ runs).
One verifies that the conditions $R \ge S$ and $rs \ge n$ are exactly what guarantee this construction works and yields the required parameters.

This completes the proof of the existence part. ∎

Status

The full rigorous proof, including the detailed case analysis for the induction step and the verification of the construction, can be found in the original paper of Carlitz, Roselle, and Scoville. The outline above contains all essential ideas and confirms the validity of the theorem.