Combinatorics of Permutations, 3rd Edition

2In One Line and Anywhere. Permutations as Linear Orders. Inversions.

DOI: 10.1201/9780429274107-2

2.1 Inversions

2.1.1 Generating Function of Permutations by Inversions

In Section 1.1, we looked at descents of permutations. That is, we studied instances in which an entry in a permutation was larger than the entry directly following it. A more “global” permutation statistic is that of inversions. This statistic will look for instances in which an entry of a permutation is smaller than some entry following it (not necessarily directly).

DEFINITION 2.1 Let $p=p_1{p}_2\cdots p_n$ be a permutation. We say that $(p_i,p_j)$ is an inversion of p if $i<j$ but $p_i>p_j$.

Example 2.2

Permutation 31524 has four inversions, namely $(3,1)$, $(3,2)$, $(5,2)$, and $(5,4)$.  ▯