Motzkin paths and reduced decompositions for permutations with forbidden patterns (Q1408518)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Motzkin paths and reduced decompositions for permutations with forbidden patterns
scientific article

    Statements

    Motzkin paths and reduced decompositions for permutations with forbidden patterns (English)
    0 references
    0 references
    0 references
    0 references
    24 September 2003
    0 references
    Summary: We obtain a characterization of \((321, 3\bar{1}42)\)-avoiding permutations in terms of their canonical reduced decompositions. This characterization is used to construct a bijection for a recent result that the number of \((321,3\bar{1}42)\)-avoiding permutations of length \(n\) equals the \(n\)th Motzkin number, due to Gire, and further studied by Barcucci, Del Lungo, Pergola, Pinzani and Guibert. Similarly, we obtain a characterization of \((231,4\bar{1}32)\)-avoiding permutations. For these two classes, we show that the number of descents of a permutation equals the number of up steps on the corresponding Motzkin path. Moreover, we find a relationship between the inversion number of a permutation and the area of the corresponding Motzkin path.
    0 references

    Identifiers