- FindStat

edit this statistic or download as text // json

Identifier

St000692: Permutations ⟶ ℤ

Values

[] => 0

[1] => 0

[1,2] => 0

[2,1] => 1

[1,2,3] => 0

[1,3,2] => 2

[2,1,3] => 2

[2,3,1] => 1

[3,1,2] => 1

[3,2,1] => 3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

>>> Load all 2998 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

Babson and Steingrímsson's statistic of a permutation.
In terms of generalized patterns this is
$$ (13-2) + (21-3) + (32-1) + (21). $$
Here, $(\pi)$ denotes the number of times the pattern $\pi$ occurs in a permutation, and letters in the pattern which are not separated by a dash must appear consecutively.

References

[1] Babson, E., Steingr'ımsson, E. Generalized permutation patterns and a classification of the Mahonian statistics MathSciNet:1758852
[2] Foata, D., Zeilberger, D. Babson-Steingrímsson statistics are indeed Mahonian (and sometimes even Euler-Mahonian) MathSciNet:1868972
[3] Burstein, A. On joint distribution of adjacencies, descents and some Mahonian statistics MathSciNet:2673870
[4] Chen, J. N., Li, S. A new bijective proof of Babson and Steingr'$\{$$\backslash $i$\}$msson's conjecture arXiv:1701.08044

Code

def statistic(pi):
    return (mesh_pattern_occurrences(pi, [1,3,2], [(1,0),(1,1),(1,2),(1,3)]) 
          + mesh_pattern_occurrences(pi, [2,1,3], [(1,0),(1,1),(1,2),(1,3)]) 
          + mesh_pattern_occurrences(pi, [3,2,1], [(1,0),(1,1),(1,2),(1,3)]) 
          + mesh_pattern_occurrences(pi, [2,1], [(1,0),(1,1),(1,2)]))

def G(w):
    return [ (x+1,y) for (x,y) in enumerate(w) ]

def mesh_pattern_occurrences(perm, pat, R=[]):
    occs = 0
    k = len(pat)
    n = len(perm)
    pat = G(pat)
    perm = G(perm)
    for H in Subsets(perm, k):
        H = sorted(H)
        X = dict(G(sorted(i for (i,_) in H)))
        Y = dict(G(sorted(j for (_,j) in H)))
        if H == [ (X[i], Y[j]) for (i,j) in pat ]:
            X[0], X[k+1] = 0, n+1
            Y[0], Y[k+1] = 0, n+1
            shady = ( X[i] < x < X[i+1] and Y[j] < y < Y[j+1]
                      for (i,j) in R
                      for (x,y) in perm
                      )
            if not any(shady):
                occs = occs + 1
    return occs

Created

Jan 30, 2017 at 08:13 by Martin Rubey

Updated

Feb 07, 2023 at 20:43 by Will Dowling