- FindStat

edit this statistic or download as text // json

Identifier

St000500: Permutations ⟶ ℤ

Values

[] => 0

[1] => 1

[1,2] => 4

[2,1] => 0

[1,2,3] => 9

[1,3,2] => 4

[2,1,3] => 0

[2,3,1] => 4

[3,1,2] => 0

[3,2,1] => 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Eigenvalues of the random-to-random operator acting on the regular representation.
This statistic is defined for a permutation $w$ as:
$$ \left[\binom{\ell(w) + 1}{2} + \operatorname{diag}\left(Q(w)\right)\right] - \left[\binom{\ell(u) + 1}{2} + \operatorname{diag}\left(Q(u)\right)\right] $$
where:

$u$ is the longest suffix of $w$ (viewed as a word) whose first ascent is even;
$\ell(w)$ is the size of the permutation $w$ (equivalently, the length of the word $w$);
$Q(w), Q(u)$ denote the recording tableaux of $w, u$ under the RSK correspondence;
$\operatorname{diag}(\lambda)$ denotes the diagonal index (or content) of an integer partition $\lambda$;
and $\operatorname{diag}(T)$ of a tableau $T$ denotes the diagonal index of the partition given by the shape of $T$.

The regular representation of the symmetric group of degree n has dimension n!, so any linear operator acting on this vector space has n! eigenvalues (counting multiplicities). Hence, the eigenvalues of the random-to-random operator can be indexed by permutations; and the values of this statistic give all the eigenvalues of the operator (Theorem 12 of [1]).

References

[1] Dieker, A. B., Saliola, F. Spectral analysis of random-to-random Markov chains arXiv:1509.08580

Code

def is_desarrangement_word(w):
    r"""
    EXAMPLES::

        sage: for n in range(4):
        ....:     for perm in Permutations(n):
        ....:         print "%s => %s" % (perm, is_desarrangement_word(perm))
        [] => True
        [1] => False
        [1, 2] => False
        [2, 1] => True
        [1, 2, 3] => False
        [1, 3, 2] => False
        [2, 1, 3] => True
        [2, 3, 1] => False
        [3, 1, 2] => True
        [3, 2, 1] => False
    """
    X = [k for k in range(len(w)-1) if w[k] <= w[k+1]]
    if X:
        return X[0] % 2 == 1
    else:
        return len(w) % 2 == 0

def desarrangement_factorization(w):
    r"""
    EXAMPLES::

        sage: for n in range(4):
        ....:     for perm in Permutations(n):
        ....:         print "%s => %s" % (perm, desarrangement_factorization(perm))
        [] => ([], [])
        [1] => ([1], [])
        [1, 2] => ([1, 2], [])
        [2, 1] => ([], [2, 1])
        [1, 2, 3] => ([1, 2, 3], [])
        [1, 3, 2] => ([1], [3, 2])
        [2, 1, 3] => ([], [2, 1, 3])
        [2, 3, 1] => ([2], [3, 1])
        [3, 1, 2] => ([], [3, 1, 2])
        [3, 2, 1] => ([3], [2, 1])
    """
    for i in range(len(w) + 1):
        u = Word(w[i:]).standard_permutation()
        if is_desarrangement_word(u):
            return w[:i], w[i:]

def diagonal_index_of_partition(la):
    return sum((j - i) for (i, j) in la.cells())

def binomial_shifted_diagonal_index_of_partition(partition):
    return binomial(partition.size() + 1, 2) + diagonal_index_of_partition(partition)

def statistic(w):
    r"""
    EXAMPLES::

        sage: for n in range(5):
        ....:     for perm in Permutations(n):
        ....:         print "%s => %s" % (perm, statistic(perm))
        [] => 0
        [1] => 1
        [1, 2] => 4
        [2, 1] => 0
        [1, 2, 3] => 9
        [1, 3, 2] => 4
        [2, 1, 3] => 0
        [2, 3, 1] => 4
        [3, 1, 2] => 0
        [3, 2, 1] => 1
    """
    Qw = RSK(w)[1]
    _, u = desarrangement_factorization(w)
    Qu = RSK(u)[1]
    Qw_index = binomial_shifted_diagonal_index_of_partition(Qw.shape())
    Qu_index = binomial_shifted_diagonal_index_of_partition(Qu.shape())
    return Qw_index - Qu_index

Created

May 23, 2016 at 21:58 by Franco Saliola

Updated

Jan 13, 2018 at 15:45 by Martin Rubey