TAOCP 5.1.3 Exercise 21
Let $\pi = a_1 a_2 \ldots a_n$ be a permutation of $\{1,2,\ldots,n\}$.
Exercise 21. [M22] If the permutation $a_1 a_2 \ldots a_n$ of ${1, 2, \ldots, n}$ has $k$ runs and requires $j$ readings, in the sense of exercise 20, what can be said about $a_n \ldots a_2 a_1$?
Verified: yes
Solve time: 16m51s
Solution
Let $\pi = a_1 a_2 \ldots a_n$ be a permutation of ${1,2,\ldots,n}$. By hypothesis $\pi$ has $k$ (ascending) runs and requires $j$ readings.
Runs of the reversed permutation.
A run is a maximal contiguous increasing subsequence; the number of runs equals one plus the number of descents $a_i > a_{i+1}$. The reversed permutation is $\pi^r = a_n a_{n-1} \ldots a_1$. For $1 \le i < n$, a descent in $\pi^r$ at position $i$ means $a_{n+1-i} > a_{n-i}$, which in $\pi$ is exactly the ascent $a_{n-i} < a_{n+1-i}$. The number of ascents in $\pi$ is $(n-1) - (k-1) = n-k$. Hence $\pi^r$ has $n-k$ descents and therefore $(n-k)+1 = n-k+1$ runs.
Readings and the inverse permutation.
A reading of $\pi$ is a left‑to‑right scan that extracts the next needed element in the order $1,2,\ldots,n$. Let $\operatorname{pos}(i)$ be the position of value $i$ in $\pi$. In the first scan we pick $1,2,\ldots,m_1$ where $m_1$ is the largest index with $\operatorname{pos}(1) < \operatorname{pos}(2) < \cdots < \operatorname{pos}(m_1)$. The second scan picks $m_1+1,\ldots,m_2$ with $\operatorname{pos}(m_1+1) < \cdots < \operatorname{pos}(m_2)$, and so on. Thus the number of readings $j$ equals the number of maximal contiguous increasing subsequences (runs) in the sequence $\operatorname{pos}(1), \operatorname{pos}(2), \ldots, \operatorname{pos}(n)$. This sequence is precisely the inverse permutation $\pi^{-1}$; consequently $j$ is the number of runs in $\pi^{-1}$.
Readings of the reversed permutation.
In $\pi^r$ the position of value $i$ is $n+1 - \operatorname{pos}(i)$. Hence the inverse of $\pi^r$ is the sequence $q_i = n+1 - \operatorname{pos}(i)$ for $i=1,\ldots,n$. A descent in $(q_i)$ occurs when $q_i > q_{i+1}$, i.e., $\operatorname{pos}(i) < \operatorname{pos}(i+1)$. Therefore the number of descents in $(q_i)$ equals the number of ascents in $\pi^{-1}$. The sequence $\pi^{-1}$ has length $n$ and $j$ runs, so it has $j-1$ descents and $(n-1)-(j-1) = n-j$ ascents. Hence $(q_i)$ has $n-j$ descents, giving $(n-j)+1 = n-j+1$ runs. This is the number of readings of $\pi^r$.
Conclusion.
The reversed permutation $a_n a_{n-1} \ldots a_1$ has $n-k+1$ runs and requires $n-j+1$ readings.
\boxed{\text{The reversed permutation has } n - k + 1 \text{ runs and requires } n - j + 1 \text{ readings.}}