TAOCP 5.2.1 Exercise 12
A 2-ordered permutation $a_1a_2\cdots a_n$ satisfies a_i<a_{i+2}\qquad (1\le i\le n-2).
Section 5.2.1: Sorting by Insertion
Exercise 12. [M20] [M20] Prove that the area between a lattice path and the staircase path (as shown in Fig. 11) equals the number of inversions in the corresponding 2-ordered permutation.
Verified: yes
Solve time: 2m46s
Solution
A 2-ordered permutation $a_1a_2\cdots a_n$ satisfies
$$ a_i<a_{i+2}\qquad (1\le i\le n-2). $$
Hence the odd-positioned entries
$$ a_1,a_3,a_5,\ldots $$
form an increasing sequence, and the even-positioned entries
$$ a_2,a_4,a_6,\ldots $$
also form an increasing sequence.
The lattice-path representation of such a permutation is obtained by scanning the integers
$$ 1,2,\ldots,n. $$
For each integer $k$, take an east step if $k$ occurs in an odd position of the permutation, and a north step if $k$ occurs in an even position. Since the odd and even subsequences are increasing, this path determines the permutation uniquely.
Let
$$ O={o_1<o_2<\cdots<o_r} $$
be the set of entries occurring in odd positions, and
$$ E={e_1<e_2<\cdots<e_s} $$
the set of entries occurring in even positions. Then
$$ a_1=o_1,\ a_3=o_2,\ldots, \qquad a_2=e_1,\ a_4=e_2,\ldots . $$
The staircase path of Fig. 11 is the alternating path
$$ ENENEN\cdots , $$
which separates the cells corresponding to pairs $(o_i,e_j)$ with $o_i<e_j$ from those with $o_i>e_j$.
Consider a cell whose southwest corner has coordinates $(i-1,j-1)$. This cell corresponds to the pair $(o_i,e_j)$. The cell lies between the lattice path and the staircase path precisely when
$$ e_j<o_i. $$
Indeed, after the integers $1,\ldots,m$ have been processed, the horizontal coordinate equals the number of odd-position entries not exceeding $m$, and the vertical coordinate equals the number of even-position entries not exceeding $m$. Therefore the lattice path passes to the southeast of the cell exactly when $e_j$ is encountered before $o_i$, that is, when $e_j<o_i$.
Now examine inversions of the permutation. Since the odd subsequence and the even subsequence are each increasing, an inversion cannot occur between two odd positions or between two even positions. Every inversion must involve adjacent parity classes. Thus inversions are exactly the pairs
$$ (a_{2j},a_{2i-1}) =(e_j,o_i) $$
for which
$$ e_j>o_i $$
fails, equivalently,
$$ e_j<o_i. $$
For each pair $(o_i,e_j)$ with $e_j<o_i$, the entry $o_i$ appears in the odd position $2i-1$, while $e_j$ appears in the earlier even position $2j$. Since $e_j<o_i$, the pair $(e_j,o_i)$ is an inversion. Conversely, every inversion arises in this way.
Hence there is a bijection:
$$ {\text{cells between the lattice path and the staircase path}} \longleftrightarrow {\text{inversions of the 2-ordered permutation}}, $$
given by
$$ (o_i,e_j)\longleftrightarrow (e_j,o_i), $$
where both sides are characterized by the same inequality $e_j<o_i$.
Each cell contributes one unit of area, so the area between the two paths equals the number of such cells. By the bijection above, this number is exactly the number of inversions of the corresponding 2-ordered permutation.
This completes the proof.
∎