- FindStat

edit this map or download as text // json

Identifier

Mp00296: Dyck paths —Knuth-Krattenthaler⟶ Dyck paths

Images

[] => []

[1,0] => [1,0]

[1,0,1,0] => [1,1,0,0]

[1,1,0,0] => [1,0,1,0]

[1,0,1,0,1,0] => [1,1,1,0,0,0]

[1,0,1,1,0,0] => [1,1,0,1,0,0]

[1,1,0,0,1,0] => [1,0,1,0,1,0]

[1,1,0,1,0,0] => [1,0,1,1,0,0]

[1,1,1,0,0,0] => [1,1,0,0,1,0]

[1,0,1,0,1,0,1,0] => [1,1,1,1,0,0,0,0]

[1,0,1,0,1,1,0,0] => [1,1,1,0,1,0,0,0]

[1,0,1,1,0,0,1,0] => [1,1,0,1,0,1,0,0]

[1,0,1,1,0,1,0,0] => [1,1,0,1,1,0,0,0]

[1,0,1,1,1,0,0,0] => [1,1,1,0,0,1,0,0]

[1,1,0,0,1,0,1,0] => [1,0,1,1,0,0,1,0]

[1,1,0,0,1,1,0,0] => [1,0,1,0,1,0,1,0]

[1,1,0,1,0,0,1,0] => [1,0,1,1,0,1,0,0]

[1,1,0,1,0,1,0,0] => [1,0,1,1,1,0,0,0]

[1,1,0,1,1,0,0,0] => [1,0,1,0,1,1,0,0]

[1,1,1,0,0,0,1,0] => [1,1,0,1,0,0,1,0]

[1,1,1,0,0,1,0,0] => [1,1,0,0,1,0,1,0]

[1,1,1,0,1,0,0,0] => [1,1,0,0,1,1,0,0]

[1,1,1,1,0,0,0,0] => [1,1,1,0,0,0,1,0]

[1,0,1,0,1,0,1,0,1,0] => [1,1,1,1,1,0,0,0,0,0]

[1,0,1,0,1,0,1,1,0,0] => [1,1,1,1,0,1,0,0,0,0]

[1,0,1,0,1,1,0,0,1,0] => [1,1,1,0,1,0,1,0,0,0]

[1,0,1,0,1,1,0,1,0,0] => [1,1,1,0,1,1,0,0,0,0]

[1,0,1,0,1,1,1,0,0,0] => [1,1,1,1,0,0,1,0,0,0]

[1,0,1,1,0,0,1,0,1,0] => [1,1,0,1,1,0,0,1,0,0]

[1,0,1,1,0,0,1,1,0,0] => [1,1,0,1,0,1,0,1,0,0]

[1,0,1,1,0,1,0,0,1,0] => [1,1,0,1,1,0,1,0,0,0]

[1,0,1,1,0,1,0,1,0,0] => [1,1,0,1,1,1,0,0,0,0]

[1,0,1,1,0,1,1,0,0,0] => [1,1,0,1,0,1,1,0,0,0]

[1,0,1,1,1,0,0,0,1,0] => [1,1,1,0,1,0,0,1,0,0]

[1,0,1,1,1,0,0,1,0,0] => [1,1,1,0,0,1,0,1,0,0]

[1,0,1,1,1,0,1,0,0,0] => [1,1,1,0,0,1,1,0,0,0]

[1,0,1,1,1,1,0,0,0,0] => [1,1,1,1,0,0,0,1,0,0]

[1,1,0,0,1,0,1,0,1,0] => [1,0,1,1,1,0,0,0,1,0]

[1,1,0,0,1,0,1,1,0,0] => [1,0,1,1,0,1,0,0,1,0]

[1,1,0,0,1,1,0,0,1,0] => [1,0,1,0,1,0,1,0,1,0]

[1,1,0,0,1,1,0,1,0,0] => [1,0,1,0,1,1,0,0,1,0]

[1,1,0,0,1,1,1,0,0,0] => [1,0,1,1,0,0,1,0,1,0]

[1,1,0,1,0,0,1,0,1,0] => [1,0,1,1,1,0,0,1,0,0]

[1,1,0,1,0,0,1,1,0,0] => [1,0,1,1,0,1,0,1,0,0]

[1,1,0,1,0,1,0,0,1,0] => [1,0,1,1,1,0,1,0,0,0]

[1,1,0,1,0,1,0,1,0,0] => [1,0,1,1,1,1,0,0,0,0]

[1,1,0,1,0,1,1,0,0,0] => [1,0,1,1,0,1,1,0,0,0]

[1,1,0,1,1,0,0,0,1,0] => [1,0,1,0,1,0,1,1,0,0]

[1,1,0,1,1,0,0,1,0,0] => [1,0,1,0,1,1,0,1,0,0]

[1,1,0,1,1,0,1,0,0,0] => [1,0,1,0,1,1,1,0,0,0]

[1,1,0,1,1,1,0,0,0,0] => [1,0,1,1,0,0,1,1,0,0]

[1,1,1,0,0,0,1,0,1,0] => [1,1,0,1,1,0,0,0,1,0]

[1,1,1,0,0,0,1,1,0,0] => [1,1,0,1,0,1,0,0,1,0]

[1,1,1,0,0,1,0,0,1,0] => [1,1,0,0,1,0,1,0,1,0]

[1,1,1,0,0,1,0,1,0,0] => [1,1,0,0,1,1,0,0,1,0]

[1,1,1,0,0,1,1,0,0,0] => [1,1,0,1,0,0,1,0,1,0]

[1,1,1,0,1,0,0,0,1,0] => [1,1,0,0,1,0,1,1,0,0]

[1,1,1,0,1,0,0,1,0,0] => [1,1,0,0,1,1,0,1,0,0]

[1,1,1,0,1,0,1,0,0,0] => [1,1,0,0,1,1,1,0,0,0]

[1,1,1,0,1,1,0,0,0,0] => [1,1,0,1,0,0,1,1,0,0]

[1,1,1,1,0,0,0,0,1,0] => [1,1,1,0,1,0,0,0,1,0]

[1,1,1,1,0,0,0,1,0,0] => [1,1,1,0,0,1,0,0,1,0]

[1,1,1,1,0,0,1,0,0,0] => [1,1,1,0,0,0,1,0,1,0]

[1,1,1,1,0,1,0,0,0,0] => [1,1,1,0,0,0,1,1,0,0]

[1,1,1,1,1,0,0,0,0,0] => [1,1,1,1,0,0,0,0,1,0]

[1,0,1,0,1,0,1,0,1,0,1,0] => [1,1,1,1,1,1,0,0,0,0,0,0]

[1,0,1,0,1,0,1,0,1,1,0,0] => [1,1,1,1,1,0,1,0,0,0,0,0]

[1,0,1,0,1,0,1,1,0,0,1,0] => [1,1,1,1,0,1,0,1,0,0,0,0]

[1,0,1,0,1,0,1,1,0,1,0,0] => [1,1,1,1,0,1,1,0,0,0,0,0]

[1,0,1,0,1,0,1,1,1,0,0,0] => [1,1,1,1,1,0,0,1,0,0,0,0]

[1,0,1,0,1,1,0,0,1,0,1,0] => [1,1,1,0,1,1,0,0,1,0,0,0]

[1,0,1,0,1,1,0,0,1,1,0,0] => [1,1,1,0,1,0,1,0,1,0,0,0]

[1,0,1,0,1,1,0,1,0,0,1,0] => [1,1,1,0,1,1,0,1,0,0,0,0]

[1,0,1,0,1,1,0,1,0,1,0,0] => [1,1,1,0,1,1,1,0,0,0,0,0]

[1,0,1,0,1,1,0,1,1,0,0,0] => [1,1,1,0,1,0,1,1,0,0,0,0]

[1,0,1,0,1,1,1,0,0,0,1,0] => [1,1,1,1,0,1,0,0,1,0,0,0]

[1,0,1,0,1,1,1,0,0,1,0,0] => [1,1,1,1,0,0,1,0,1,0,0,0]

[1,0,1,0,1,1,1,0,1,0,0,0] => [1,1,1,1,0,0,1,1,0,0,0,0]

[1,0,1,0,1,1,1,1,0,0,0,0] => [1,1,1,1,1,0,0,0,1,0,0,0]

[1,0,1,1,0,0,1,0,1,0,1,0] => [1,1,0,1,1,1,0,0,0,1,0,0]

[1,0,1,1,0,0,1,0,1,1,0,0] => [1,1,0,1,1,0,1,0,0,1,0,0]

[1,0,1,1,0,0,1,1,0,0,1,0] => [1,1,0,1,0,1,0,1,0,1,0,0]

[1,0,1,1,0,0,1,1,0,1,0,0] => [1,1,0,1,0,1,1,0,0,1,0,0]

[1,0,1,1,0,0,1,1,1,0,0,0] => [1,1,0,1,1,0,0,1,0,1,0,0]

[1,0,1,1,0,1,0,0,1,0,1,0] => [1,1,0,1,1,1,0,0,1,0,0,0]

[1,0,1,1,0,1,0,0,1,1,0,0] => [1,1,0,1,1,0,1,0,1,0,0,0]

[1,0,1,1,0,1,0,1,0,0,1,0] => [1,1,0,1,1,1,0,1,0,0,0,0]

[1,0,1,1,0,1,0,1,0,1,0,0] => [1,1,0,1,1,1,1,0,0,0,0,0]

[1,0,1,1,0,1,0,1,1,0,0,0] => [1,1,0,1,1,0,1,1,0,0,0,0]

[1,0,1,1,0,1,1,0,0,0,1,0] => [1,1,0,1,0,1,0,1,1,0,0,0]

[1,0,1,1,0,1,1,0,0,1,0,0] => [1,1,0,1,0,1,1,0,1,0,0,0]

[1,0,1,1,0,1,1,0,1,0,0,0] => [1,1,0,1,0,1,1,1,0,0,0,0]

[1,0,1,1,0,1,1,1,0,0,0,0] => [1,1,0,1,1,0,0,1,1,0,0,0]

[1,0,1,1,1,0,0,0,1,0,1,0] => [1,1,1,0,1,1,0,0,0,1,0,0]

[1,0,1,1,1,0,0,0,1,1,0,0] => [1,1,1,0,1,0,1,0,0,1,0,0]

[1,0,1,1,1,0,0,1,0,0,1,0] => [1,1,1,0,0,1,0,1,0,1,0,0]

[1,0,1,1,1,0,0,1,0,1,0,0] => [1,1,1,0,0,1,1,0,0,1,0,0]

[1,0,1,1,1,0,0,1,1,0,0,0] => [1,1,1,0,1,0,0,1,0,1,0,0]

[1,0,1,1,1,0,1,0,0,0,1,0] => [1,1,1,0,0,1,0,1,1,0,0,0]

[1,0,1,1,1,0,1,0,0,1,0,0] => [1,1,1,0,0,1,1,0,1,0,0,0]

[1,0,1,1,1,0,1,0,1,0,0,0] => [1,1,1,0,0,1,1,1,0,0,0,0]

>>> Load all 2738 entries. <<<

click to show experimental identities (only identities of compositions of up to three maps are shown)

Description

The map that sends the Dyck path to a 321-avoiding permutation, then applies the Robinson-Schensted correspondence and finally interprets the first row of the insertion tableau and the second row of the recording tableau as up steps.
Interpreting a pair of two-row standard tableaux of the same shape as a Dyck path is explained by Knuth in [1, pp. 60].
Krattenthaler's bijection between Dyck paths and $321$-avoiding permutations used is Mp00119to 321-avoiding permutation (Krattenthaler), see [2].
This is the inverse of the map Mp00127left-to-right-maxima to Dyck path that interprets the left-to-right maxima of the permutation obtained from Mp00024to 321-avoiding permutation as a Dyck path.

References

[1] Knuth, D. E. The art of computer programming. Vol. 3 MathSciNet:3077154
[2] Krattenthaler, C. Permutations with restricted patterns and Dyck paths arXiv:math/0002200

Properties

bijective, graded

Sage code

def mapping(D):
    return from_pair_of_standard_tableaux(*RSK(to_321_avoiding_permutation(D)))

def from_pair_of_standard_tableaux(P, Q):
    """
    Return a Dyck path from a pair of SYT of the same shape with at most two rows.

    sage: all(from_pair_of_SYT(*D.to_pair_of_standard_tableaux()) == D for D in DyckWords(9))
    True
    """
    n = 2*P.size()
    D = [0]*(n)
    if not P:
        return DyckWord(D)
    for p in P[0]:
        D[p-1] = 1
    if len(Q) == 2:
        for p in Q[1]:
            D[n-p] = 1
    return DyckWord(D)

def to_321_avoiding_permutation(P):
    n = (len(P)//2)
    a = P.rise_composition()
    A = [sum(a[:i+1]) for i in range(len(a))]
    d = P.reverse().rise_composition().reversed()
    D = [sum(d[:i]) for i in range(len(a))]
    pi = [None]*n
    rest = list(range(1, n+1))
    for (e,f) in zip(A, D):
        pi[f] = e
        rest.remove(e)

    i = 0
    for e in rest:
        while pi[i] is not None:
            i += 1
        pi[i] = e
        
    return Permutation(pi)

Weight

Created

Jun 12, 2023 at 11:15 by Martin Rubey

Updated

Jun 12, 2023 at 11:15 by Martin Rubey