Motzkin Paths and Reduced Decompositions for Permutations with Forbidden Patterns

Abstract

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.