 Inversion number

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.