- FindStat

edit this statistic or download as text // json

Identifier

St000463: Permutations ⟶ ℤ

Values

[] => 0

[1] => 0

[1,2] => 0

[2,1] => 0

[1,2,3] => 0

[1,3,2] => 1

[2,1,3] => 0

[2,3,1] => 2

[3,1,2] => 0

[3,2,1] => 0

[1,2,3,4] => 0

[1,2,4,3] => 1

[1,3,2,4] => 1

[1,3,4,2] => 2

[1,4,2,3] => 2

[1,4,3,2] => 2

[2,1,3,4] => 0

[2,1,4,3] => 1

[2,3,1,4] => 2

[2,3,4,1] => 3

[2,4,1,3] => 3

[2,4,3,1] => 3

[3,1,2,4] => 0

[3,1,4,2] => 2

[3,2,1,4] => 0

[3,2,4,1] => 3

[3,4,1,2] => 4

[3,4,2,1] => 4

[4,1,2,3] => 0

[4,1,3,2] => 1

[4,2,1,3] => 0

[4,2,3,1] => 2

[4,3,1,2] => 0

[4,3,2,1] => 0

[1,2,3,4,5] => 0

[1,2,3,5,4] => 1

[1,2,4,3,5] => 1

[1,2,4,5,3] => 2

[1,2,5,3,4] => 2

[1,2,5,4,3] => 2

[1,3,2,4,5] => 1

[1,3,2,5,4] => 2

[1,3,4,2,5] => 2

[1,3,4,5,2] => 3

[1,3,5,2,4] => 3

[1,3,5,4,2] => 3

[1,4,2,3,5] => 2

[1,4,2,5,3] => 3

[1,4,3,2,5] => 2

[1,4,3,5,2] => 4

[1,4,5,2,3] => 4

[1,4,5,3,2] => 4

[1,5,2,3,4] => 3

[1,5,2,4,3] => 4

[1,5,3,2,4] => 3

[1,5,3,4,2] => 5

[1,5,4,2,3] => 3

[1,5,4,3,2] => 3

[2,1,3,4,5] => 0

[2,1,3,5,4] => 1

[2,1,4,3,5] => 1

[2,1,4,5,3] => 2

[2,1,5,3,4] => 2

[2,1,5,4,3] => 2

[2,3,1,4,5] => 2

[2,3,1,5,4] => 3

[2,3,4,1,5] => 3

[2,3,4,5,1] => 4

[2,3,5,1,4] => 4

[2,3,5,4,1] => 4

[2,4,1,3,5] => 3

[2,4,1,5,3] => 4

[2,4,3,1,5] => 3

[2,4,3,5,1] => 5

[2,4,5,1,3] => 5

[2,4,5,3,1] => 5

[2,5,1,3,4] => 4

[2,5,1,4,3] => 5

[2,5,3,1,4] => 4

[2,5,3,4,1] => 6

[2,5,4,1,3] => 4

[2,5,4,3,1] => 4

[3,1,2,4,5] => 0

[3,1,2,5,4] => 1

[3,1,4,2,5] => 2

[3,1,4,5,2] => 3

[3,1,5,2,4] => 3

[3,1,5,4,2] => 3

[3,2,1,4,5] => 0

[3,2,1,5,4] => 1

[3,2,4,1,5] => 3

[3,2,4,5,1] => 4

[3,2,5,1,4] => 4

[3,2,5,4,1] => 4

[3,4,1,2,5] => 4

[3,4,1,5,2] => 5

[3,4,2,1,5] => 4

[3,4,2,5,1] => 6

[3,4,5,1,2] => 6

[3,4,5,2,1] => 6

[3,5,1,2,4] => 5

>>> Load all 3000 entries. <<<

search for individual values

searching the database for the individual values of this statistic

/ search for generating function

searching the database for statistics with the same generating function

click to show known generating functions

Description

The number of admissible inversions of a permutation.
Let $w = w_1,w_2,\dots,w_k$ be a word of length $k$ with distinct letters from $[n]$.
An admissible inversion of $w$ is a pair $(w_i,w_j)$ such that $1\leq i < j\leq k$ and $w_i > w_j$ that satisfies either of the following conditions:
$1 < i$ and $w_{i−1} < w_i$ or there is some $l$ such that $i < l < j$ and $w_i < w_l$.

References

[1] Lin, Z., Zeng, J. The γ-positivity of basic Eulerian polynomials via group actions arXiv:1411.3397

Code

def statistic(w):
    return len(admissible_inversions(w))

def admissible_inversions(w):
    """
    sage: len(admissible_inversions([2,9,1,7,5,3,4,6,8]))
    12
    """
    return [(i,j) for (i,j) in Permutation(w).inversions()
            if admissible_inversion(w, i, j)]
    
def admissible_inversion(w, i, j):
    return (w[i-1] > w[j-1] and
            ((1 < i and w[i-2] < w[i-1]) or
             any(w[i-1] < w[l-1] for l in range(i+1, j))))

Created

Apr 07, 2016 at 12:05 by Martin Rubey

Updated

Jan 12, 2018 at 22:07 by Martin Rubey