Refined inversion statistics on permutations
Electronic Journal of Combinatorics, Volume 19 (2012)
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 (\leq
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.
Download the paper
Presentations
- Counting special inversions in permutations, Mathematics Colloquium, University of Iceland, Reykjavik, Iceland, November 2010 (Henning presented)
- Counting special inversions in permutations, Mathematics Colloquium, California State University, Long Beach, California, December 2010 (Joshua presented)
- Refined inversion statistics on permutations, 2012 Joint Mathematics Meetings, Boston, MA, January 2012 (Joshua presented)
Later work (last updated 2 October 2026)
- M. Schreyer, R. Paulin and W. Trutschnig, On the exact region determined by Kendall’s τ and Spearman’s ρ, J. R. Stat. Soc. Ser. B 79 (2017). Determines all possible pairs of values of the rank correlations Kendall’s τ and Spearman’s ρ, using analogues of the inversion sums studied here.
- R. Davis, Width-k generalizations of classical permutation statistics, J. Integer Seq. 20 (2017). Generalizes descents and inversions to width-k descents and inversions, building on the k-step inversions introduced here, with analogues of the classical equidistribution results.
- J. Elder, N. Lafrenière, E. McNicholas, J. Striker and A. Welch, Homomesies on permutations: an analysis of maps and statistics in the FindStat database, Math. Comp. 93 (2024). Among many homomesies, shows that the cosine of a permutation, $\sum_i i\sigma_i$, a statistic named after a construction in this paper, is homomesic under the reverse and the complement maps.
- M. Ben Abdelmaksoud and A. Hamdi, Width-k Eulerian polynomials of type A and B: the γ-positivity, J. Algebra Comb. Discrete Struct. Appl. 11 (2024). Extends these statistics to signed permutations, giving width-k Eulerian polynomials of types A, B and D, and proves their γ-positivity.
- N. Chapelier-Laget and T. Gerber, Atomic length on Weyl groups, J. Comb. Algebra (2024). Shows that the inversion sum studied here is the atomic length in type A, and that the atomic length takes every value in its range in every Weyl group except in rank two, recovering a result of this paper as a special case.
- N. Chapelier-Laget, T. Gerber, N. Jacon and C. Lecouvey, Entropy of affine permutations and universality of affine atomic lengths, preprint (2026). Takes the question to affine permutations: every nonnegative integer is the entropy of some affine permutation, an analogue of the Granville–Ono theorem.
- M. Braverman and O. Zamir, Parity and pattern detection in permutation streams, preprint (2026). Streaming algorithms that detect patterns of length three in a permutation using little memory; they use identities from this paper, among others.
- All citing papers on Google Scholar (12)