TAOCP 5.1.3 Exercise 20
Let $\pi = a_1 a_2 \ldots a_n$ be a permutation of $\{1,2,\ldots,n\}$.
Exercise 20. ▶ [M21] A permutation is said to require $k$ readings if we must scan it $k$ times from left to right in order to read off its elements in nondecreasing order. For example, the
permutation $4,9,1,8,2,5,3,6,7$ requires four readings: On the first we obtain 1, 2, 3; on the second we get 4, 5, 6, 7; then 8; then 9. Find a connection between runs and readings.
Verified: yes
Solve time: 17m49s
Solution
Let $\pi = a_1 a_2 \ldots a_n$ be a permutation of ${1,2,\ldots,n}$. For each $x \in {1,\ldots,n}$ denote by $\operatorname{pos}(x)$ the index $i$ such that $a_i = x$. The inverse permutation is $\sigma = \pi^{-1}$, written as the sequence [ \sigma = \bigl(\operatorname{pos}(1),, \operatorname{pos}(2),, \ldots,, \operatorname{pos}(n)\bigr). ]
A reading of $\pi$ is defined by the following procedure: set the target value $t = 1$; scan the permutation from left to right; whenever the current element equals $t$, output $t$ and increment $t$; when the scan reaches the end, if $t \le n$ start a new scan from the left with the current $t$. The number of scans required is the number of readings.
Consider one reading. It starts with some value $c$ (initially $c=1$). The reading outputs $c$, then continues scanning to the right. It outputs $c+1$ iff $\operatorname{pos}(c+1) > \operatorname{pos}(c)$, otherwise the scan ends before reaching $c+1$ and the value $c+1$ must wait for the next reading. By induction, the reading outputs a maximal block of consecutive integers [ {c,, c+1,, \ldots,, d} ] such that [ \operatorname{pos}(c) < \operatorname{pos}(c+1) < \cdots < \operatorname{pos}(d), ] and either $d = n$ or $\operatorname{pos}(d) > \operatorname{pos}(d+1)$. The next reading then begins with $d+1$.
Thus the readings partition ${1,\ldots,n}$ into blocks of consecutive integers; the boundaries between blocks are exactly the indices $i$ ($1 \le i < n$) for which [ \operatorname{pos}(i) > \operatorname{pos}(i+1). ]
Now examine the runs of the inverse permutation $\sigma$. By definition, a run (ascending run) of $\sigma$ is a maximal contiguous increasing subsequence. A run ends at position $i$ precisely when $\sigma_i > \sigma_{i+1}$, i.e., when $\operatorname{pos}(i) > \operatorname{pos}(i+1)$. The first run starts at $i=1$. Therefore the number of runs in $\sigma$ equals the number of indices $i$ with $\operatorname{pos}(i) > \operatorname{pos}(i+1)$, plus one.
Comparing the two descriptions, the boundaries between readings coincide exactly with the boundaries between runs of $\sigma$. Hence
The number of readings of a permutation $\pi$ equals the number of ascending runs in its inverse permutation $\pi^{-1}$.
Since the map $\pi \mapsto \pi^{-1}$ is a bijection on the symmetric group $S_n$, the number of permutations of $n$ elements that require exactly $k$ readings is the same as the number of permutations with exactly $k$ runs. By equation (1) of the text, this number is the Eulerian number $\left\langle n \atop k-1 \right\rangle$.
∎
Notes
The example $4,9,1,8,2,5,3,6,7$ has inverse $3,5,7,1,6,8,9,4,2$, which indeed has four runs: $3,5,7 \mid 1,6,8,9 \mid 4 \mid 2$. The exercise reveals that the statistic “number of readings” is equidistributed with the statistic “number of runs” (Eulerian numbers), even though they are not identical on a given permutation.