Up Main page

Let σ∈Sn. The pair (i,j) gives an inversion of σ if i<j and σ(i)>σ(j). (This should not be confused with the inverse permutation discussed above.)

The total number of inversions of σ is denoted by #inv(σ).

Examples

  1. The identity permutation has no inversions because for every pair (i,j) with i<j, σ(i)=i<j=σ(j). For example, one can see that there are no inversions of the identity permuation from S4: (12341234).

  2. Consider σ=(123312). The pair (1,2) is an inversion of σ because with i=1 and j=2, we have i<j and σ(i)=3>1=σ(j). The remaining inversion is given by the pair (1,3). Thus #inv(σ)=2.

  3. Let σ∈Sn be such that there exist i,j∈{1,…,n}, i<j such that σ(i)=j, σ(j)=i, and σ(k)=k for all k∈{1,…,i−1,i+1,…,j−1,j+1,…,n}. In other words, σ only swaps i and j. We want to determine #inv(σ).

    Note that for each k=i+1,…,j−1, (i,k) is an inversion because i<k and σ(i)=j>k=σ(k).

    Also, for each k=i+1,…,j−1), (k,j) is an inversion because k<j and σ(j)=i>k=σ(k).

    4. Finally, the remaining inversion is (i,j). Thus, #inv(σ)=2(j−1−(i+1)+1)+1=2(j−i)−1, which is always odd.

    For example, the inversions of (1234514325) are (2,3), (3,4), and (2,4).

Quick Quiz

Exercises

For each of the following permutations, give the number of inversions and the inverse permutation.

  1. (12341324)  

  2. (12344321)  

  3. (1234551423)