TAOCP 5.1.1 Exercise 28

Let \(a_1 a_2 \ldots a_n\) be a permutation of \(\{1,2,\ldots,n\}\).

taocpmathematicsalgorithmsvolume-3medium

Section 5.1.1: Inversions

Exercise 28. ▶ [25] If $a_1 a_2 \ldots a_n$ is a permutation of ${1, 2, \ldots, n}$, its total displacement is defined to be $\sum_{j=1}^{n} |a_j - j|$. Find upper and lower bounds for total displacement in terms of the number of inversions.

Verified: yes
Solve time: 1h44m

Solution

Let (a_1 a_2 \ldots a_n) be a permutation of ({1,2,\ldots,n}). Its total displacement is [ D = \sum_{j=1}^n |a_j - j|, ] and its number of inversions is [ I = #{(i,j)\mid 1\le i<j\le n,; a_i > a_j}. ] We prove the following universal bounds [ \boxed{I \le D \le 2I}. ]

Upper bound (D \le 2I)

For each element (x\in{1,\ldots,n}) let (p(x)) be its position in the permutation, i.e. (a_{p(x)} = x).
The displacement of (x) is (d(x) = |p(x)-x|).
The inversions involving (x) are exactly the pairs ((x,y)) with (y<x) and (p(y)>p(x)) (where (x) is the larger element) together with the pairs ((y,x)) with (y>x) and (p(y)<p(x)) (where (x) is the smaller element). Denote this number by (\text{inv}(x)).

We show that (\text{inv}(x) \ge d(x)) for every (x).

  • Case (p(x) < x) (x moved left).
    All elements smaller than (x) are ({1,\ldots,x-1}). There are (p(x)-1) positions to the left of (x); at most all of them can be occupied by smaller elements. Hence the number of smaller elements to the right of (x) is at least ((x-1) - (p(x)-1) = x-p(x) = d(x)). These are precisely the inversions where (x) is the larger element. Inversions where (x) is the smaller element are non‑negative, so (\text{inv}(x) \ge d(x)).

  • Case (p(x) > x) (x moved right).
    The elements larger than (x) are ({x+1,\ldots,n}), totalling (n-x). There are (n-p(x)) positions to the right of (x); at most all of them can be occupied by larger elements. Thus the number of larger elements to the left of (x) is at least ((n-x) - (n-p(x)) = p(x)-x = d(x)). These are the inversions where (x) is the smaller element, so (\text{inv}(x) \ge d(x)).

  • Case (p(x) = x).
    Then (d(x)=0) and (\text{inv}(x)\ge 0) trivially.

In all cases (\text{inv}(x) \ge d(x)). Summing over all (x) gives [ \sum_{x=1}^n \text{inv}(x) \ge \sum_{x=1}^n d(x) = D. ] Every inversion is counted exactly twice in the sum (\sum \text{inv}(x)) (once for each of its two elements), therefore (\sum \text{inv}(x) = 2I). Hence [ 2I \ge D \qquad\Longrightarrow\qquad D \le 2I. ]

Lower bound (I \le D)

We proceed by induction on (n).

  • Base case (n=1). The only permutation is ([1]); (I=0), (D=0), so (0\le 0) holds.

  • Inductive step. Assume the inequality holds for all permutations of length (n-1) ((n\ge 2)). Consider a permutation (a_1\ldots a_n) of ({1,\ldots,n}). Let (p) be the position of the maximum element (n) (so (a_p = n)).

    If (p = n), then (n) is fixed. It contributes (0) to both (D) and (I). Removing (n) leaves a permutation of ({1,\ldots,n-1}) whose displacement and inversion count are unchanged. By the induction hypothesis the inequality holds for it, hence for the original permutation.

    If (p < n), then (n) has moved left by (d = n-p) places.

    • Its displacement contribution is (d).
    • Every element to the right of (n) is smaller than (n), so (n) forms exactly (d) inversions (with those elements).
    • Removing (n) and shifting the tail left by one position yields a permutation of ({1,\ldots,n-1}). For the elements to the right of (n) (originally at positions (j = p+1,\ldots,n)) the new displacement is (|a_j - (j-1)| = |(a_j-j)+1| \ge |a_j-j| - 1). The elements to the left of (n) keep their displacement unchanged. Therefore the displacement (D') of the ((n-1))-permutation satisfies [ D' \ge \Bigl(\sum_{j=1}^{p-1}|a_j-j|\Bigr) + \sum_{j=p+1}^n\bigl(|a_j-j|-1\bigr) = D - d - d = D - 2d. ] The new inversion count is (I' = I - d) (the (d) inversions involving (n) are gone). By the induction hypothesis (D' \ge I'). Substituting, [ D - 2d \ge I - d \quad\Longrightarrow\quad D \ge I + d \ge I. ]

Thus in all cases (D \ge I), completing the induction.

Verification of tightness

The upper bound (D = 2I) is attained, for example, by any permutation that is a product of disjoint adjacent transpositions, such as (2,1,4,3,6,5\ldots). In such a permutation every element either stays in place ((d=0), (\text{inv}=0)) or swaps with an adjacent neighbour ((d=1), (\text{inv}=1)), giving (\text{inv}(x)=d(x)) for all (x) and hence (2I = D).

The lower bound (D = I) is attained only by the identity permutation ((I=0), (D=0)). For any non‑identity permutation we have (D > I) (the induction proof shows that whenever the maximum element is not fixed, (D \ge I+d > I); if it is fixed, the inequality for the remaining permutation forces a strict inequality unless the whole permutation is the identity).

Therefore the best possible universal bounds depending only on the number of inversions are [ I \le D \le 2I. ]

This completes the proof. ∎