π = Permutation([3,1,2,5,4])
π.inversions()[(1, 2), (1, 3), (4, 5)]8 Inversions
We present a second (or third depending if you count the proof we didn’t prove) proof that the number of transpositions is always ever even or always odd.
Let \(\pi\) be a permutation. An inversion for \(\pi\) is a pair of outputs which are not in sorted order. I.e. we have \(i < j\) to begin with and \(\pi(i) > \pi(j)\) to end with.
In counting inversions, we look at where \(\pi(i)\) is greater than \(\pi(j)\) for some \(j\) that comes after \(i\).
Example 8.1 Consider the permutation represented by \(31254\).
We have \(\pi(1) = 3\) and this is greater than both \(\pi(2) = 1, \pi(3) = 2\).
We have \(\pi(2) = 1\) but this is not greater than anything that comes after.
We have \(\pi(3) = 2\) but this is not greater than anything that comes after.
We have \(\pi(4) = 5\) which is greater than \(\pi(5) = 4\).
So this permutation has \(3\) inversions: \((1 < 2) \to (\pi(1) > \pi(2))\) and \((1 < 3) \to (\pi(1) > \pi(3))\) and \((4 < 5) \to (\pi(4) > \pi(5))\).
We can use SageMath to check our work:
8.1 Parity of the number of inversions
Inversions as a concept have a few uses in combinatorics. Relevant to us now is that the number of inversions has the same parity as the permutation. To show this, we will consider how a single transposition affects this parity. But since the total number can go up or down, let us define a quantity which we can analyze to describe the parity.
For the identity permutation, define \[ V(1) = \prod_{i < j} (j - i) \]
E.g. for \(n = 4\) this is \((2 - 1)(3 - 1)(4 - 1)(3 - 2)(4 - 2)(4 - 3)\). We’re not interested in the absolute value here but rather the sign—which for the identity permutation is \(+1\).
More generally, define \[ V(\pi) = \prod_{i < j}(\pi(j) - \pi(i)). \]
Note that we will have a factor of \(V(\pi)\) which is negative whenever \(i < j\) and \(\pi(i) > \pi(j)\). So the sign of \(V(\pi)\) tells us the parity of the number of inversions.
What’s useful here is that factoring out the various \(-1\)’s and reordering, we can write \(V(\pi) = \pm V(1)\) where it is a \(+1\) if we have an even number of inversions and a \(-1\) if we have an odd number.
8.2 Analysis
We want to show that a single transposition changes \(V(1)\) to \(-V(1)\). Then a sequence of odd length will have a sign of \(-1\) and one of even length will have a sign of \(+1\), matching what we did in Chapter 7.
Suppose we apply the transposition \((ij)\) with \(i < j\). Right away, we get one inversion because now \(\pi(i) > \pi(j)\). Let’s look at the other numbers. Suppose \(x < i < j\). Then after swapping, we still have \(x\) on the left of \(i,j\)$ so no inversions here. Likewise, if \(i < j < x\) then \(x\) will still be on the right afterwards.
The last case is that \(i < x < j\). Then we get two inversions going from \(i,x,j\) to \(j,x,i\). One between \(i\) and \(x\) and one between \(x\) and \(j\) since both these pairs are now out of order.
To summarize, this single transposition gives us:
- \(0\) inversions for anything left of \(i\) or right of \(j\),
- \(2\) inversions for each number in between,
- \(1\) inversion for the pair \(i, j\)
So overall we get an odd number of inversions for each swap. This shows that the number of inversions is odd if and only if the number of swaps is odd.