Inversion of a permutation ($\mathrm{inv}(\pi )$)

For a permutation $\pi$ of $\{1,\dots ,n\}$, an inversion is a pair $i<j$ with $\pi (i)>\pi (j)$. Its number equals the Coxeter length for adjacent transpositions: each adjacent swap changes the count by one, and swapping adjacent descents sorts the permutation in exactly that many steps.

The inversion number of a permutation $a_1\cdots a_n$ isFor 3142, the inverted pairs of values are $(3,1),(3,2),(4,2)$, giving three. The inversion number ranges from zero for increasing order to $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ for decreasing order; it is the minimum number of adjacent transpositions needed to sort the permutation. Its parity gives the sign of a permutation, $(-1{)}^{\mathrm{inv}(a)}$. The same pair-counting formula defines the word inversion number when repeated symbols are allowed.