6.3 Inversions
Position pair \((i, j)\) is an inversion of \(\sigma \) when \(i {\lt} j\) but \(\sigma (j) {\lt} \sigma (i)\) — i.e., the pair appears in the “wrong” order.
\(\mathrm{inv\_ set}(\sigma )\) is the set of inversion pairs; \(\mathrm{inv}(\sigma ) = |\mathrm{inv\_ set}(\sigma )|\) is their count. Stanley writes \(\mathrm{inv}(w)\).
\(\mathrm{inv}(\mathrm{id}) = 0\).
\(\# \{ (i, j) \in \{ 0, \dots , m-1\} ^2 : i {\lt} j\} = \binom {m}{2}\).
\(\mathrm{inv}(\sigma ) \leq \binom {n+1}{2}\). The maximum is achieved by the order-reversing permutation, which has every pair inverted.
Let \(\rev _n \in \mathfrak {S}_{n+1}\) be the order-reversing permutation. Then
Each pair \((i, j)\) with \(i {\lt} j\) is either an inversion or a co-inversion of \(\sigma \) (exactly one), and the bijection \((i, j) \mapsto (\rev _n(j), \rev _n(i))\) swaps the two.