TAOCP 5.1.4 Exercise 41
Let $\pi = a_1 a_2 \ldots a_n$ be a permutation of $\{1,2,\ldots,n\}$.
Section 5.1.4: Tableaux and Involutions
Exercise 41. [25] (Disorder in a library.) Casual users of a library often put books back on the shelves in the wrong place. One way to measure the amount of disorder present in a library is to consider the minimum number of times we would have to take a book out of one place and insert it in another, before all books are restored to the correct order.
Thus let $\pi = a_1 a_2 \ldots a_n$ be a permutation of ${1, 2, \ldots, n}$. A "deletion-insertion operation" changes $\pi$ to
$$a_1 \ldots a_{i-1} a_{i+1} \ldots a_j , a_i , a_{j+1} \ldots a_n \qquad \text{or} \qquad a_1 \ldots a_j , a_i , a_{j+1} \ldots a_{i-1} , a_{i+1} \ldots a_n,$$
for some $i$ and $j$. Let $\text{dis}(\pi)$ be the minimum number of deletion-insertion operations that will sort $\pi$ into order. Can $\text{dis}(\pi)$ be expressed in terms of simpler characteristics of $\pi$?
Verified: yes
Solve time: 9m20s
Solution
Let $\pi = a_1 a_2 \ldots a_n$ be a permutation of ${1,2,\ldots,n}$.
A deletion‑insertion operation removes one element $a_i$ and inserts it at an arbitrary position (before some $a_j$ if $j < i$, or after $a_j$ if $j \ge i$).
We denote by $\operatorname{dis}(\pi)$ the minimum number of such operations needed to transform $\pi$ into the sorted order $1,2,\ldots,n$.
The answer is yes: $\operatorname{dis}(\pi)$ can be expressed in terms of the longest increasing subsequence of $\pi$.
Theorem
[ \operatorname{dis}(\pi) = n - \operatorname{LIS}(\pi), ] where $\operatorname{LIS}(\pi)$ is the length of the longest increasing subsequence of $\pi$.
Equivalently, if we apply Algorithm I (Schensted insertion) to the sequence $a_1, a_2, \ldots, a_n$ and obtain the $P$‑tableau of shape $\lambda = (\lambda_1, \lambda_2, \ldots)$, then $\operatorname{LIS}(\pi) = \lambda_1$ and therefore $\operatorname{dis}(\pi) = n - \lambda_1$.
Proof
1. Lower bound: $\operatorname{dis}(\pi) \ge n - \operatorname{LIS}(\pi)$.
Consider any deletion‑insertion operation. It takes an element $x = a_i$ and moves it to a new position, leaving the relative order of all other elements unchanged. Let $\pi'$ be the permutation after the operation. Any increasing subsequence of $\pi'$ either does not contain $x$ (hence is an increasing subsequence of $\pi$ as well) or contains $x$. In the latter case, removing $x$ from that subsequence leaves an increasing subsequence of $\pi$ (since the other elements appear in the same order in $\pi$). Thus
[
\operatorname{LIS}(\pi') \le \operatorname{LIS}(\pi) + 1.
]
Starting from $\pi$ we need at least $n - \operatorname{LIS}(\pi)$ operations to reach the identity permutation, whose LIS is $n$.
2. Upper bound: $\operatorname{dis}(\pi) \le n - \operatorname{LIS}(\pi)$.
Fix a longest increasing subsequence of $\pi$; its length is $\operatorname{LIS}(\pi)$. The elements of this subsequence are already in the correct relative order. We can sort $\pi$ by repeatedly taking an element not in this subsequence and inserting it into its proper position among the elements of the subsequence (and the previously inserted elements). Each such operation places one element correctly without disturbing the relative order of the subsequence. After exactly $n - \operatorname{LIS}(\pi)$ moves all elements are in place.
3. Connection with the $P$‑tableau.
Algorithm I (Schensted insertion) applied to the sequence $a_1, a_2, \ldots, a_n$ produces a standard Young tableau $P$. It is a fundamental property of the Robinson-Schensted correspondence that the length $\lambda_1$ of the first row of $P$ equals $\operatorname{LIS}(\pi)$. Hence $\operatorname{dis}(\pi) = n - \lambda_1$.
This completes the proof. ∎
Notes
The operation considered here is exactly the “move” operation used in insertion sort. The identity $\operatorname{dis}(\pi) = n - \operatorname{LIS}(\pi)$ is classical; it follows immediately from the fact that an element move can increase the longest increasing subsequence by at most one, and that the elements outside a longest increasing subsequence can be inserted one by one into their correct positions. The connection with the $P$‑tableau places the result in the context of Theorem A (Section 5.1.4).