Motzkin paths and reduced decompositions for permutations with forbidden patterns

William Y. C. Chen,  Yu P. Deng  and  Laura L. M. Yang

  Abstract:  We obtain a characterization of -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 -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 -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.

  AMS Classification:  05A05, 05A15.

  Keywords:  Permutations with forbidden patterns, Motzkin paths, reduced decomposition, descents, strip decomposition, trapezoidal decomposition, inversion number.