2012The Electronic Journal of CombinatoricsOpen access

Refined Inversion Statistics on Permutations

Joshua Sack, Henning Úlfarsson

Open full text 8 citations

Abstract

We introduce and study new refinements of inversion statistics for permutations, such as $k$-step inversions, (the number of inversions with fixed position differences) and non-inversion sums (the sum of the differences of positions of the non-inversions of a permutation). We also provide a distribution function for non-inversion sums, a distribution function for $k$-step inversions that relates to the Eulerian polynomials, and special cases of distribution functions for other statistics we introduce, such as $(\le\!\!k)$-step inversions and $(k_1,k_2)$-step inversions (that fix the value separation as well as the position). We connect our refinements to other work, such as inversion tops that are $0$ modulo a fixed integer $d$, left boundary sums of paths, and marked meshed patterns. Finally, we use non-inversion sums to show that for every number $n>34$, there is a permutation such that the dot product of that permutation and the identity permutation (of the same length) is $n$.

Open-access reader

About this research paper

What this paper is about

We introduce and study new refinements of inversion statistics for permutations, such as $k$-step inversions, (the number of inversions with fixed position differences) and non-inversion sums (the sum of the differences of positions of the non-inversions of a permutation). We also provide a distribution function for non-inversion sums, a distribution function for $k$-step inversions that relates to the Eulerian polynomials, and special cases of distribution functions for other statistics we introduce, such as $(\le\!\!k)$-step inversions and $(k_1,k_2)$-step inversions (that fix the value separation as well as the position). We connect our refinements to other work, such as inversion tops that are $0$ modulo a fixed integer $d$, left boundary sums of paths, and marked meshed patterns. Finally, we use non-inversion sums to show that for every number $n>34$, there is a permutation such that the dot product of that permutation and the identity permutation (of the same length) is $n$.

Why it matters

OpenAlex reports 8 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

We introduce and study new refinements of inversion statistics for permutations, such as $k$-step inversions, (the number of inversions with fixed position differences) and non-inversion sums (the sum of the differences of positions of the non-inversions of a permutation). We also provide a distribution function for non-inversion sums, a distribution function for $k$-step inversions that relates to the Eulerian polynomials, and special cases of distribution functions for other statistics we introduce, such as $(\le\!\!k)$-step inversions and $(k_1,k_2)$-step inversions (that fix the value separation as well as the position). We connect our refinements to other work, such as inversion tops that are $0$ modulo a fixed integer $d$, left boundary sums of paths, and marked meshed patterns. Finally, we use non-inversion sums to show that for every number $n>34$, there is a permutation such that the dot product of that permutation and the identity permutation (of the same length) is $n$.

Key concepts: Mathematics, Inversion (geology), Permutation (music), Combinatorics, Modulo, Random permutation, Eulerian path, Discrete mathematics

Related papers

Back to paper searchBrowse research topicsOriginal source
Refined Inversion Statistics on Permutations — Research Paper | ScholarLens