Skip to main content
1 of 8

Sortedness of permutations of an n element ordering: inversions versus "adjacent pairs"

If we order $n$ elements such as these 4,

$1234$,

and consider some permutations of those elements, we can classify them by the number of inversions. Another way to classify them is by what I am calling the number of "adjacent pairs" shared by the ordering and a given permutation, but maybe there is another term I should be using. So I'll have to explain what I mean by shared adjacent pairs.

$1423$ has $2$ inversions: $(23)$ and $(24)$, where the numbers in parentheses indicate which positions (indices) are out of order. $1423$ has one adjacent pair shared with the ordering given by indices $(34)$, or the elements $(2,3)$ Note: I am not concerned whether the adjacent pair is in the same positions, and I am also not concerned with the order of the pair. So $1432$ would have two shared adjacent pairs $(23)$ and $(34)$, and a third and fourth if we're considering cyclic orderings, $(12)$ and $(14)$. $1432$ however has three inversions: $(23),(24)$ and $(34)$.

I am interested in counting the number of these pairs as a function of $n$ in $S_{n}$ and certain subgroups. A generating function giving the fraction of the permutations having $i={0,1,2,..n}$ shared adjacent pairs would be particularly interesting to me, but terminology, references or general guidance might be more helpful so I could pursue this further on my own.