TAOCP 5.2.2 Exercise 1
Let $x = a_i$ and $y = a_j$ with $i < j$ and $x > y$.
Section 5.2.2: Sorting by Exchanging
Exercise 1. [**] [M20] Let $a_1 \dots a_n$ be a permutation of ${1,\dots,n}$, and let $i$ and $j$ be indices such that $i < j$ and $a_i > a_j$. Let $a_1 \dots a_n'$ be the permutation obtained from $a_1 \dots a_n$ by interchanging $a_i$ and $a_j$. Can $a_1 \dots a_n'$ have more inversions than $a_1 \dots a_n$?
Verified: yes
Solve time: 1m26s
Let $x = a_i$ and $y = a_j$ with $i < j$ and $x > y$. The inversion number changes only through pairs involving positions $i$ or $j$, since all other relative orders are unaffected by the transposition.
The pair $(i,j)$ contributes one inversion before the swap because $x > y$. After swapping, the entries become $y$ at position $i$ and $x$ at position $j$, and since $y < x$, the pair $(i,j)$ is no longer an inversion. This contributes a change of $-1$.
For any index $k$ with $i < k < j$, write $z = a_k$. Before the swap, the contributions involving $z$ are $[x > z]$ from $(i,k)$ and $[z > y]$ from $(k,j)$. After the swap, they become $[y > z]$ from $(i,k)$ and $[z > x]$ from $(k,j)$. Hence the change for this fixed $k$ equals
$$ ([y > z] + [z > x]) - ([x > z] + [z > y]). $$
If $z < y < x$, both expressions equal $1$. If $y < z < x$, the value changes from $2$ to $0$. If $y < x < z$, both expressions equal $1$. In each case the change is nonpositive, so no $k$ contributes a positive increase.
All inversion contributions not involving indices between $i$ and $j$ remain unchanged. The total change in inversion number is therefore at most $-1$, so the resulting permutation cannot have more inversions than the original permutation. This completes the proof. ∎